Pagerank与SVD的比较

Question

Pagerank与SVD的比较

algorithmmathgraphpageranksvd

5

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

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

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

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

- Phil H

2个回答

1

请注意，PageRank使用了一个随机游走矩阵进行跳转。跳跃是重要的，以避免随机游走矩阵的局部特征向量（低度）。我认为PageRank比HITS更好，因为随机游走矩阵是一个度规范化的邻接矩阵，抑制了大度数节点和循环的影响，而不像HITS，大度数节点可能会产生局部向量。

- Pan Zhang

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jitse Niesen · Accepted Answer

这里有两个问题：哪个度量方式更容易计算，以及哪个度量方式可以提供我们需要的信息？我不知道这两个问题的答案，但我或许可以给出部分答案。

首先是相关性。两种量都是来自网络理论中的中心性度量。PageRank计算（一种变体的）特征向量中心性，而奇异值分解（SVD）似乎会导致“超链接引导主题搜索”（HITS）算法。它们测量的是不同的东西，但对于衡量一个网页的重要性，哪一个更相关并不清楚。这些信息来自Peter Dodds（佛蒙特大学）的这个手册。

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

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