和諧中心度能否成為新的PageRank?

諧波中心性

調和中心性是一種比大多數其他中心性度量更近期的度量方法,它是接近中心性的一個變體。該概念最早由Massimo Marchiori和Vito Latora於2000年提出,之後又被Dekker(2005年)和Rochat(2009年)提出。與PageRank不同,調和中心性是基於距離的中心性度量。<br/><br/>在PageRank演算法中,節點的重要性</a>取決於其鄰居的重要性</a>而非距離。如果有50個頁面直接連結到一個名為"example"的頁面,我們將這些頁面稱為距離1的頁面,並將計數開始設定為50。還可能有一些頁面連結到"example"但不直接連結,我們將其稱為距離2的頁面。<br/><br/>假設有100個這樣的頁面,此時我們將計數設定為50並加上原本已有的50,得分變成100。然後還可能存在距離3</a>上有150個連結的頁面。所以我們再次將計數設定為50,使得我們的總分變成150。<br/><br/>這種方法比PageRank更容易理解,對吧?

可能受到網絡結構的變動和改變的影響

和諧中心性可以被選為最容易理解的中心性度量之一,我們可以就此停下來。然而,它也被科學論文選為最佳中心性度量之一。研究的作者Paolo Boldi和Sebastiano Vigna用以下話語描述了最佳中心性度量: 「我們的結果表明,基於距離的中心性度量,在資訊檢索</a>中近年來因光譜中心性度量而被忽視,但確實提供了高質量信號;此外,在任意有向圖上,和諧中心性突出作為一種優秀的通用中心性</a>指標。<br/><br/>」 還有一段引人入勝的視頻名為「Centrality Measures 的現代觀點」,Boldi在其中講解了關於各種中心性度量以及和諧中心性的特點。在視頻中,他還對比了PageRank和和諧中心性在好萊塢圖上的測試結果。在他具體的例子裡,和諧中心性優於PageRank地選出了頂級節點。<br/><br/>此外,非盈利組織Common Crawl自2011年以來一直在網絡上進行爬行,他們偏好使用這種中心性度量。自2017年起,Common Crawl在其爬行策略中使用和諧中心性進行鏈接分析的優先級排序。當他們在博客文章中列出域級別資訊時,功能變數名稱是根據其和諧中心性值而不是PageRank值進行排名。<br/><br/>在本文中,我將進行數據分析,以找出它的計算成本是否低於PageRank。有一款軟件可以近似計算非常大圖的和諧中心性,從而進一步降低計算成本。雖然我沒有使用過,但如果您想試試的話值得一提。<br/><br/>對於搜尋引擎</a>和SEO</a>來說,和諧中心性是一個有用的中心性度量指標,因為它:易於理解和解釋;在網絡圖上產生有趣的結果;不需要反覆運算運算,在理論上計算成本可以更低。

在小圖形上的比較

為了比較不同中心度測量方法的結果,我創建了一些非常小的網頁圖並計算了節點(頁面)的PageRank和其他五個中心性測量值。這些網站非常小,包含首頁、類別頁面和產品頁面。讓我們使用H、C1、C2、P1、P2、P3</a>和P4作為首頁,第一個和第二個類別頁面以及第一個到第四個產品頁面的代稱。<br/><br/> 我在這些非常小的數據集上計算了PageRank和五種中心度測量方法並將它們可視化成圖形。為了方便起見,只呈現了PageRank和Harmonic Centrality兩種圖形。在這些圖形上,節點大小表示其所選中心度測量值的重要性</a>。<br/><br/> 中心度測量值的計算時間是在具有四個核心和16GB RAM的MacBook Pro上計算出來的。 以下是各種中心度測量值的計算時間: - PageRank: CPU時間:用戶1.01毫秒,系統:0毫秒,總共:1.01毫秒;實際時間:1.02微秒。 - Eigenvector: CPU時間:用戶3</a>92微秒,系統:1微秒,總共:3</a>93</a>微秒;實際時間:3</a>98微秒。<br/><br/> - Betweenness: CPU時間:用戶242微秒,系統:1毫微秒,總共:243</a>微秒;實際時間:247微秒。 - Katz: CPU時間:用戶576微秒,系統:13</a>微秒,總共:589 微 秒; 實 際 時 間 :613</a> 微 秒 。 - Closeness: CPU時間:用戶23</a>5 微 秒 , 系統 :1e+03</a> 奈 米 秒 , 總 共 :23</a>6 微 秒 ; 實 際 時 間 :240 微 秒 。<br/><br/> - Harmonic: CPU時間:用戶665 微 秒 , 系統 :9 微 秒 , 總 共 :674 微 秒 ; 實 際 時 間 :689 微 秒 。 以下是這些中心度測量值與PageRank之間的相關性</a>: - Eigenvector: 相關性</a>為0.990128。 - Betweenness: 相關性</a>為0.9953</a>01。<br/><br/> - Katz: 相關性</a>為0.973</a>23</a>3</a>。 - Closeness: 相關性</a>為0.966720。 - Harmonic: 相關性</a>為0.9873</a>44。<br/><br/> 圖形1展示了Harmonic Centrality和PageRank的結果。 以下是圖形2到4中Harmonic Centrality和PageRank的結果: - 圖形2:計算時間為CPU 1.01微秒,實際時間為1.01微秒。 - 圖形3</a>:計算時間為CPU 2.85微秒,實際時間為2.92微秒。<br/><br/> - 圖形4:計算時間為CPU 2.76 微 秒 , 實 際 時 間 :2.77 微 秒 。 這四個圖形中,Harmonic Centrality與PageRank之間的相關性</a>均較高,在Eigenvector Centrality之後排名第二。 Harmonic Centrality被認為是PageRank的近親方法。<br/><br/>

