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

Figure contains an axes object. The axes object with title PageRank Score Transfer Between Nodes contains an object of type graphplot.

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'})

Figure contains an axes object. The axes object contains an object of type graphplot.

Вычислите счет центрированности 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)

Figure contains an axes object. The axes object contains an object of type line.

Создайте ориентированного графа с разреженной матрицей смежности, 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')

Figure contains an axes object. The axes object with title Websites linked to https://www.mathworks.com contains an object of type graphplot.

Вычислите музыку 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

Figure contains an axes object. The axes object with title Websites linked to https://www.mathworks.com contains an object of type graphplot.

Музыка PageRank к главным веб-сайтам все весьма схожа, такова, что у случайного интернет-пользователя есть приблизительно шанс на 4,5% приземлиться на каждой странице. Эта небольшая группа очень связанных страниц формирует клику в центре графика. Соединенный с этой центральной кликой несколько меньших клик, которые высоко соединяются среди себя.

Ссылки

Moler, C. Эксперименты с MATLAB. Глава 7: Google PageRank. MathWorks, Inc., 2011.

Смотрите также

| |