Использование алгоритма 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)

Просмотрите очки 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

Документация