algorithm - Pagerank 及其数学 : Explanation needed

Question

我是一名学生，有兴趣开发一个搜索引擎来索引我所在国家/地区的网页。一段时间以来，我一直在研究要使用的算法，并且我认为 HITS 和 PageRank 是目前最好的。我决定使用 PageRank，因为它比 HITS 算法更稳定(或者我已经读过)。

我找到了无数与 PageRank 相关的文章和学术论文，但我的问题是我不理解这些论文中构成算法的大部分数学符号。具体来说，我不明白谷歌矩阵(不可约的随机矩阵)是如何计算的。

我的理解是基于这两篇文章:

• http://online.redwoods.cc.ca.us/instruct/darnold/LAPROJ/fall2005/levicob/LinAlgPaperFinal2-Screen.pdf
• http://ilpubs.stanford.edu:8090/386/1/1999-31.pdf

有人可以用较少的数学符号提供基本解释(例子会更好)吗？

提前致谢。

Answer 1

PageRank 的正式定义，如引用文件第 4 页所定义，在数学方程式中用有趣的“E”符号表示(它实际上是大写的 Sigma 希腊字母。Sigma 是字母“S”这里代表求和)。

简而言之，这个公式表示计算第 X 页的 PageRank...

   For all the backlinks to this page  (=all the pages that link to X)   you need to calculate a value that is         The PageRank of the page that links to X    [R'(v)]         divided by          the number of links found on this page.    [Nv]         to which you add           some "source of rank",  [E(u)] normalized by c             (we'll get to the purpose of that later.)     And you need to make the sum of all these values [The Sigma thing]     and finally, multiply it by a constant   [c]         (this constant is just to keep the range of PageRank manageable)

这个公式的关键思想是所有链接到给定页面 X 的网页都在增加其“值(value)”的值(value)。通过链接到某个页面，他们“投票”支持该页面。然而，这个“投票”的权重或多或少取决于两个因素:

• 链接到 X [R'(v)] 的页面的流行度
• 链接到 X 的页面是否也链接到许多其他页面的事实。 [Nv]

这两个因素反射(reflect)了非常直观的想法:

• 从该领域公认的专家那里获得推荐信通常比从陌生人那里获得更好。
• 无论是谁提供推荐，如果他们也向其他人提供推荐，他们就会降低他们向您推荐的值(value)。

正如您所注意到的，这个公式使用了有点循环引用，因为要知道 X 的页面范围，您需要知道链接到 X 的所有页面的 PageRank。那么如何你算出这些 PageRank 值了吗？...这就是文档开始部分解释的下一个收敛问题的地方。

本质上，对于所有页面，通过一些“随机”(或者最好是“合理猜测”的 PageRank 值)开始，并通过使用上面的公式计算 PageRank，新的计算值会变得“更好”，因为你迭代这个处理几次。值收敛，即它们每个都越来越接近实际/理论值。因此，通过迭代足够多的次数，我们达到了额外迭代不会达到的时刻为上次迭代提供的值添加任何实际精度。

现在...从理论上讲，这很好而且花花公子。诀窍是将此算法转换为等效但可以更快完成的算法。有几篇论文描述了如何完成此任务以及类似的任务。我手头没有这样的引用资料，但稍后会添加这些。当心它们会涉及大量线性代数。

编辑:正如所 promise 的，这里有一些关于计算网页排名的算法的链接。 Efficient Computation of PageRank Haveliwala 1999/// Exploiting the Block Structure of the Web for Computing PR Kamvar etal 2003/// A fast two-stage algorithm for computing PageRank Lee et al. 2002

虽然上面提供的链接的许多作者都来自斯坦福，但很快就会意识到寻求高效的类似 PageRank 的计算是一个热门的研究领域。我意识到这些 Material 超出了 OP 的范围，但重要的是要暗示基本算法对大型网络不实用这一事实。

为了以易于理解的文本结束(但有许多指向深入信息的链接)，我想提一下 Wikipedia's excellent article

如果您认真对待这类事情，您可以考虑参加数学入门/复习类(class)，尤其是线性代数，以及一般处理图形的计算机科学类(class)。顺便说一句，Michael Dorfman 在这篇文章中对 OCW 的 1806 讲座视频提出了很好的建议。

希望对您有所帮助...