加载中…
个人资料
Yode
Yode
  • 博客等级:
  • 博客积分:0
  • 博客访问:594,545
  • 关注人气:250
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

page rank和它的原型

(2007-04-06 15:06:35)
分类: 数学之美

昨天在Google黑板报上读到了一篇介绍Page Rank的文章, 最让我感兴趣的是它的数学模型。Google 的创始人之一拉里"佩奇在谈到怎么想到网页排名算法时说:“当时我们觉得整个互联网就像一张大的图 (Graph),每个网站就像一个节点,而每个网页的链接就像一个弧。我想,互联网可以用一个图或者矩阵描述,我也许可以用这个发现做个博士论文。”

事实上,“Google 的两个创始人拉里"佩奇 (Larry Page )和谢尔盖"布林 (Sergey Brin) 把这个问题变成了一个二维矩阵相乘的问题,并且用迭代的方法解决了这个问题。”至于他们是如何把这个问题转化成矩阵相乘的,文中并没有详细介绍。我google了一下,发现了这两人在斯坦福大学的博士论文,文中介绍了PageRank的数学定义:

We assume page A has pages T1...Tn which point to it (i.e., are citations). The parameter d is a damping factor which can be set between 0 and 1. We usually set d to 0.85. There are more details about d in the next section. Also C(A) is defined as the number of links going out of page A. The PageRank of a page A is given as follows:

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

Note that the PageRanks form a probability distribution over web pages, so the sum of all web pages' PageRanks will be one.

假 设指向页面A的页面有T1...Tn共n个页面,C(Ti)指的是页面Ti指向外界的链接数,d是一个常数。PR(Ti)/C(Ti)指的是页面Ti本身 的PageRank分配给A的一份。(1-d)只是为了让所有网页的PageRank服从概率分布。

因 为一开始所有的页面并没有PageRank,所以这个公式需要迭代多次才能使PageRank值稳定下来。黑板报的这篇文章提到这点时说到:“他们先假定 所有网页的排名是相同的,并且根据这个初始值,算出各个网页的第一次迭代排名,然后再根据第一次迭代排名算出第二次的排名。他们两人从理论上证明了不论初 始值如何选取,这种算法都保证了网页排名的估计值能收敛到他们的真实值。”

好了公式有了,但好像还是看不出和矩阵有什么关系。实际上,每一 个网页都对应于一个二维矩阵的第i行和第i列,如果网页j指向网页i,并且网页i是网页j的n个链接之一,则矩阵的第i行第j列的值就为1/n,否则就为 0。这也就是黑板报的文章提到的“如果我们假定有十亿个网页,那么这个矩阵就有一百亿亿个元素。”当然这个矩阵中大部分元素都为0,所以“拉里和谢尔盖两 人利用稀疏矩阵计算的技巧,大大的简化了计算量,并实现了这个网页排名算法。“
   矩阵建立之后,PageRank值其实就是这个矩阵的主特征向量当时看到这里我就纳闷,既然是特征向量为什么不直接计算反而要迭代呢,后来一想怎么求10亿*10亿的矩阵的特征向量,可能还是迭代计算简单方便。
   不 管具体的实现怎样,这个算法真正的突破在于文中所说的,“网页排名的高明之处在于它把整个互联网当作了一个整体对待。它无意识中符合了系统论的观点。相比 之下,以前的信息检索大多把每一个网页当作独立的个体对待,很多人当初只注意了网页内容和查询语句的相关性,忽略了网页之间的关系。”两位创始人的数学建 模能力和想象力在这里发挥了关键作用。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有