使用 PageRank 算法对网站进行排名

以下示例演示如何使用 PageRank 算法对多个网站进行排名。虽然 PageRank 算法最初是为确定搜索引擎结果排名而设计的，但也可以更广泛地应用到许多不同类型的图形中的节点。PageRank 得分根据每个图形节点与其他节点的连接方式，对该节点的相对重要性给出意见。

理论上，PageRank 得分是指某人随机点击每个网站上的链接时会进入任何特定网页的极限概率。因此，得分较高的网页在网络中是高度关联并且可以发现的，随机的 Web 浏览者更可能访问该网页。

算法说明

在 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 得分的选项。

包含 6 个节点的 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'})

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

计算该图形的 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。

mathworks.com 网站的 PageRank 得分

加载 mathworks100.mat 中的数据，并查看邻接矩阵 A。这些数据是使用自动网页爬网程序在 2015 年生成的。网页爬网程序从 https://www.mathworks.com 开始，然后是指向后续网页的链接，直到邻接矩阵包含 100 个唯一网页连接的相关信息。

load mathworks100.mat spy(A)

Figure contains an axes object. The axes object with xlabel nz = 632 contains a line object which displays its values using only markers.

通过将 U 中包含的 URL 用作节点名称，创建带有稀疏邻接矩阵 A 的有向图。

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.

使用 200 次迭代和阻尼因子 0.85 计算图形 G 的 PageRank 得分。将得分和级别信息添加到图形的节点表中。

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 得分都十分相似，因此随机的 Web 浏览者大约有 4.5% 的几率登录每个网页。这一小组高度关联的网页在绘图中心形成了一个团。与这个中心团相连的是几个较小的团，这几个较小的团彼此之间高度关联。

参考

Moler, C. Experiments with MATLAB.Chapter 7:Google PageRank.MathWorks, Inc., 2011.