Page Rank和它的数学模型 - 无线搜索技术 - 无线搜索论坛 自由！开放！专门研究与交流无线搜索(移动搜索/手机搜索/WAP搜索/短信搜索/语音搜索/手机客户端软件搜索/实名/寻址) - Powered by Discuz!

注册 登录 搜索 标签 帮助
无线搜索论坛 无线搜索技术 Page Rank和它的数学模型
上一主题 下一主题

发新话题 发布投票 发布商品 发布悬赏 发布活动 发布辩论 发布视频
打印 Page Rank和它的数学模型
NapolLee


少校
个人空间 发短消息 加为好友 当前离线
1#大 中小 发表于 2008-1-19 20:52 只看该作者
Page Rank和它的数学模型
作者：风雨骑士　来源：CSDN博客　 酷勤网收集　2007-12-04
摘要酷勤网　　网页排名的高明之处在于它把整个互联网当作了一个整体对待。它无意识中符合了系统论的观点。相比之下，以前的信息检索大多把每一个网页当作独立的个体对待，很多人当初只注意了网页内容和查询语句的相关性，忽略了网页之间的关系。
昨天在Google黑板报上读到了一篇介绍Page Rank的文章，最让我感兴趣的是它的数学模型。Google 的创始人之一拉里佩奇在谈到怎么想到网页排名算法时说：“当时我们觉得整个互联网就像一张大的图 （Graph），每个网站就像一个节点，而每个网页的链接就像一个弧。我想，互联网可以用一个图或者矩阵描述，我也许可以用这个发现做个博士论文。”
事实上，“Google 的两个创始人拉里佩奇 （Larry Page ）和谢尔盖布林 (Sergey Brin) 把这个问题变成了一个二维矩阵相乘的问题，并且用迭代的方法解决了这个问题。”至于他们是如何把这个问题转化成矩阵相乘的，文中并没有详细介绍。我google了一下，发现了这两人在斯坦福大学的博士论文，文中介绍了PageRank的数学定义：
We assume page A has pages T1Tn 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的页面有T1Tn共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值其实就是这个矩阵的主特征向量。具体的例子可以参考这篇PDF文档。当时看到这里我就纳闷，既然是特征向量为什么不直接计算反而要迭代呢，后来一想怎么求10亿*10亿的矩阵的特征向量，可能还是迭代计算简单方便。
不管具体的实现怎样，这个算法真正的突破在于文中所说的，“网页排名的高明之处在于它把整个互联网当作了一个整体对待。它无意识中符合了系统论的观点。相比之下，以前的信息检索大多把每一个网页当作独立的个体对待，很多人当初只注意了网页内容和查询语句的相关性，忽略了网页之间的关系。”两位创始人的数学建模能力和想象力在这里发挥了关键作用。
回想前些天，孟岩老师贴了两篇文章探讨数学的重要性：数学与算法随想和技术图书与数学教育 。大家还在对数学的重要性争论不休，PageRank这个例子相信很有说服力。对于数学的作用，我很喜欢这篇文章中的比喻：一个运动员总要进行跑步和负重训练以增强体质磨练心智；和运动员一样，计算机专业的学生也应该通过数学思维的磨练以增强从细节中抽象的能力以及解决问题的创造力。
来自：blog.csdn.net/rideronstorm/archive/2006/02/28/612151.aspx

UID793 帖子638 精华9 积分3906 财富12478 贡献1264 威望13 阅读权限10 性别男 来自广东 在线时间126 小时 注册时间2007-10-6 最后登录2008-10-4
查看详细资料
TOP efgh917


下士
个人空间 发短消息 加为好友 当前离线
2#大 中小 发表于 2008-12-26 05:26 只看该作者
星期三了，上班聊天
星期三了，上班聊天鲜花

UID2120 帖子50 精华 积分151 财富510 贡献50 威望0 阅读权限4 性别女 在线时间0 小时 注册时间2008-12-9 最后登录2008-12-26
查看个人网站
查看详细资料
TOP 日日思君


新兵
个人空间 发短消息 加为好友 当前离线
3#大 中小 发表于 2008-12-26 15:28 只看该作者
不错不错,顶
楼主说的,我很认同!!!
|///
- - //
( @ @ )
┏━━━━━━━━oOOo-(_)-oOOo━┓
┃网海茫茫,认识你是我们的福份； ┃
┃网语缠绵,那是我们注定的缘份。 ┃
┃ Oooo ┃
┗━━━━━━━━ oooO━-( )━┛
( ) ) /
( (_/
_)美国留学
澳大利亚留学
留学澳大利亚
澳洲留学
留学澳洲
韩国留学

UID2188 帖子6 精华 积分19 财富70 贡献6 威望0 阅读权限1 性别男 在线时间0 小时 注册时间2008-12-22 最后登录2009-1-2
查看个人网站
查看详细资料
TOP passting169


老兵
个人空间 发短消息 加为好友 当前离线
4#大 中小 发表于 2009-1-9 07:19 只看该作者
减肥常识
我想瘦身 ,那里有合适的瘦身常识 和减肥常识

UID2149 帖子14 精华 积分43 财富150 贡献14 威望0 阅读权限2 性别男 在线时间0 小时 注册时间2008-12-16 最后登录2009-1-9
查看详细资料
TOP 上一主题 下一主题

控制面板首页 编辑个人资料 积分记录 公众用户组 升级个人空间
当前时区 GMT+8, 现在时间是 2009-1-9 17:20 粤ICP备07021541号
清除 Cookies - 联系我们 - 无线搜索论坛 - Archiver - WAP - TOP

Powered by Discuz! 6.0.0 (C) 2001-2007 Comsenz Inc.
内页
内页 内页

直接浏览

提示:以上根据您的指令使用Timewe浏览服务访问的www.wxss.org网站,其内容、服务或立场跟Timewe无关 ...
欢迎举报存在违法、不良信息的网站，净化网络环境

Wap推荐: 极品游戏大作