Этот пример показывает, как использовать алгоритм 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. Эти данные были сгенерированы в 2 015 использованиях автоматического поискового робота страницы. Поисковый робот страницы начался в 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% приземлиться на каждой странице. Эта небольшая группа очень связанных страниц формирует клику в центре графика. Соединенный с этой центральной кликой несколько меньших клик, которые высоко соединяются среди себя.
Moler, C. Эксперименты с MATLAB. Глава 7: Google PageRank. MathWorks, Inc., 2011.
centrality | digraph | graph