Использование алгоритма PageRank, чтобы Ранжировать веб-сайты
В этом примере показано, как использовать алгоритм 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.
PageRank с 6 узлами
Создайте и постройте ориентированного графа, содержащего шесть узлов, представляющих фиктивные веб-сайты.
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 алгоритмом.
PageRank веб-сайтов на mathworks.com
Загрузите данные в 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