PageRank背景.docx

文档介绍：摘要
PageRank是衡量网络节点重要性的指标之一,个性化PageRank 是普通PageRank 的推广形式。本文首先叙述了PageRank算法的原理与基本思想,说明了个性化PageRank算法产生的背景,总结了当今个性化PageRank算法的研究现况和发展趋势,对于各种个性化PageRank算法作出了分类并且进行了详细的分析和比较,最后列举了个性化PageRank算法在实际中的应用。
Abstract
PageRank is one of the indicators to measure the importance work nodes, personalized PageRank is an extension of ordinary PageRank. First, in this paper, we described the principle and basic idea of PageRank algorithm. Then, explained the background of personalized PageRank algorithm. This paper summarized the current research status and development trend of personalized PageRank algorithm. For a variety of personalized PageRank algorithm to make a classification and a detailed analysis parison. Finally, the application of personalized PageRank algorithm in practice was listed.
PageRank算法及个性化PageRank算法
PageRank算法
PageRank是Google创始人拉里·佩奇和谢尔盖·布林于1997年构建早期的搜索系统原型时提出的链接分析算法,自从Google在商业上获得空前的成功后,该算法也成为其他搜索引擎和学术界十分关注的计算模型。目前很多重要的链接分析算法都是在PageRank算法基础上衍生出来的。PageRank是Google用于用来标识网页的等级/重要性的一种方法,是Google用来衡量一个网站的好坏的唯一标准。在揉合了诸如Title标识和Keywords标识等所有其它因素之后,Google通过PageRank来调整结果,使那些更具“等级/重要性”的网页在搜索结果中另网站排名获得提升,从而提高搜索结果的相关性和质量。其主要思想如下:
如果一个页面被多次引用,则这个页面很可能是重要的;
如果一个页面尽管未被多次引用,但都被一个重要的页面引用,则这个页面很可能是重要的;
一个页面的重要性被均分,并传递到它所引用的页面。
衡量每个页面的PageRank分数排名如公式1所示的算法:
PRpi=1-d+d*j=1nPR(pj)L(pj)
公式1
其中L(pj)是pj链出页面的数量,PR值是每个网页的重要程度,而d是阻尼因子()。
初始时,对每个网页赋值为:PRv=1n。然后用公式1进行迭代,直至收敛并趋于稳定。容易知道,PR值越高说明该网页越受欢迎(越重要)。例如:一个PR值为1的网站表明这个网站不太具有流行度,而PR值为7到10则表明这个网站非常受欢迎(或者说极其重要)。一般PR值达到4,就算是一个不错的网站了。Google把自己的网站的PR值定到10,这说明Google这个网站是非常受欢迎的,也可以说这个网站非常重要。
Matthew Richardson 与 Pedro Domingos 于2001将其描述为公式2:
PRv=1-dv+d*(u,v)ϵEPR(u)L(u)
公式2
其中v是所有网页的数量,其它变量含义保持一致。
这种思想与传统的PageRank思想大致一致,不同的地方在于它能更好的模拟一个用户在浏览网页时的行为,公式后半部分是根据每次的迭代所得到的PR值,根据这个值进行网页排序,越大的越靠前,用户在浏览网页时点击他的概率也相印的较高;前半部分则是模拟了用户在不关注排名时的行为,随机打开了一个网页中的一个页面。
不管是PageRank算法还是Matthew Richardson 与 Pedro Domingos描述的personal pagerank算法,其应用的随机游走的模型都是非常成功的,但是这种算法本身的缺点也是非常之明显的:将查询抽象为一个与查询无关的模型,线下进行计算,无疑的造成了主题的漂移性,对于新网页的支持也弱于旧的网页;另外,这种算法是