文档介绍：PageRank 背景摘要 PageRank 是衡量网络节点重要性的指标之一,个性化 PageRank 是普通 PageRank 的推广形式。本文首先叙述了 PageRank 算法的原理与基本思想, 说明了个性化 PageRank 算法产生的背景, 总结了当今个性化 PageRan k 算法的研究现况和发展趋势, 对于各种个性化 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 来调整结果, 使那些更具“等级/ 重要性”的网页在搜索结果中另网站排名获得提升,从而提高搜索结果的相关性和质量。其主要思想如下: 1. 如果一个页面被多次引用,则这个页面很可能是重要的; 2. 如果一个页面尽管未被多次引用,但都被一个重要的页面引用,则这个页面很可能是重要的; 3. 一个页面的重要性被均分,并传递到它所引用的页面。衡量每个页面的 PageRank 分数排名如公式 1 所示的算法: ????(????)PR ???? = 1?d +d? ??=1???? 公式?? 其中??(????) 是???? 链出页面的数量, PR 值是每个网页的重要程度, 而d 是阻尼因子(一般取 )。初始时,对每个网页赋值为: PRv= ?? 。然后用公式 1 进行迭代,直至收敛并趋于稳定。容易知道, PR 值越高说明该网页越受欢迎( 越重要)。例如:一个 PR 值为 1 的网站表明这个网站不太具有流行度,而 PR 值为 7 到 10 则表明这个网站非常受欢迎(或者说极其重要) 。一般 PR 值达到 4, 就算是一个不错的网站了。 Google 把自己的网站的 PR 值定到 10, 这说明 Google 这个网站是非常受欢迎的,也可以说这个网站非常重要。 Matthew Richardson 与 Pedro Domingos 于 2001 将其描述为公式 2: 11 PRv =1?d????(??)+d? (??,??)???? 公式?? 其中?? 是所有网页的数量,其它变量含义保持一致。这种思想与传统的 PageRank 思想大致一致, 不同的地方在于它能更好的模拟一个用户在浏览网页时的行为, 公式后半部分是根据每次的迭代所得到的 PR 值,根据这个值进行网页排序,越大的越靠前,用户在浏览网页时点击他的概率也相印的较高; 前半部分则是模拟了用户在不关注排名时的行为,随机打开了一个网页中的一个页面。不管是 PageRan k 算法还是 Matthew Richardson 与 P