此示例显示如何使用PageRank算法对网站的集合进行排名。虽然PageRank算法最初被设计为排序搜索引擎结果,但它也可以更广泛地应用于许多不同类型的图表中的节点。PageRank评分基于如何连接到其他节点,给出了每个图节点的相对重要性。
从理论上讲,PageRank分数是指某人随机点击每个网站上的链接将到达任何特定页面的有限概率。因此,得分高的页面在网络中具有高度的连接性和可发现性,更有可能是随机的网络冲浪者访问该页面。
在PageRank算法的每一步中,每个页面的分数都是根据,
r =(1-p)/ n + p *(a'*(r./d)+ s / n);
r
是PageRank分数的向量。
P
是一个标量阻尼因子(通常为0.85),这是一个随机冲浪者点击当前页面上的链接而不是继续浏览另一个随机页面的概率。
一个“
是图的邻接矩阵的转置。
d
是包含图中每个节点的出度的向量。d
被设定为1
对于没有传出边的节点。
n
是图中的标量数的节点。
年代
PageRank分数的标量和没有链接的页面。
换句话说,每个页面的排名很大程度上是基于链接到它的页面的排名。这个词A'*(R./d)
从图表中的每个节点中选择链接的源节点的分数,并且分数由这些源节点的出站链接总数归一化。这确保了PageRank分数的总和始终是1
.例如,如果节点2链接到节点1,3和4,则它会传输1/3
在算法的每次迭代期间,每个节点的PageRank得分。
创建一个图表,说明每个节点如何将其PageRank分数赋予图表中的其他节点。
s = {“一个”“一个”“一个”“b”“b”“c”' d '' d '' d '};t = {“b”“c”' d '' d '“一个”“b”“c”“一个”“b”};G =有向图(s, t);标签= {'A / 3''A / 3''A / 3'《b / 2》《b / 2》“c”' d / 3 '' d / 3 '' d / 3 '};p =情节(G,“布局”,'分层',“EdgeLabel”,标签);突出显示(p,[1 1 1],[2 3 4],“EdgeColor”,'G')突出显示(p,[2 2],[1 4],“EdgeColor”,“r”)突出(p, 3、2、“EdgeColor”,'M') 标题('PageRank分数在节点之间传输')
的居民
函数包含一个计算PageRank分数的选项。
创建并绘制一个包含六个节点的有向图,这些节点代表虚构的网站。
S = [1 1 2 2 3 3 3 4 5];T = [2 5 3 4 4 5 6 1 1];名称= {'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 =有向图(s t[],名称)
G =具有属性的有向图:Edges: [9x1 table] Nodes: [6x1 table]
绘图(g,“布局”,'分层',...'nodelabel',{'α',“β”,“伽马”,'三角洲',‘ε’,“ζ”})
计算这个图的PageRank中心性得分。使用跟随概率(也称为阻尼因子)0.85
.
Pr = Centrality(G,'网页排名',“FollowProbability”, 0.85)
Pr =6×10.3210 0.1706 0.1066 0.1368 0.2008 0.0643
查看每个页面的PageRank分数和学位信息。
G.Nodes.PageRank =公关;G.Nodes.InDegree =入度(G);G.Nodes.OutDegree =出度(G);G.Nodes.
ans =.6×4表名字PageRank入度出度 __________________________________ ________ ________ _________ {' 0.32098 http://www.example.com/alpha '} 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
结果表明它不仅仅是数字确定得分的页面链接,还有质量.的α
和γ
然而,两个网站的总分都是4α
链接都埃斯利昂
和bet
,这也是高度排名的。γ
只能通过一个页面链接,bet
,它在列表的中间。因此,α
得分高于γ
通过算法。
加载数据mathworks100.mat
并查看邻接矩阵,一个
.该数据是在2015年使用自动页面爬虫生成的。页面爬虫从//www.tatmou.com.
并追踪到后续网页的链接,直到邻接矩阵包含100个独立网页的连接信息。
负载mathworks100.mat间谍(A)
使用稀疏邻接矩阵创建定向图形,一个
,使用包含的URLU
节点名。
G =有向图(U)
g =带有属性的数字:边缘:[632x1表]节点:[100x1表]
使用力布局绘制图形。
绘图(g,'nodelabel',{},'nodeColor',[0.93 0.78 0],“布局”,'力量');标题(“链接到//www.tatmou.com的网站”)
计算图的PageRank分数,G
,采用200次迭代,阻尼系数为0.85
.将分数和程度信息添加到图的节点表中。
Pr = Centrality(G,'网页排名',“MaxIterations”, 200,“FollowProbability”, 0.85);G.Nodes.PageRank =公关;G.Nodes.InDegree =入度(G);G.Nodes.OutDegree =出度(G);
查看最高25个结果分数。
G.Nodes (1:25,:)
ans =.25×4表名字PageRank入度出度 ______________________________________________________________________________ ________ ________ _________ {' 14 {//www.tatmou.com} 0.044342 20 ' 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 {'//www.tatmou.com/uk' } 0.043085 20 14 {'//www.tatmou.com/au' } 0.043085 20 14 {'//www.tatmou.com/de' } 0.043085 20 14 {'//www.tatmou.com/es' } 0.043085 20 14 {'//www.tatmou.com/fr' } 0.043085 20 14 {'//www.tatmou.com/in' } 0.043085 20 14 {'//www.tatmou.com/it' } 0.043085 20 14 {'//www.tatmou.com/nl' } 0.043085 20 14 {'//www.tatmou.com/se' } 0.043085 20 14 {'//www.tatmou.com/index.html%3Fnocookie%3Dtrue' } 0.0015 0 1 {'//www.tatmou.com/company/aboutus/policies_statements/patents.html'} 0.007714 6 6 ⋮
提取并绘制包含所有得分大于的节点的子图0.005.
.根据其PageRank分数彩色图形节点。
h =子图(g,find(g.nodes.pagerank> 0005));情节(H,'nodelabel',{},“NodeCData”H.Nodes.PageRank,“布局”,'力量');标题(“链接到//www.tatmou.com的网站”)彩色栏
顶级网站的PageRank分数都非常相似,使得随机网络冲浪者大约有4.5%的机会降落在每页上。这一小组高度连接的页面在图中形成了一个集团。连接到这个中央集团是几个较小的派系,它们在自己之间高度相连。
致莫尔,C.与MATLAB实验.第7章:谷歌PageRank.Mathworks,Inc。,2011年。