PageRank vs SVD

Question

Pagerank適用於一系列頁面的節點圖和由其各自的內部和外部鏈接形成的有向邊。因此，特定頁面的排名廣泛地是節點圖中由局部引起的效應。

SVD另一方面，工作在整個矩陣的值，沒有方向性 - 站點A和站點B之間的鏈接只會在正確的矩陣元素上註冊爲1。這是一個全球性的系統，所以排名是一個全球性的影響。

鑑於網絡衍生矩陣的極端稀疏性，我期望SVD在這裏表現不佳，因爲它需要一個完整的數據集，並且有很大的內存需求。

這是真的嗎？ Pagerank勝過SVD很大程度上是因爲它是基於節點圖的算法嗎？ Pagerank如何從一個頁面推斷超出單詞提及次數的語義相關性？或者這是第二步，在Pagerank排名頁面之後執行？

Answer 1

這裏有兩個問題：哪個度量容易計算，哪個度量產生我們正在尋找的信息？我不知道這兩個問題的答案，但我可以給出部分答案。

首先，相關性。這兩個數量都是centrality度量，用網絡理論中的一個術語。 PageRank計算（特徵向量中心性的變體），而SVD顯然導致超鏈接誘導主題搜索（HITS）算法。我從Peter Dodds（佛蒙特大學）的this handout得到了這個。他們衡量不同的事情，但我不清楚哪一個衡量網頁的重要性最相關。

其次，計算成本。從數學上講，PageRank是（修改後的）鄰接矩陣的主要特徵向量 - 如維基百科頁面上所解釋的那樣 - 而HITS給出鄰接矩陣的主導奇異向量。兩者都由全球網頁和它們之間的鏈接來定義，並且兩者都可以通過僅在本地考慮節點圖來計算。所以乍一看，我認爲計算成本大致相等。

總之，我不知道爲什麼PageRank比SVD好;我甚至不清楚它比SVD更好。

Answer 2

請注意，PageRank使用傳送的隨機行走矩陣。傳送對於避免隨機行走矩陣的（低度）局部特徵向量很重要。我認爲PageRank比HITS要好，因爲隨機行走矩陣是一個度量歸一化的鄰接矩陣，它抑制了大程度節點和循環的影響，而不是大規模節點可以製作局部向量的HITS。