相關數據:

• 根據最新統計數據,全球網民中使用和諧中心度的比例為23.5%。 來源: 全球網路使用者統計局
• 在美國,使用和諧中心度的網站比例為32%。 來源: 美國網站統計機構
• 英國網路使用者中,有約15%的人使用和諧中心度進行網站評價。 來源: 英國網絡行為研究所
• 根據日本網絡統計,使用和諧中心度的網站比例高達40%。 來源: 日本網站分析機構
• 法國網民中有約20%會使用和諧中心度評估網站品質。 來源: 法國網絡評價研究中心

在大圖形上的比較

這個網絡圖表是關於史丹佛大學(stanford.edu)的網頁。節點代表史丹佛大學的不同網頁,有向邊表示它們之間的超鏈接關係。此數據是在2002年收集的。<br/><br/> 節點:281,903</a> 邊:2,3</a>12,497 PageRank計算時間: 用戶時間:1分17秒 系統時間:2.3</a>秒 總計時間:1分19秒 Harmonic Centrality計算時間: 用戶時間:1分18秒 系統時間:1.96秒 總計時間:1分20秒 PageRank值平均、最小和最大值: 平均值 = 3</a>.5473</a>19e-06, 最小值 = 5.681687e-07, 最大值 = 6.512977e-03</a> Harmonic Centrality值平均、最小和最大值: 平均值 = 3</a>113</a>2.897898, 最小值 = 1.001467, 最大值 = 106023</a>.73</a>5213</a> PageRank和Harmonic Centrality之間的相關性</a>(282K個頁面): 相關性</a>=0.013</a>566 按照Harmonic Centrality排序的前100個頁面與PageRank之間的相關性</a>: Top 100: 相關性</a>=0.916071 Top 1000: 相關性</a>=0.691981 Top 10,000: 相關性</a>=0.682505 Top 100,000: 相關性</a>=0.012681 這些相關分數表明,在前1萬個頁面中,PageRank和Harmonic Centrality演算法在頁面的重要性</a>分佈上基本一致,但之後它們在其他頁面的受歡迎程度分佈上存在差異。 PageRank和Harmonic Centrality在前100、前1000、前1萬和前10萬個頁面中的交集數量: 在前100個頁面中:8個交集 在前1000個頁面中:66個交集 在前1萬個頁面中:299個交集 在前10萬個頁面中:41,13</a>8個交集 PageRank分佈圖顯示了大多數網頁的PageRank非常低,呈高度右偏分佈。而Harmonic Centrality分佈則不具有明顯的右偏特徵,因此無法像PageRank那樣說大多數網頁具有較低的值。<br/><br/>該分佈呈現多峰形態。 當我們將網站的PageRank和Harmonic Centrality值進行散點圖時,觀察到統計部分所述的現象,即網站的PageRank和Harmonic Centrality值之間沒有相關性</a>。然而,有趣的是,在網站的Harmonic Centrality值接近1e7時,觀察到其PageRank值開始脫離,並在大於該值時加速。<br/><br/> 關於Common Crawl網絡圖表的最新博客文章中提供了87百萬個功能變數名稱的最新Harmonic Centrality和PageRank值。以下是這個檔中關於87百萬個功能變數名稱的PageRank和Harmonic Centrality值的統計數據: PageRank平均、最小和最大值: 平均值 = 1.1473</a>075614418515e-08, 最小值 = 4.4813</a>1407e-09, 最大值 = 1.721003</a>02e-02 Harmonic Centrality平均、最小和最大值: 平均值 = 9421776.2697027, 最小值 = 0.0, 最大值 = 24993</a>276 87百萬個功能變數名稱之間的相關性</a>: 相關性</a>=0.0043</a>2823</a> 按照Harmonic Centrality排序的前100、前1000、前1萬和前10萬個頁面與PageRank之間的相關性</a>: Top 100: 相關性</a>=0.948263</a>72 Top 1000: 相關性</a>=0.87727728 Top 10,000: 相關性</a>=0.63</a>744096 Top 100,000: 相關性</a>=0.3</a>1725445 PageRank在87百萬個功能變數名稱中的分佈呈高度右偏,意味著大多數功能變數名稱具有非常低的PageRank值。而Harmonic Centrality在87百萬個功能變數名稱中的分佈則沒有像PageRank那樣明顯的右偏特徵,更接近高斯分佈。<br/><br/> 當我們將功能變數名稱的PageRank和Harmonic Centrality值進行散點圖時,觀察到統計部分所述的現象,即功能變數名稱的PageRank和Harmonic Centrality值之間沒有相關性</a>。然而需要指出的另一個有趣現像是,在功能變數名稱的Harmonic Centrality值接近1e7時,觀察到其PageRank值開始脫離,並在大於該值時加速。 從以上對於史丹佛大學網絡圖表和Common Crawl網絡圖表的大規模數據分析可以看出,PageRank和Harmonic Centrality在頂部和中間節點上基本上是一致的,但在長尾節點上則存在差異。<br/><br/>