PageRank,一瞬间的触动的数学之美

摘自《数学之美》

在互联网上,如果一个网页被很多其他网页所链接,说明它受到普遍的承认和信赖,那么它的排名就高。这就是PageRank的核心思想。当然Google的PageRank算法实际上要复杂得多。比如说,对来自不同网页的链接区别对待,因为那些排名高的网页的链接更可靠,于是要给这些链接以较大的权重。这就好比在现实世界中股东大会里的表决,要考虑每个股东的表决权( Voting Power),拥有20%表决权的股东和拥有1% 表决权的股东,对最后的表决结果的影响力明显不同。PageRank 算法考虑了这个因素,即网页排名高的网站贡献的链接权重大。

现在举一个例子,我们知道一个网页Y的排名应该来自于所有指向这个网页的其他网页X,2….Xx的权重之和,如下图中,Y的网页排名pagerank= 0.001 + 0.01 + 0.02 + 0.05 = 0.081。

虽然佩奇和布林不强调这个算法中谁都贡献了什么思想,但是据我了解,上述想法应该来自于佩奇。接下来的问题是X,X2,Xz,X4的权重分别是多少,如何度量。佩奇认为,应该是这些网页本身的网页排名。现在麻烦来了,计算搜索结果的网页排名过程中需要用到网页本身的排名,这不成了“先有鸡还是先有蛋”的问题了吗
破解这个怪圈的应该是布林。他把这个问题变成了一个二维矩阵相乘的问题,并用迭代的方法解决了这个问题。他们先假定所有网页的排名是相同的,并且根据这个初始值,算出各个网页的第一- 次迭代排名,然后再根据第一次迭代排名算出第二次的排名。他们两人从理论上证明了不论初始值如何选取,这种算法都能保证网页排名的估计值能收敛到排名的真实值。值得提的事, 这种算法不需要任何人工干预。

2.网页排名算法的高明之处在于它把整个互联网当作一个整体来对待。 这无意中符合了系统论的观点。相比之下,以前的信息检索大多把每一个网页当作独立的个体对待,大部分人当初只注意了网页内容和查询语句的相关性, 忽略了网页之间的关系。虽然在佩奇和布林同时代也有一此人在思考如何利用网页之间的联系来衡量网页的质量,但只是摸到一些皮毛,找到一些拼凑的办法,都没有从根本上解决问题。

Leave A Comment