В этом примере показано, как использовать алгоритм 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