中心性演算法

Ⅰ betweeness（中間中心性或中介中心性）

中間中心性，即betweenness，是基於節點在圖中作為其他節點之間最短路徑中必經路徑的次數來衡量節點的重要性。這一概念建立在最短路徑搜索演算法之上，如Dijkstra演算法，通過擴展到全圖，即對每個節點執行一次Dijkstra演算法，然後使用並行計算來提高效率。最常用的是所有點對最短路徑演算法（APSP algorithm），用於計算圖中任意兩點間的最短路徑。在圖中，橋節點（如大圓中的女生或渣男角色）在連接獨立社交圈中起著關鍵作用，其通過的最短路徑數量往往較多，因為這些獨立圈間直接連接較少，通過橋節點實現連接。中間中心性定義為：對於每個節點u，計算所有節點s和t之間最短路徑總數p，以及通過節點u的最短路徑數量p(u)。計算過程涉及遍歷所有節點，找出通過它們的最短路徑，計算最短路徑占所有可能最短路徑的百分比，最後將這些值相加得到節點的中間中心性得分。

在某些特定場景，如涉及非法交易的黑中介，中間中心性計算顯示出較高的效率。在這種情況下，黑中介作為不同用戶群體（如國外教授A、國內學生C和黑中介B）之間的連接點，其中間中心性得分顯著高於其他參與者。由於黑中介在非法業務中扮演的關鍵角色，它連接了原本獨立的社交圈，使得在圖中其作為關鍵節點的重要性突出。

原中間中心性演算法計算復雜度高，難以在大型圖中實現高效計算。為解決這一問題，出現了近似中間中心性計算方法，如RA-Brandes演算法。該演算法通過考慮節點的子集而非所有可能的節點對，以減少計算復雜度。在Neo4j中，RA-Brandes演算法用於提高中間中心性計算的效率。此外，還需注意，中間中心性演算法在非聯通圖中的應用存在誤差問題。解決方法包括分別計算每個連通分量的中間中心性，對計算結果進行懲罰以考慮不同連通分量的節點數量大小，或過濾掉節點數量較少的連通分量，對每個節點數量較多的連通分量進行獨立分析。

在具體實現方面，網路分析庫networkit提供了兩種近似中間中心性計算方法。其中一種方法涉及計算圖的直徑和一個超參數r，然後在每次迭代中隨機采樣節點對，並計算它們之間的最短路徑集合。通過這一過程，演算法估計了每個節點的中間中心性得分。第二種方法則直接關注於提高中間中心性計算的效率和准確性，通過優化采樣過程和迭代演算法，提供了更精確的中間中心性估計。