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

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