algorithm - Pagerank 与 SVD

Question

Pagerank在一系列页面的节点图和由它们各自的向内和向外链接形成的有向边上工作。因此，特定页面的排名广泛地是节点图中的局部诱导效应。

SVD ，另一方面，适用于整个值矩阵，并且没有方向性 - 站点 A 和站点 B 之间的链接只会在正确的矩阵元素上注册为 1。这是一个全局系统，因此排名是一个全局效应。

鉴于网络派生矩阵的极度稀疏性，我预计 SVD 在这里表现不佳，因为它需要完整的数据集，并且具有显着的内存需求。

这是真的吗？ Pagerank 是否主要因为它是基于节点图的算法而胜过 SVD？除了提及单词的次数之外，Pagerank 如何从页面推断出语义相关性？还是在 Pagerank 对页面进行排名后执行第二步？

Answer 1

这里有两个问题:哪个度量容易计算，哪个产生我们正在寻找的信息？我不知道这两个问题的答案，但我或许可以给出部分答案。

首先，相关性。两个数量都是 centrality措施，使用网络理论中的一个术语。 PageRank 计算(一种变体)特征向量中心性，而 SVD 显然导致了超链接诱导主题搜索 (HITS) 算法。我从 this handout 得到这个来自 Peter Dodds(佛蒙特大学)。它们衡量的是不同的东西，但我不清楚哪一个与衡量网页的重要性最相关。

其次，计算成本。从数学上讲，PageRank 是(修改后的)邻接矩阵的主要特征向量 - 正如维基百科页面上所解释的那样 - 而 HITS 给出了邻接矩阵的主要奇异向量。两者都是由网页的全局网络和它们之间的链接定义的，并且都可以通过只考虑局部节点图来计算。所以乍一看，我认为计算成本大致相等。

总之，我不知道为什么 PageRank 比 SVD 好；我什至不清楚它是否比 SVD 更好。