В этом примере показано, как использовать алгоритм PageRank для ранжирования коллекции веб-сайтов. Хотя алгоритм PageRank изначально был разработан для ранжирования результатов поисковой системы, он также может быть более широко применен к узлам во многих различных типах графов. Оценка PageRank дает представление об относительной важности каждого узла графа на основе того, как он связан с другими узлами.
Теоретически, оценка PageRank является предельной вероятностью того, что кто-то случайно щелкает ссылки на каждом веб-сайте, попадет на любую конкретную страницу. Таким образом, страницы с высоким баллом являются очень связанными и обнаруживаемыми в сети, и, скорее всего, случайный веб-серфер посетит эту страницу.
На каждом шаге алгоритма PageRank оценка каждой страницы обновляется в соответствии с:
r = (1-P)/n + P*(A'*(r./d) + s/n);
r является вектором оценок PageRank.
P является скалярным коэффициентом демпфирования (обычно 0,85), который является вероятностью того, что случайный серфер щелкает по ссылке на текущей странице, вместо продолжения на другой случайной странице.
A' - транспонирование матрицы смежности графа.
d - вектор, содержащий степень отклонения каждого узла графа. d имеет значение 1 для узлов без исходящих краев.
n - скалярное число узлов в графе.
s - скалярная сумма оценок PageRank для страниц без ссылок.
Другими словами, ранг каждой страницы во многом основан на рангах страниц, которые на нее ссылаются. Термин A'*(r./d) выбирает оценки исходных узлов, которые связаны с каждым узлом на графике, и оценки нормализуются по общему количеству исходящих ссылок этих исходных узлов. Это гарантирует, что сумма баллов PageRank всегда 1. Например, если узел 2 связан с узлами 1, 3 и 4, то он передает 1/3 своего показателя PageRank каждому из этих узлов во время каждой итерации алгоритма.
Создайте график, иллюстрирующий, как каждый узел присваивает оценку PageRank другим узлам на графике.
s = {'a' 'a' 'a' 'b' 'b' 'c' 'd' 'd' 'd'};
t = {'b' 'c' 'd' 'd' 'a' 'b' 'c' 'a' 'b'};
G = digraph(s,t);
labels = {'a/3' 'a/3' 'a/3' 'b/2' 'b/2' 'c' 'd/3' 'd/3' 'd/3'};
p = plot(G,'Layout','layered','EdgeLabel',labels);
highlight(p,[1 1 1],[2 3 4],'EdgeColor','g')
highlight(p,[2 2],[1 4],'EdgeColor','r')
highlight(p,3,2,'EdgeColor','m')
title('PageRank Score Transfer Between Nodes')
centrality содержит опцию для вычисления баллов PageRank.
Создайте и постройте график, содержащий шесть узлов, представляющих фиктивные веб-сайты.
s = [1 1 2 2 3 3 3 4 5];
t = [2 5 3 4 4 5 6 1 1];
names = {'http://www.example.com/alpha', 'http://www.example.com/beta', ...
'http://www.example.com/gamma', 'http://www.example.com/delta', ...
'http://www.example.com/epsilon', 'http://www.example.com/zeta'};
G = digraph(s,t,[],names)G =
digraph with properties:
Edges: [9x1 table]
Nodes: [6x1 table]
plot(G,'Layout','layered', ... 'NodeLabel',{'alpha','beta','gamma','delta','epsilon','zeta'})
Вычислите показатель центральности PageRank для этого графика. Используйте следующую вероятность (иначе называемую коэффициентом демпфирования) 0.85.
pr = centrality(G,'pagerank','FollowProbability',0.85)
pr = 6×1
0.3210
0.1706
0.1066
0.1368
0.2008
0.0643
Просмотрите оценки PageRank и сведения о степенях для каждой страницы.
G.Nodes.PageRank = pr; G.Nodes.InDegree = indegree(G); G.Nodes.OutDegree = outdegree(G); G.Nodes
ans=6×4 table
Name PageRank InDegree OutDegree
__________________________________ ________ ________ _________
{'http://www.example.com/alpha' } 0.32098 2 2
{'http://www.example.com/beta' } 0.17057 1 2
{'http://www.example.com/gamma' } 0.10657 1 3
{'http://www.example.com/delta' } 0.13678 2 1
{'http://www.example.com/epsilon'} 0.20078 2 1
{'http://www.example.com/zeta' } 0.06432 1 0
Результаты показывают, что не только количество ссылок на страницы определяет оценку, но и качество. alpha и gamma оба веб-сайта имеют общую степень 4, однако alpha ссылки на оба epsilon и beta, которые также высоко ранжированы. gamma связан только с одной страницей, beta, которая находится в середине списка. Таким образом, alpha оценено выше, чем gamma по алгоритму.
Загрузить данные в mathworks100.mat и просмотрите матрицу смежности, A. Эти данные были сгенерированы в 2015 году с помощью автоматического обходчика страниц. Обход страницы начался в https://www.mathworks.com и следовали ссылкам на последующие web-страницы до тех пор, пока матрица смежности не содержала информацию о соединениях 100 уникальных web-страниц.
load mathworks100.mat
spy(A)
Создайте направленный граф с разреженной матрицей смежности, A, используя URL-адреса, содержащиеся в U в виде имен узлов.
G = digraph(A,U)
G =
digraph with properties:
Edges: [632x1 table]
Nodes: [100x1 table]
Постройте график с помощью компоновки силы.
plot(G,'NodeLabel',{},'NodeColor',[0.93 0.78 0],'Layout','force'); title('Websites linked to https://www.mathworks.com')
Вычислите оценки PageRank для графика, G, используя 200 итераций и коэффициент демпфирования 0.85. Добавьте оценки и сведения о степенях в таблицу узлов графика.
pr = centrality(G,'pagerank','MaxIterations',200,'FollowProbability',0.85); G.Nodes.PageRank = pr; G.Nodes.InDegree = indegree(G); G.Nodes.OutDegree = outdegree(G);
Просмотрите 25 лучших итоговых баллов.
G.Nodes(1:25,:)
ans=25×4 table
Name PageRank InDegree OutDegree
______________________________________________________________________________ ________ ________ _________
{'https://www.mathworks.com' } 0.044342 20 14
{'https://ch.mathworks.com' } 0.043085 20 14
{'https://cn.mathworks.com' } 0.043085 20 14
{'https://jp.mathworks.com' } 0.043085 20 14
{'https://kr.mathworks.com' } 0.043085 20 14
{'https://uk.mathworks.com' } 0.043085 20 14
{'https://au.mathworks.com' } 0.043085 20 14
{'https://de.mathworks.com' } 0.043085 20 14
{'https://es.mathworks.com' } 0.043085 20 14
{'https://fr.mathworks.com' } 0.043085 20 14
{'https://in.mathworks.com' } 0.043085 20 14
{'https://it.mathworks.com' } 0.043085 20 14
{'https://nl.mathworks.com' } 0.043085 20 14
{'https://se.mathworks.com' } 0.043085 20 14
{'https://www.mathworks.com/index.html%3Fnocookie%3Dtrue' } 0.0015 0 1
{'https://www.mathworks.com/company/aboutus/policies_statements/patents.html'} 0.007714 6 6
⋮
Извлеките и постройте подграф, содержащий все узлы, оценка которых больше 0.005. Раскрасьте узлы графика на основе их показателя PageRank.
H = subgraph(G,find(G.Nodes.PageRank > 0.005)); plot(H,'NodeLabel',{},'NodeCData',H.Nodes.PageRank,'Layout','force'); title('Websites linked to https://www.mathworks.com') colorbar
Оценки PageRank для лучших веб-сайтов очень похожи, так что случайный веб-серфер имеет около 4,5% шансов приземлиться на каждой странице. Эта небольшая группа сильно связанных страниц образует клику в центре сюжета. С этой центральной кликой связаны несколько более мелких клик, которые сильно связаны между собой.
Молер, С. Эксперименты с MATLAB. Глава 7: Google PageRank. MathWorks, Inc., 2011.
centrality | digraph | graph