PageRank
Brin, S. and Page, L. 1998. The anatomy of a large-scale hypertextual
Web search engine. In Proceedings of the Seventh international
Conference on World Wide Web (WWW-7)
PageRank算法是Web超链接结构分析中最成功的代表之一。该算法由Stanford大学的Brin和Page提出，是评价网页权威性的一种重要工具。搜索引擎Google、Yahoo、Baidu都是利用该算法和anchor text标记、词频统计等因素相结合的方法对检索出的大量结果进行相关度排序，将最权威的网页尽量排在前面。
1)PageRank基本原理
传统情报检索理论中的引文分析方法是确定学术文献权威性的重要方法之一,即根据引文的数量来确定文献的权威性。PageRank 的发明者对网络超链接结构和文献引文机制的相似性进行了研究,把引文分析思想借鉴到网络文档重要性的计算中来,利用网络自身的超链接结构给所有的网页确定一个重要性的等级数,当从网页A 链接到网页B 时,就认为”网页A 投了网页B 一票”,增加了网页B 的重要性。最后根据网页的得票数评定其重要性,以此来帮助实现排序算法的优化,而这个重要性的量化指标就是PageRank 值。
但是网页和学术上的出版文献的差别是很大的。首先学术论文的出版发表非常的严格,而网页的出版非常自由、成本很低并缺乏控制,用一个简单的程序就可以产生大量的网页和很多链接。另外学术出版物的引文一般和文章的领域有关系,而网页的链接范围领域却很广。可见简单的链接数量计算并不能客观真实地反映网页的重要性,所以PageRank 除了考虑网页得票数(即链接) 的纯数量之外,还要分析为其投票的网页的重要性,重要的网页所投之票有助于增强其他网页的“重要性”。简单地说,PageRank 就是要从链接结构中获取网页的重要性,而网页的重要
2)PageRank的实现
PageRank在具体实现时会忽略掉Web页面上的文本和其它内容，只考虑页面间的超链接，把Web看成是一个巨大的有向图G =(V，E)，结点vÎ V代表一个Web页面，有向边(p,
q )Î E代表从结点p指向结点q的超链接，结点p的出度是指从页面p出发的超链接(outlink)的总数，而入度是指所有指向结点p的超链接(inlink)的总数。
PageRank的具体定义如下：将Web对应成有向图，设W为该有向图结点的集合，N=|W|， Fi是页面i指向的所有页面的集合，Bi是指向页面i的所有页面的集合。对每个出度为0的结点S，设FS ={有向图中全部N个结点}，则所有其他结点的Bi={B È i S}，这样可以将结点S所具有的PageRank值均匀地传递给其他所有页面。PageRank的具体迭代公式为 。
其中，参数 d是 取值0到1之间的衰减因子，因为任何一个网页的作者都认为其它的网页不如自己的重要。d通常被置为0.85。
PageRank的实现过程为：将网页的URL对应成唯一的整数，把每一个超链接用其整数ID存放到索引数据库中，经过预处理(如去除数据库中的悬摆指针)之后，设每个网页的初
始PR值为1，通过以上的递归算法计算每一个网页的PageRank值，反复进行迭代，直至结果收敛。
[此贴子已经被作者于2007-8-8 16:30:07编辑过]
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 人工智能 :: 机器学习|数据挖掘|进化计算 』 → [讨论]十大经典算法之PageRank
(订阅本版)
2007/8/8 11:47:00
新浪微博
[讨论]十大经典算法之PageRank
