PageRank 及其数学：需要解释

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 的所有网页都是增加其“价值”的价值。通过链接到某个页面，他们“投票”支持该页面。然而，这种“投票”的权重或多或少取决于两个因素：

• 链接到 X 的页面的受欢迎程度 [R'(v)]
• 链接到 X 的页面是否也链接到许多其他页面这一事实。 [Nv]

这两个因素反映了非常直观的想法：

• 通常从该领域公认的专家那里得到一封推荐信比从一个不知名的人那里得到推荐信要好。
• 无论是谁提供推荐，通过向其他人提供推荐，他们都会降低他们向您推荐的价值。

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

本质上，通过从所有页面的某些“随机”（或最好是“合理的猜测”）PageRank 值开始，然后计算使用上面的公式计算 PageRank 后，新的计算值会变得“更好”，当您迭代此过程几次时，这些值会收敛，即它们会越来越接近实际/理论值。因此，通过迭代足够多的次数，我们会达到这样的时刻：额外的迭代不会为上次迭代提供的值增加任何实际精度。

从理论上讲，这很好。将此算法转换为等效的算法，但可以更快地完成。有几篇论文描述了如何完成此任务以及类似的任务。我暂时没有这样的参考资料，但稍后会添加这些参考资料。请注意，它们确实会涉及大量的线性代数。

编辑：正如所承诺的，这里有一些有关计算页面排名算法的链接。
PageRank Haveliwala 1999 的高效计算 ///
利用网络的块结构进行计算 PR Kamvar 等人 2003 ///
一种快速两阶段算法计算 PageRank Lee 等人。 2002

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

为了以非常易于理解的文本结束（但有许多深入信息的链接），我想提一下 维基百科的优秀文章

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

我希望这会有所帮助......

Answer 2

如果您真的想为搜索引擎开发算法，我强烈建议您参加线性代数课程。在没有面对面课程的情况下，Gilbert Strang 的 MIT OCW 课程相当不错（视频讲座位于 http://ocw.mit.edu/OcwWeb/Mathematics/18-06Spring-2005/VideoLectures/）。

像这样的课程肯定会让您理解您提供的文档中的数学符号——该论文中的所有内容都是第一年线性代数课程中不会涵盖的。

我知道这不是您正在寻找的答案，但这确实是您的最佳选择。当你没有很好地掌握基本概念时，让别人尝试向你解释各个符号或算法并不是很好地利用任何人的时间。

Answer 3

这是您需要的论文：http://infolab.stanford.edu/~backrub/google .html（如果您不认识作者的姓名，可以在此处找到有关他们的更多信息：http://www.google.com/corporate/execs.html）。

文件中使用的符号以通俗英语描述。

谢谢你让我用谷歌搜索这个。

Answer 4

您可能还想阅读由 David Austin 撰写的关于构建 Pagerank 矩阵背后的数学原理的介绍性教程，标题为 Google 如何在网络大海捞针中找到你的目标；它从一个简单的示例开始，然后构建完整的定义。

Answer 5

“价值 25,000,000,000 美元的特征向量：Google 背后的线性代数”。 来自 Rose- Hulman 有点过时了，因为现在 Page Rank 是 $491B 的线性代数问题。我认为这篇论文写得很好。

“编程集体智慧”也对页面排名进行了很好的讨论。

Answer 6

达菲莫发布了我认为最好的参考。我在本科四年级时研究了页面排名算法。页面排名正在执行以下操作：

1. 将当前网页的集合定义为有限马尔可夫链的状态。

2. 定义从站点 u 转换到 v 的概率，其中存在从 u 到 v 的传出链接

   1/u_{n}，其中 u_{n} 是从 u 发出的传出链接的数量。

3. 假设上面定义的马尔可夫链是不可约的（这可以通过仅稍微降低结果来强制执行）

4. 可以证明每个有限不可约马尔可夫链都具有平稳分布。将页面排名定义为平稳分布，也就是说，当状态转换次数趋于无穷时，随机粒子最终到达每个给定站点的概率的向量。

Google 使用幂法的细微变化来查找平稳分布（幂法查找主导特征值）。除此之外没有什么可做的。它相当简单和优雅，可能是我能想到的最简单的马尔可夫链应用之一，但它值很多钱！

因此，PageRank 算法所做的就是考虑网络的拓扑结构，作为网站是否重要的​​指示。站点拥有的传入链接越多，随机粒子在无限时间内停留在站点上的概率就越大。

Answer 7

如果您想通过更少的数学了解有关页面排名的更多信息，那么 这是关于基本矩阵运算的非常好的教程。我向所有没有多少数学背景但想深入研究排名算法的人推荐它。