В этом примере показано, как использовать алгоритм 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')
The 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
Результаты показывают, что счет определяет не только количество ссылок на страницы, но и качество. The alpha и gamma оба сайта имеют общую степень 4, однако alpha ссылки на оба epsilon и beta, которые также имеют высокий рейтинг. gamma связана только одной страницей, beta, который находится в середине списка. Таким образом, alpha оценивается выше gamma по алгоритму.
Загрузите данные в mathworks100.mat и просмотрите матрицу смежности, A. Эти данные были сгенерированы в 2015 году с помощью автоматического обходчика страниц. Поиск страниц начался в https://www.mathworks.com и следовали по ссылкам на последующие веб-страницы, пока матрица смежности не содержала информацию о соединениях 100 уникальных веб-страниц.
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