更改

PageRank算法 (查看源代码)

2020年4月24日 (五) 19:26的版本

添加25字节、 2020年4月24日 (五) 19:26

无编辑摘要

第5行：第5行：

[[File:PageRanks-Example.jpg|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左侧排算法，由谷歌创始人之一的'''拉里·佩奇 Larry Page''命名。PageRank是一种衡量网站页面重要性的方法。根据谷歌的说法：

+

PageRank(PR)算法，又称为网页排名算法，Google左侧排算法，由谷歌创始人之一的'''拉里·佩奇 Larry Page'''命名。PageRank是一种衡量网站页面重要性的方法。根据谷歌的说法：

PageRank通过计算页面链接的数量和质量来粗略估计分析网站的重要性。基本假设是：更重要的页面往往更多地被其他页面引用（或称其他页面中会更多地加入通向该页面的超链接）。

第13行：第13行：

==描述==

−

Page Rank是一种链接分析算法，它通过对超链接集合（如万维网）中的元素实现数值权重赋值，实现“衡量集合范围内某一元素的相关重要性”的目的。该算法可以应用于带有相互引用或者引用关系的任何实体集合。算法赋值给任何给定元素E的数值权重称为E的PageRank，并且用PR(E) 表示。

+

PageRank是一种链接分析算法，它通过对超链接集合（如万维网）中的元素实现数值权重赋值，实现“衡量集合范围内某一元素的相关重要性”的目的。该算法可以应用于带有相互引用或者引用关系的任何实体集合。算法赋值给任何给定元素E的数值权重称为E的PageRank，并且用PR(E) 表示。

+

PageRank的结果来源于一种基于'''图论'''的数学算法。它将万维网上所有的网页视作'''节点 node'''，而将超链接视作'''边 edge'''，并且考虑到了一些权威的网站，类似cnn.com或者qq.com。每个节点的权重值表示对应的页面的重要度。通向该网页的超链接称做“对该网页的投票 a vote of support”。每个网页的权重值大小被递归地定义，依托于所有链接该页面的页面的权重值。例如，一个被很多页面的链接的页面将会拥有较高的权重值。

第23行：第25行：

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万股的股份。

第45行：第48行：

搜索引擎的工作原理可以简化为：输入关键词，返回与该关键词相关的网页（一个集合，相当于得到一张子图），在该子图上计算每个节点的PageRank值，PageRank值高的网页排在前面，低的就排在后面。

+

===计算PageRank===

第264行：第268行：

main()

</syntaxhighlight>

+

===迭代次数===

第275行：第280行：

在超大型的网络上，会有更加复杂的计算方法，比如分布式计算。

+

===PR 初始值===

第320行：第326行：

node_and_pr = dict.fromkeys(G, 1.0 / N)

</syntaxhighlight>

+

=====创建随机图 Stochastic graph=====

第603行：第610行：

[1]]

</syntaxhighlight>

+

====邻接函数 Adjacency functionc====

第632行：第640行：

事实上，<math> M </math>是一个转移矩阵Transition matrix（也叫概率矩阵Probability matrix，马尔可夫矩阵Markov matrix）。因此，PageRank是Eigenvector centrality的一个变体。

+

====矩阵M====

第749行：第758行：

</syntaxhighlight>

−

~~得到R需要normalized，所有节点的PR加起来才能等于1。~~

+

得到R需要归一化，所有节点的PR加起来才能等于1。

第866行：第875行：

main()

</syntaxhighlight>

+

==演化==

第888行：第898行：

也就是说，当且仅当该图是规则的，即每个顶点具有相同的度数时，无向图的PageRank等于度数分布矢量。

+

===针对PageRank的分布式算法===

Sarma 等人描述了两种基于随机游走的分布式算法，用于计算网络中节点的 PageRank。一种算法<math>O(\log n/\epsilon)</math> 在任何图（有向图或无向图）上以高概率四舍五入，其中<math>n</math>是网络规模，<math>\epsilon</math>是重置概率（<math> 1- \epsilon</math>为PageRank计算中使用的阻尼因子）。他们还提出了一种更快的算法<math> O(\sqrt{\log n}/\epsilon)</math>，在无向图中四舍五入。在这两种算法中，每个节点每轮处理并发送网络位数n中多对数的位。

+

===谷歌工具栏===

Google工具栏具有PageRank功能，该功能可将访问页面的PageRank显示为介于0到10之间的整数。最受欢迎的网站显示的PageRank为10，浏览可能性最小的页面的PageRank为0。Google并未披露工具栏确定网页PageRank值的具体方法，该值仅被视为网站价值的粗略指示。2016年3月，Google宣布将不再支持此功能。

+

===搜索引擎结果页(SERP)===

第902行：第915行：

网页在Google SERP上某个关键字的位置取决于相关性和声誉，也称为权威性和受欢迎度。PageRank是Google评估其网页信誉的一种指示：它是非关键字特定的。Google使用网页和网站权限的组合来确定竞争关键字的网页的总体权限。网站首页的PageRank是Google为网站授权提供的最佳指示。

在将Google地方信息引入主流有机SERP之后，除PageRank之外，还有许多其他因素会影响企业在本地业务结果中的排名。

+

===操纵PageRank===

为了优化搜索引擎的结果，一些公司提供向网站管理员出售高PageRank的链接。由于较高PR页面的链接被认为更有价值，因此它们往往更昂贵。在质量和相关站点的内容页面上购买链接广告以提高访问量并提高网站站长的链接流行度成为一种有效可行的营销策略。因此，Google公司有网站出售高PageRank的链接时，该链接将被拉入黑名单（在计算其他页面的PageRanks时将被忽略）。

+

==社会网络属性==

第912行：第927行：

Matteo Pasquinelli认为，PageRank具有社会成分的基础在于注意力经济这一概念。通过注意力节约，可以将价值放在那些能吸引更多人的注意力的产品上，而与随后页面上的结果相比，PageRank顶部的结果获得更多的关注（即更高的注意力）。因此，具有较高PageRank的结果有更大的概率进入人类意识，这会进一步的影响浏览该网页的人的行为。高PageRank网页具有更高的潜力来吸引用户的注意力。因此，这些网页可以获得更多的流量，这也能够让用户为他们的业务进行更多的付费。这些网页的PageRank允许它们被信任，并且能够将这种信任增加更多的业务。

+

==PageRank的其他用途==

第925行：第941行：

一个版本的 PageRank 最近被提议用来取代传统的 ISI 影响因子，并在 Eigenfactor 和 SCImago 实施。与仅仅计算引文总数不同，每条引文的“重要性”是以 PageRank 的方式确定的。

在神经科学中，已经发现神经网络中神经元的PageRank 与它的相对放电速率相关。

+

===互联网===

第932行：第949行：

一个网络爬虫可以使用 PageRank 作为它用来确定在网络爬行过程中访问哪个 URL 的重要度量之一。创建 Google 时使用的早期工作论文之一是高效地搜索 URL 排序，讨论了一系列不同重要性度量标准的使用，以确定 Google 搜索网站的深度和程度。网页排名是众多重要性指标中的一个，尽管还有其他一些指标，比如一个 URL 的入站和出站链接的数量，以及站点的根目录到 URL 的距离。

Pagerank 也可以作为一种方法来衡量像 Blogosphere 这样的社区对整个 Web 本身的影响。因此，这种方法使用 PageRank 来衡量注意力的分布情况，这种分布情况反映了[[无标度网络]]模式。

+

===其他===

第938行：第956行：

在体育运动中，PageRank 算法被用来对球队或者运动员的表现进行排名: 美国国家橄榄球联盟(NFL)的球队; 个人足球运动员; 钻石联盟的运动员。

Pagerank 被用于对空间或街道进行排序，以预测有多少人(行人或车辆)来到各个空间或街道。在词汇语义学中，它被用来进行词义消歧，语义相似度，以及根据词网同义词具有给定的语义属性(如积极性或消极性)的强度自动对它们进行排序。

+

==参考==

第954行：第973行：

* https://www.cs.princeton.edu/~chazelle/courses/BIB/pagerank.htm

+

==编者推荐==

第961行：第982行： −

+

</br>

----

本中文词条由[[用户:ZQ|ZQ]]参与编译，[[用户:薄荷|薄荷]]欢迎在讨论页面留言。

'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''

薄荷

7,129

个编辑