7,129
个编辑
更改
跳到导航
跳到搜索
第5行：
第5行： − + − PageRank通过计算页面链接的数量和质量来粗略估计分析网站的重要性。基本假设是：更重要的页面往往更多地被其他页面引用（或称其他页面中会更多地加入通向该页面的超链接）+ + − PageRank的结果来源于一种基于图论的数学算法。它将万维网上所有的网页视作节点（node），而将超链接视作边（edge），并且考虑到了一些权威的网站，类似cnn.com或者qq.com。每个节点的权重值表示对应的页面的重要度。通向该网页的超链接称做“对该网页的投票（a vote of support）”。每个网页的权重值大小被递归地定义，依托于所有链接该页面的页面的权重值。例如，一个被很多页面的链接的页面将会拥有较高的权重值（high PageRank）。+ + + + − 自Page和Brin(Google的另外一位创始人)的原始论文以来，已经发表了许多有关PageRank的学术论文。实际上，PageRank概念可能容易受到利用。相关的研究会关注那些因受到影响而出现错误的PageRank结果，以找到一种有效地避免其PageRank被错误影响的方法（如忽略部分错误的链接）。 − PageRank算法中的点击算法是由乔恩·克莱因伯格(Jon Kleinberg)提出的。而其他的基于链接的网页排名算法有乔恩·克莱因伯格发明的HITS算法，IBM CLEVER Project，TrustRank算法以及hummingbird算法等等。 − 拉里·佩奇（Larry Page）和谢尔盖·布林（Sergey Brin）于1996年在斯坦福大学开发了PageRank，这是关于一种新型搜索引擎研究项目的一部分。赫克托·加西亚·莫利纳（Hector Garcia-Molina），斯坦福大学计算机科学教授也是谢尔盖（Sergey）的导师，提供了页面排名算法开发的背景知识。谢尔盖·布林（Sergey Brin）的想法是，可以通过“链接流行度”(Link popularity)按层次结构对Web上的信息进行排序：网页的排名越高，链接就越多。该系统是在Scott Hassan和Alan Steremberg的帮助下开发的，Page和Brin都认为他们对Google的发展至关重要。Rajeev Motwani和Terry Winograd与Page和Brin共同撰写了有关该项目的第一篇论文，描述了PageRank和Google搜索引擎的初始原型。此后不久，Page和Brin创立了Google公司，谷歌搜索为其产品。PageRank目前虽然只是决定Google搜索结果排名的众多因素之一，但仍继续为所有Google搜索提供基础。+ − + − PageRank收到引文分析(Citation analysis)研究的启发，这是20世纪50年代宾夕法尼亚大学的Eugene Garfield和Hyper Search和University of Padua的Massimo Marchiori。在PageRank被提出的同一年,Jon Kleinberg 发表了[[HITS]]的研究成果。+ − 编者注：[[HITS]]也是一种网络重要性分析的算法，按照HITS算法，用户输入关键词后，算法对返回的匹配页面计算两种值，一种是枢纽值（Hub Scores），另一种是权威值(Authority Scores),这两种值是互相依存、互相影响的。所谓枢纽值，指的是页面上所有导出链接指向页面的权威值之和。权威值是指所有导入链接所在的页面中枢纽之和。 − − PageRank是以Google创始人Larry Page的姓命名，也来源于网页（web page）中的Page，该算法于1999被提出来，用于测量网页的相对重要性（对网页进行排序）。 − 第43行：
第41行： − 万维网（World Wide Web）可以抽象成一张[[有向图]]，节点表示网页，连线p_i -> p_j表示网页p_i包含了超链接p_j(p_i指向了p_j)。对图中每个节点的重要性进行量化，则就可以对网页进行排序。PageRank提出之初就是为了对网页进行排序。+ + 第57行：
第56行： − 为了打破这个循环，佩奇和布林采用了很巧妙的思路，他们分析一个虚拟用户在互联网上的漫游过程。 他们假定：虚拟用户一旦访问了一个网页，下一步将以相同的概率访问被该网页所链接的任何一个其它网页。比如，网页p_i包含了N个超链接，那么虚拟用户访问这N个页面中的任何一个的概率就是1。那么，网页的排序就可以堪称一个虚拟用户在万维网漫游了很长时间，页面被访问的概率越大，其PR值就越高，网页排名也越靠前。+ + 第64行：
第64行： − 如图所示，每个节点初始化或者指定一个PageRank值（如PR(A)=0.4），网页A包含两个超链接，分别指向B和C（或者说A投票给B和C），0.4拆分成两份，每份0.2，所以PR(B)=0.2。A和B同时给C投票，所以PR(C)=0.2+0.2=0.4。如此，不断地迭代，最后每个节点的值都会收敛，这样就求得了所有节点的PR值。+ 第82行：
第82行： − 对于第一个问题，给等式乘以一个小于1的常数d(damping factor)，这个常数被翻译成阻尼系数，意思为任意时刻浏览者访问到某页面后继续访问下一个页面的概率；对于第二个问题，给等式加上一个常数。新的等式如下（N表示网页总数，或者节点数目，本文中该公式成为PageRank基本公式，下同）：+ 第92行：
第92行： − + + 第103行：
第104行： − 假设他们的初始PR值为1，第一次迭代后，PR(A)和PR(B)的值为：+ 第264行：
第265行： + + − 迭代次数越多，结果越准确，但花费时间也越长。出于效率考虑，在实际应用中，当PR值落在误差允许范围内（PR值跟前一次比较，如PR^'(A)-PR(A)<1.0e-6，其中1.0e-6即为浮点数在计算机的存储）就可以返回结果了。Python实现的nx.pagerank相关源代码如下：+ 第275行：
第278行： − + + + − + + 第305行：
第311行： − 如果没有给节点指定PR初始值，那么每个节点的PR初始化为1/N+ − 1/N (N为节点数目)，以图1为例，节点的PR初始值为1/11： 第365行：
第370行： − 当PR^'(A)-PR(A)<1.0e-6，即迭代后的PR值跟前一次比较差别很小时，程序的迭代将结束。代码如下：+ 第696行：
第701行： − 公式中R为特征向量（eignevector），根据公式：+ 第915行：
第920行： − 2005年，在巴基斯坦进行的一项试点研究中，“结构性深层民主（Structural Deep Democracy，SD2）”被用于一个名为“Contact Youth”的可持续农业组织的领导层的选举。SD2使用PageRank来处理传递式代理投票，另外还有每个投票者至少要委托两个初始代理的约束，所有选民都是代理候选人。可以在SD2的基础上构建更复杂的变体，例如添加专家代理和针对特定问题的直接投票，但是作为基础的总体系统，SD2要求总是使用通用代理。+
无编辑摘要
[[File:Pagerank show.png|thumb|400x400px|图片注释：在简单的网络中，使用百分比表示PageRank(Google使用对数标尺)。尽管到C的链接较少，但页面C的PageRank高于页面E。到C的一个链接来自重要页面，因此具有很高的价值。如果一个人从随机页面开始浏览，有85％的可能性从他当前访问的页面中选择一个随机链接，而有15％的可能性从整个网络中随机跳转到某个页面，则他们将到达页面E占8.1％的时间（即跳到任意页面的可能性为15％，对应的阻尼系数为85％）。如果没有阻尼，则所有浏览网站的人最终都将停留在A，B或C页上，而所有其他页面的PageRank均为0。在存在阻尼的情况下，即使页面A没有自己的传出链接，它也可以有效链接到网络中的所有页面。]]
[[File:Pagerank show.png|thumb|400x400px|图片注释：在简单的网络中，使用百分比表示PageRank(Google使用对数标尺)。尽管到C的链接较少，但页面C的PageRank高于页面E。到C的一个链接来自重要页面，因此具有很高的价值。如果一个人从随机页面开始浏览，有85％的可能性从他当前访问的页面中选择一个随机链接，而有15％的可能性从整个网络中随机跳转到某个页面，则他们将到达页面E占8.1％的时间（即跳到任意页面的可能性为15％，对应的阻尼系数为85％）。如果没有阻尼，则所有浏览网站的人最终都将停留在A，B或C页上，而所有其他页面的PageRank均为0。在存在阻尼的情况下，即使页面A没有自己的传出链接，它也可以有效链接到网络中的所有页面。]]
PageRank(PR)算法，又称为网页排名算法， Google左侧排算法。Page Rank得名为谷歌创始人之一拉里佩奇(Larry Page).PageRank是一种衡量网站页面重要性的方法。根据谷歌的说法：
PageRank(PR)算法，又称为网页排名算法，Google左侧排算法，由谷歌创始人之一的'''拉里·佩奇 Larry Page''命名。PageRank是一种衡量网站页面重要性的方法。根据谷歌的说法：
PageRank通过计算页面链接的数量和质量来粗略估计分析网站的重要性。基本假设是：更重要的页面往往更多地被其他页面引用（或称其他页面中会更多地加入通向该页面的超链接）。
目前该算法不再是谷歌用于排序搜索结果的唯一算法，但它是谷歌公司使用的第一个排序搜索算算法，也是最著名的算法。截止至2019年9月24日，PageRank和所有的相关专利已过期。
目前该算法不再是谷歌用于排序搜索结果的唯一算法，但它是谷歌公司使用的第一个排序搜索算算法，也是最著名的算法。截止至2019年9月24日，PageRank和所有的相关专利已过期。
==描述==
==描述==
Page Rank是一种链接分析算法，它通过对超链接集合（如万维网）中的元素实现数值权重赋值，实现“衡量集合范围内某一元素的相关重要性”的目的。该算法可以应用于带有相互引用或者引用关系的任何实体集合。算法赋值给任何给定元素E的数值权重称为E的PageRank，并且用PR(E) 表示。
Page Rank是一种链接分析算法，它通过对超链接集合（如万维网）中的元素实现数值权重赋值，实现“衡量集合范围内某一元素的相关重要性”的目的。该算法可以应用于带有相互引用或者引用关系的任何实体集合。算法赋值给任何给定元素E的数值权重称为E的PageRank，并且用PR(E) 表示。
PageRank的结果来源于一种基于'''图论'''的数学算法。它将万维网上所有的网页视作'''节点 node'''，而将超链接视作'''边 edge'''，并且考虑到了一些权威的网站，类似cnn.com或者qq.com。每个节点的权重值表示对应的页面的重要度。通向该网页的超链接称做“对该网页的投票 a vote of support”。每个网页的权重值大小被递归地定义，依托于所有链接该页面的页面的权重值。例如，一个被很多页面的链接的页面将会拥有较高的权重值。
自Page和谢尔盖·布林 Sergey Brin(Google的另外一位创始人)的原始论文以来，已经发表了许多有关PageRank的学术论文。实际上，PageRank概念可能容易受到利用。相关的研究会关注那些因受到影响而出现错误的PageRank结果，以找到一种有效地避免其PageRank被错误影响的方法（如忽略部分错误的链接）。
PageRank算法中的点击算法是由乔恩·克莱因伯格 Jon Kleinberg提出的。而其他的基于链接的网页排名算法有Kleinberg发明的HITS算法，IBM CLEVER Project，TrustRank算法以及hummingbird算法等等。
==历史==
==历史==
Page和Brin于1996年在斯坦福大学开发了PageRank，这是关于一种新型搜索引擎研究项目的一部分。赫克托·加西亚·莫利纳 Hector Garcia-Molina，斯坦福大学计算机科学教授,也是Brin的导师，提供了页面排名算法开发的背景知识。Brin的想法是，可以通过“链接流行度 Link popularity”按层次结构对Web上的信息进行排序：网页的排名越高，链接就越多。该系统是在Scott Hassan和Alan Steremberg的帮助下开发的，Page和Brin都认为他们对Google的发展至关重要。Rajeev Motwani和Terry Winograd与Page和Brin共同撰写了有关该项目的第一篇论文，描述了PageRank和Google搜索引擎的初始原型。此后不久，Page和Brin创立了Google公司，谷歌搜索为其产品。PageRank目前虽然只是决定Google搜索结果排名的众多因素之一，但仍继续为所有Google搜索提供基础。
"PageRank"这个名字里面的"Page"来源于拉里佩奇(Larry Page)，也源于网页(Web Page)一次。但是这项专利为斯坦福大学所有，作为交换，斯坦福大学拥有谷歌的180万股的股份。
"PageRank"这个名字里面的"Page"来源于Larry Page，也源于网页 Web Page。但是这项专利为斯坦福大学所有，作为交换，斯坦福大学拥有谷歌的180万股的股份。
PageRank收到'''引文分析 Citation analysis'''研究的启发，这是20世纪50年代宾夕法尼亚大学的Eugene Garfield和Hyper Search和University of Padua的Massimo Marchiori。在PageRank被提出的同一年,Jon Kleinberg 发表了[[HITS]]的研究成果。[[HITS]]也是一种网络重要性分析的算法，按照HITS算法，用户输入关键词后，算法对返回的匹配页面计算两种值，一种是'''枢纽值 Hub Scores'''，另一种是'''权威值 Authority Scores''',这两种值是互相依存、互相影响的。所谓枢纽值，指的是页面上所有导出链接指向页面的权威值之和。权威值是指所有导入链接所在的页面中枢纽之和。
==算法==
==算法==
===PageRank的基本思想===
===PageRank的基本思想===
PageRank算法通过输出概率分布来体现某人随机地点击某个链接的概率。PageRank值（PR）可以在任何规模的文件（document）集合中计算得出，而每个链接都指向该集合中的某个特定文件。相关研究论文指出，在初次计算前，总概率将被均分到每个文件上，使得集合中的每个文件被访问的概率都是相同的。接下来在重复多次的计算（又称为“迭代”）中，算法将根据集合的实际情况不断调整PR值，使得其越来越接近最真实的理论值。
PageRank算法通过输出概率分布来体现某人随机地点击某个链接的概率。PageRank值（PR）可以在任何规模的文件（document）集合中计算得出，而每个链接都指向该集合中的某个特定文件。相关研究论文指出，在初次计算前，总概率将被均分到每个文件上，使得集合中的每个文件被访问的概率都是相同的。接下来在重复多次的计算（又称为“迭代”）中，算法将根据集合的实际情况不断调整PR值，使得其越来越接近最真实的理论值。
万维网 World Wide Web可以抽象成一张[[有向图]]，节点表示网页，连线<math>p_i -> p_j</math>表示网页<math>p_i</math>包含了超链接<math>p_j(p_i指向了p_j)</math>。对图中每个节点的重要性进行量化，则就可以对网页进行排序。PageRank提出之初就是为了对网页进行排序。
搜索引擎的工作原理可以简化为：输入关键词，返回与该关键词相关的网页（一个集合，相当于得到一张子图），在该子图上计算每个节点的PageRank值，PageRank值高的网页排在前面，低的就排在后面。
搜索引擎的工作原理可以简化为：输入关键词，返回与该关键词相关的网页（一个集合，相当于得到一张子图），在该子图上计算每个节点的PageRank值，PageRank值高的网页排在前面，低的就排在后面。
===计算PageRank===
===计算PageRank===
其他网页的PR值很可能是依赖于<math>p_{i}</math>。这就陷入了一个循环，要想知道<math>p_{i}</math>的PR值，就得知道链向<math>p_{i}</math>所有网页的PR值，而要知道其他网页的PR值，又得先知道<math>p_{i}</math>的PR值。
其他网页的PR值很可能是依赖于<math>p_{i}</math>。这就陷入了一个循环，要想知道<math>p_{i}</math>的PR值，就得知道链向<math>p_{i}</math>所有网页的PR值，而要知道其他网页的PR值，又得先知道<math>p_{i}</math>的PR值。
为了打破这个循环，Page和Brin采用了很巧妙的思路，他们分析一个虚拟用户在互联网上的漫游过程。 他们假定：虚拟用户一旦访问了一个网页，下一步将以相同的概率访问被该网页所链接的任何一个其它网页。比如，网页<math> p_i </math>包含了<math> N </math>个超链接，那么虚拟用户访问这<math> N </math>个页面中的任何一个的概率就是1。那么，网页的排序就可以堪称一个虚拟用户在万维网漫游了很长时间，页面被访问的概率越大，其PR值就越高，网页排名也越靠前。
===简化的PageRank的例子===
===简化的PageRank的例子===
如图所示，每个节点初始化或者指定一个PageRank值（如<math>PR(A)=0.4</math>），网页A包含两个超链接，分别指向B和C（或者说A投票给B和C），0.4拆分成两份，每份0.2，所以<math> PR(B)=0.2 </math>。A和B同时给C投票，所以<math> PR(C)=0.2+0.2=0.4 </math>。如此，不断地迭代，最后每个节点的值都会收敛，这样就求得了所有节点的PR值。
每个页面将其当前的PageRank值平均分配到本页面所有出链上，一个页面将所有入链的PR值累加起来就构成了该页面新的PR值。如此迭代下去，最后得到一个稳定值。用数学公式表达，如下：
每个页面将其当前的PageRank值平均分配到本页面所有出链上，一个页面将所有入链的PR值累加起来就构成了该页面新的PR值。如此迭代下去，最后得到一个稳定值。用数学公式表达，如下：
* 对于没有blacklinks (inedges)的网页，即没人给她投票，其PageRank永远等于0。
* 对于没有blacklinks (inedges)的网页，即没人给她投票，其PageRank永远等于0。
对于第一个问题，给等式乘以一个小于1的常数<math> d </math>(damping factor)，这个常数被翻译成阻尼系数，意思为任意时刻浏览者访问到某页面后继续访问下一个页面的概率；对于第二个问题，给等式加上一个常数。新的等式如下（<math> N <math>表示网页总数，或者节点数目，本文中该公式成为PageRank基本公式，下同）：
* <math>B(p_{i}</math>：链接到网页<math>p_{i}</math>的（a set of pages link to <math>p_{i}</math>）。
* <math>B(p_{i}</math>：链接到网页<math>p_{i}</math>的（a set of pages link to <math>p_{i}</math>）。
* L(p_{j})：从<math>p_{j}</math>链出去的网页数目（the number of outbound links)。
* <math>L(p_{j})</math>：从<math>p_{j}</math>链出去的网页数目（the number of outbound links)。
这样子，所有的节点的PR值加起来就确保为1了。
这样子，所有的节点的PR值加起来就确保为1了。
===简单的实例===
===简单的实例===
假设他们的初始<math> PR </math>值为1，第一次迭代后，<math> PR(A) </math>和<math> PR(B) </math>的值为：
<source lang="Python">
<source lang="Python">
main()
main()
</syntaxhighlight>
</syntaxhighlight>
===迭代次数===
===迭代次数===
迭代次数越多，结果越准确，但花费时间也越长。出于效率考虑，在实际应用中，当PR值落在误差允许范围内PR值跟前一次比较，如<math> PR^'(A)-PR(A)<1.0e-6 </math>，其中<math> 1.0e-6 </math>即为浮点数在计算机的存储）就可以返回结果了。Python实现的nx.pagerank相关源代码如下：
<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
# check convergence, l1 norm
# check convergence, l1 norm
在超大型的网络上，会有更加复杂的计算方法，比如分布式计算。
在超大型的网络上，会有更加复杂的计算方法，比如分布式计算。
===PR初始值===
===PR 初始值===
不管节点PR初始值怎么设置，最后节点的PR值都一样，但收敛不一样。可以修改上面Python代码的PR初始值，运行代码，体验不同的初始值带来的不同效果。NetworkX的pagerank实现是将PR值初始化为1/N。
不管节点PR初始值怎么设置，最后节点的PR值都一样，但收敛不一样。可以修改上面Python代码的PR初始值，运行代码，体验不同的初始值带来的不同效果。NetworkX的pagerank实现是将PR值初始化为1/N。
===阻尼系数===
===阻尼系数===
Damping factor被翻译为阻尼系数，公式中记为d，和PR初始值一样，d的取值也会影响PageRank算法的效率。在佩奇和布林的论文中，d通常被设置为0.85。
Damping factor被翻译为阻尼系数，公式中记为<math> d </math>，和 PR 初始值一样，d的取值也会影响PageRank算法的效率。在佩奇和布林的论文中，d通常被设置为0.85。
===PageRank的计算方法===
===PageRank的计算方法===
=====初始化节点PR值=====
=====初始化节点PR值=====
如果没有给节点指定PR初始值，那么每个节点的PR初始化为<math> 1/N </math>(<math> N </math>为节点数目)，以图1为例，节点的PR初始值为<math>1/11</math>：
当<math> PR^'(A)-PR(A)<1.0e-6 </math>，即迭代后的PR值跟前一次比较差别很小时，程序的迭代将结束。代码如下：
<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
====求解====
====求解====
公式中<math> R </math>为[[特征向量 eignevector]]，根据公式：
===其他===
===其他===
2005年，在巴基斯坦进行的一项试点研究中，“结构性深层民主 Structural Deep Democracy(SD2）”被用于一个名为“Contact Youth”的可持续农业组织的领导层的选举。SD2使用PageRank来处理传递式代理投票，另外还有每个投票者至少要委托两个初始代理的约束，所有选民都是代理候选人。可以在SD2的基础上构建更复杂的变体，例如添加专家代理和针对特定问题的直接投票，但是作为基础的总体系统，SD2要求总是使用通用代理。
在体育运动中，PageRank 算法被用来对球队或者运动员的表现进行排名: 美国国家橄榄球联盟(NFL)的球队; 个人足球运动员; 钻石联盟的运动员。
在体育运动中，PageRank 算法被用来对球队或者运动员的表现进行排名: 美国国家橄榄球联盟(NFL)的球队; 个人足球运动员; 钻石联盟的运动员。
Pagerank 被用于对空间或街道进行排序，以预测有多少人(行人或车辆)来到各个空间或街道。 在词汇语义学中，它被用来进行词义消歧，语义相似度，以及根据词网同义词具有给定的语义属性(如积极性或消极性)的强度自动对它们进行排序。
Pagerank 被用于对空间或街道进行排序，以预测有多少人(行人或车辆)来到各个空间或街道。 在词汇语义学中，它被用来进行词义消歧，语义相似度，以及根据词网同义词具有给定的语义属性(如积极性或消极性)的强度自动对它们进行排序。