22

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

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

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

有人可以用更少的数学符号提供一个基本的解释（例子会很好）吗？

提前致谢。

4

7 回答 7

26

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

简而言之，这个公式说要计算页面 X 的 PageRank...

   对于此页面的所有反向链接（=链接到 X 的所有页面）
   你需要计算一个值
         链接到 X [R'(v)] 的页面的 PageRank
         除以
         在此页面上找到的链接数。[女]
         您添加的
           一些“排名来源”，[E(u)] 由 c 归一化
             （我们稍后会谈到这个目的。）

     你需要将所有这些值相加 [The Sigma thing]
     最后，将它乘以一个常数 [c]
        （这个常数只是为了保持 PageRank 的范围易于管理）

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

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

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

  • 通常，从该领域公认的专家那里获得推荐信比从不知名的人那里获得推荐信要好。
  • 不管是谁推荐，通过也向其他人推荐，他们正在降低他们对你的推荐的价值。

如您所见，这个公式在某种程度上使用了循环引用，因为要知道 X 的页面范围，您需要知道链接到 X 的所有页面的 PageRank。那么您如何计算这些 PageRank 值？...文档部分中解释的下一个收敛问题在哪里开始。

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

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

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

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

最后以一个非常易于理解的文本（但有许多指向深入信息的链接），我想提一下维基百科的优秀文章

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

我希望这个能有一点帮助...

于 2009-09-20T18:38:04.440 回答
9

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

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

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

于 2009-09-20T19:02:38.820 回答
5

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

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

谢谢你让我谷歌这个。

于 2009-09-20T18:31:33.020 回答
3

您可能还想阅读 David Austin 撰写的关于构建 Pagerank 矩阵背后的数学的介绍性教程，题为Google 如何在 Web 的 Haystack 中找到您的针；它从一个简单的示例开始，并构建为完整的定义。

于 2009-09-20T19:44:11.657 回答
3

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

“Programming Collective Intelligence”也对 Page Rank 进行了很好的讨论。

于 2009-09-20T20:38:07.100 回答
3

在我看来，Duffymo 发布了最好的参考。我在大四的时候研究了页面排名算法。页面排名正在执行以下操作：

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

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

    1/u_{n} 其中 u_{n} 是来自 u 的出站链接数。

  3. 假设上面定义的马尔可夫链是不可约的（这可以在结果略有下降的情况下强制执行）

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

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

因此，pagerank 算法所做的所有事情都是将 Web 的拓扑结构考虑在内，以表明网站是否应该重要。一个站点的传入链接越多，随机粒子在该站点上花费无限时间的可能性就越大。

于 2009-09-21T04:31:24.667 回答
0

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

于 2012-10-18T05:37:55.277 回答