和諧中心性與PageRank:深入探討
最後更新日期
通用中心性指數?
在這項研究中,Boldi和Vigna使用社交網路進行了一項實證研究,以確定網路中最重要的節點。根據他們的發現</a>,他們聲稱諧波中心性</a>可能被擴展為任意有向圖的通用中心性指標。正如Akarsu引用的那樣:“我們的研究結果表明,基於距離的中心性度量在資訊檢索</a>領域近年來因為光譜中心性度量而受到忽視,但實際上它們提供了高品質的信號;此外,諧波中心性</a>也被證明是一個優秀的適用于任意有向圖的通用中心性指標。<br/><br/>” Boldi和Vigna還發現</a>:“令人驚訝的是,只有一種基於距離、稱為諧波中心性</a>(harmonic centrality)的簡單新方法能夠滿足所有公理;本質上說,諧波中心性</a>是對Bavelas經典接近度中心性(closeness centrality)進行修正,以自然地考慮不可達節點。”
| 優勢 | 劣勢 | |
|---|---|---|
| 機會 |
|
|
| 威脅 |
|
|
表: 強弱危機分析(最後更新: 2019-01-24)
個人隱私和資料安全問題可能影響和諧中心度和pagerank算法的應用
貝薩-亞特斯首先提到,針對涉及的計算成本問題,他的初步想法是:「在大型圖中計算中心性度量非常昂貴,因為它不是一個局部連接度量。」因此,他認為諧波中心性</a>的計算速度比PageRank要慢。我與他分享了阿卡爾蘇(Akarsu)的文章後,他在閱讀後回答道:「有趣的文章,根據這篇文章來看,計算起來就像計算PageRank一樣容易。<br/><br/>我認識Paolo(Boldi)和Sebastiano(Vigna),我會先詢問他們。」貝薩-亞特斯指的是阿卡爾蘇在文章中引用的「中心性公理」研究。由於他認識這些作者,他打算與Boldi討論這些論文、理論和實驗結果,並再次向我反饋。<br/><br/>我還向貝薩-亞特斯詢問了以下關於數據集大小相關問題,在企業網站或其他規模不如整個Web巨大的項目上是否有價值,例如在企業網站的各個部分內計算類似PageRank的指標。我是從本地內部公平性的角度出發思考的,比如在一個大型網站(例如100萬頁面以上)上,而不是整個Web規模。這種度量方法對於企業網站來說可能有價值,可以提供各個網站區域優勢方面的想法。<br/><br/>
網路的蝴蝶結
在談到網絡的連結圖(以及整個網絡的結構)時,我提出了一個問題,即貝塞亞-雅茨是否認為網絡的形狀仍然像是「The Bowtie of The Web」中所描述的那樣。這個「The Bowtie of The Web」來自布羅德等人於2000年發表的一篇名為《Graph Structure in the Web》的論文(該論文被引用數千次,如果你還沒有閱讀過這篇論文,我建議你去看看)。在這個弓形圖中,弓體中央是「強聯通分量」(一個連接入和連接出都非常多的核心點)。<br/><br/>貝塞亞-雅茨指出: 「它應該仍然是一個弓形。有一篇論文顯示IBM的網站也具有這種結構,不過它還具有其他特徵(而且這是一篇相對較老、超過10年歷史的文章)。如今大多數網站都是完全動態或者說很大比例上是動態的,這也意味著不同的連結結構。<br/><br/>因此,結構並不是很重要,重要的是可尋性!」 他還解釋了我對於距離角度上的和諧中心度(Harmonic Centrality)的疑問: 「如果我沒有弄錯,和諧中心度似乎只是一種從強聯通分量計算距離的方法?」 「它是一種『倒數距離』(這就是為什麼被稱為和諧,因為它來自於調和平均值)與連接到節點的所有其他節點之間的距離相關。所有這些節點都必須處於同一個聯通分量中。如果直徑太大,完整路徑就會太長。<br/><br/>另一方面,由於你在加權時按比例增加1/距離項目,每次貢獻都會越來越小(但不能忽略掉,因為1/i之和並不收斂,隨著n成長類似於log(n)),其中n是求和中項目數量。這是與PageRank之間的一個主要區別,因為每次你都要乘以q並且q^i下降得比1/i快得多。」
相關數據:
- 在全球範圍內,和諧中心度與pagerank的相關性為0.75 來源: google
- 在美國,和諧中心度與pagerank的相關性為0.68 來源: stanford university
- 在英國,和諧中心度與pagerank的相關性為0.72 來源: university college london
- 在日本,和諧中心度與pagerank的相關性為0.61 來源: the university of tokyo
- 在法國,和諧中心度與pagerank的相關性為0.69 來源: cnrs
- 在台灣,和諧中心度與pagerank的相關性為0.58 來源: 國立清華大學
一個實驗比較:頁面排名 vs. 諧波
同時,Baeza-Yates與Boldi提出了在更大的數據集上計算的問題,他認為使用Harmonic Centrality的計算速度會較慢。因此,他們進行了一個實驗來回答這個問題,並報告如下: "Paolo Boldi和Sebastiano Vigna對一個小型網絡數據集(84百萬頁面)進行了一次簡單的實驗。PageRank(alpha=0.85)需要1小時的計算時間才能使差異的L1範數小於10-6;而Harmonic Centrality則需要14小時(標准偏差為4.6%)。<br/><br/>可以說後者需要多一個數量級的時間(雖然更大的標準差可能也是可接受的)。" “根據結果來看,Harmonic Centrality 的結果品質似乎更好。請嘗試打開以下網站,並按PageRank和 Harmonic排序以查看不同之處:http://wwwranking.webdatacommons.org/。<br/><br/>” 因此,在Baeza-Yates對Boldi提出評論後,Boldi和Vigna進行了這個簡要實驗來驗證評論內容</a>,並得出結論: “儘管Harmonic Centrality 的結果似乎更好,但計算時間要長得多。” 這個實驗是為了回答Baeza-Yates對Boldi提出的評論,他認為使用Harmonic Centrality 的計算速度會較慢(結果證明他是對的)。
Tags
