基于割點移除的社交網絡重要節點評估與仿真

王 安，顧益軍

(中國人民公安大學信息技術與網絡安全學院，北京 102600)

1 引言

隨著復雜網絡科學的不斷研究與發展，人們發現許多具備引用，共現關系的事物幾乎都可以被轉化成復雜網絡。人類的社交關系的呈現出一定的組織結構，其構成的社交網絡同樣可以被轉化成復雜網絡的表示。為了對社交網絡的人員進行有效地控制與管理，需要對社交網絡中的節點與結構進行詳細的分析。在社交網絡中，一些節點在網絡中處于關鍵的位置，如果這樣的節點受到攻擊不能發揮作用，就會導致整個網絡的連通情況發生較大的變化，整個網絡的功能也會受到較大的影響[1]。以社交通信網絡為例，一些關鍵人物承擔起重要的通信橋梁，對于這樣的角色，所處的位置較為特殊，所扮演的角色較為關鍵，采取特定的打擊便可以使整個網絡崩潰。因此發掘出對于社交網絡整體結構和功能起到關鍵作用的重要節點至關重要。

對于社交網絡重要節點的評估，已有許多成熟的方法[2，3]，最為經典的方法是應用復雜網絡中的中心性[4，5]，基于隨機游走的PageRank[6]等方式從不同角度測定了各個節點的重要程度，進而對節點進行排序。

近年來國內外學者針對社交網絡中節點重要性問題提出了一些新的改進方法。呂琳媛[7]等人在PageRank的基礎上增加了背景節點，形成LeaderRank算法，將整個網絡變成強連通網絡，提升了算法的迭代速度與重要節點的傳播性能。在LeaderRank的基礎之上，顧亦然[8]等人引入節點間的相似度，以此來評估節點間的相互關系，進而得到節點的重要性表示。Hu[9]等人將社區劃分與K-shell進行結合，有效的提升了K-shell算法在傳播性能上的表現。然而以K-shell為代表的算法其分辨率都較差，很多節點會具有同樣的重要程度。韓忠明[10]等人提出一種基于節點間的特殊三角型結構的LTC影響力度量模型，在SIR性能提高較為明顯。上述方法或是基于已有算法進行改進，將原始算法加入新的特征，或是直接將復雜網絡中節點間的特殊關系作為節點重要性排序的依據。而以TOPSIS[11]為代表的綜合性評估方法，將多種指標進行了融合，考慮更加全面，但是與此同時也增加了算法的復雜度。

以上方法都關注了節點的不同特征，但上述算法大多都是從傳播動力學模型進行綜合評估，得到的重要節點在傳播影響力指標上有一定的效果。對于社交網絡，一些節點對于網絡的魯棒性影響同樣是重要的指標，依次移除這些節點后對網絡結構和功能會有不同的影響。

本文從社交網絡中一些節點在結構上具有的特殊性質出發，重點關注這些節點在對整個網絡結構和功能上的影響，提出一種基于復雜網絡割點移除的節點重要度評估方法APRRank(ArticulationPointRemovalRank)

2 割點以及Tarjan算法

2.1 復雜網絡中的割點

定義1 割集：在一個無向圖中，如果有一個頂點集合，刪除這個頂點集合以及這個集合中所有頂點相關聯的邊以后，圖的連通分量增多，就稱這個點集為割集。

定義2 割點：在一個割集中，若該割集僅有一個節點，則稱該點為割點(Articulation Point)。

圖1 割點示意圖

如圖1所示，在無向連通圖G中，如果將節點a或者節點d及其所有的連邊移除，該無向連通圖G便不再連通，那么在該圖中節點a和節點d就是割點。

2.2 利用Tarjan算法求取割點

求取割點有多種方法，其中最經典的便是Tarjan算法[12]。Tarjan算法是一種基于深度優先搜索(DFS)的，可以在線性時間內得到無向圖割點的算法。在Tarjan算法中定義了兩個數值：

定義3 DFS時間戳(DFN)：對每一個節點在深度優先搜索中被遍歷時的順序記作為節點的時間戳。記節點v的DFS時間戳為DFN[v]。

定義4回溯值(LOW)：一個節點或者它的子樹通過反向邊能到達的最小DFS時間戳。記節點v的回溯值為LOW[v]。

Tarjan算法在一次深度優先搜索過程中，得到所有節點的DFN和LOW值。利用以下規則判斷節點v的是否為割點：

1)v為根節點時v的子樹數量大于一顆。可以理解為，若移除該根節點，則會產生多顆子樹，則圖便不再聯通。

2)v為非根節點，節點v存在一個子節點u使得節點v和節點u符合式(1)要求

DFN[v]≤LOW[u]

(1)

可以理解為從v的子節點u反向追溯，無法到達比 節點v更早被訪問的節點。

圖2 Tarjan算法求取割點過程示意圖

Tarjan算法求取割點的過程如圖2所示，以節點e為DFS的根節點遍歷整個網絡的所有節點。圖中節點a為非根節點，它的子樹上節點b的回溯值LOW[b]大于等于a的時間戳DFN[a]，所以節點a為割點，同理節點d也為割點。

3 基于割點移除的節點重要性方法

本文對社交網絡重要節點的評估采用的是復雜網絡節點重要性排序的方法。在諸如話單網絡，朋友關系網絡等社交網絡中，通常需要得到一些重要的人物節點，這樣的人物節點通常具有核心的作用。在復雜網絡中最直觀的解釋是，一旦這樣的節點失去相應的功能或者無法正常運轉，會導致整個網絡受到較大的損傷。

實際上，由于割點的定義就是去掉后圖便不再連通，所以移除圖中的割點便能很好的破壞網絡的結構。

而在一個圖中可能會有很多的割點，如何在這些割點中選擇“最好”的割點便是一個關鍵問題。這里將“最好割點”定義為移除該割點后能使最大聯通分量規模減小最多的節點。筆者發現，通常這樣的節點具有較高的度中心性。度中心性的計算方式如式(2)所示

(2)

實際上在這里可以將度中心性替換為PageRank，PageRank迭代計算方法如式(3)所示

(3)

其中，PR(Vi)為節點Vi的PageRank值;d為阻尼因子，1-d是隨機游走到其它節點的概率，一般取1-d=0.15；In(Vi)表示指向節點Vi的所有節點的集合，Out(Vj)表示節點vj所有指向節點的集合。由于對節點計算PageRank值時參考了節點與其鄰居，一個節點的鄰節點越重要，則這個節點越重要。計算的過程相比于度中心性具有較高的復雜度，整個算法的運行時間將會較大，因此在較大規模的網絡中使用節點的度中心性來選擇割點更為合適。

所以基于割點移除的節點重要性方法由以下幾個步驟組成：

1)構建候選移除節點集合

取當前圖的最大連通分量作為待操作子圖。利用Tarjan算法判斷并求取當前待操作子圖中所含有的割點，若當前子圖為點雙連通分量則不存在割點，如果含有割點則將所有割點放入候選移除節點集合AP

AP={n|n∈V且n為割點}

(4)

2)獲得待移除節點

將當前所有割點中具有度中心性最高的節點作為移除的節點，考慮到不是所有的圖都具有割點，因此若圖中無割點，則直接將該子圖中度中心性最高的節點作為移除節點。

圖3 割點移除過程示意圖

如圖3所示，移除割點a和割點d都可以破壞網絡的結構，使網絡的最大聯通分量規模減少，但是，移除割點a后，最大聯通分量規模減少的更多，割點a比割點d更接近網絡的核心位置。通常，在具有多個割點的情況下，度中心性更高的節點更接近網絡的中心，所以在移除節點時優先選擇度中心性更高的割點。移除節點的選擇如式(5)所示

(5)

其中AP為割點集，V為當前子圖下節點集。

3)移除節點

移除步驟1)步得到的節點。得到不含有此節點子圖。

具體而言，取G的真子圖G’使得G’符合以下要求

G′(V′，E′)?G(V，E)

(6)

其中V’，E’分別表示移除節點后的節點集合與邊集合，ω(Nr)表示取Nr所有的連邊，其取值由以下公式決定

E′=E-ω(Nr)

(7)

V′={n|n∈V且n≠Nr}

(8)

4)更新當前操作子圖

將移除節點后的圖中最大聯通分量作為新一輪移除的圖。

重復1)-4)直到整個圖中的最大聯通分量不再具有邊。

根據前文提到的步驟，本文所提出的節點重要度排序算法APRRank核心部分偽代碼如下所示。

代碼1 APRRank算法主要工作流程

Input：Graph

Output：節點排序以及評分 Score

1：FUNCTION APRRank(Graph)

2： LC ←σ(Graph)

3： APList←Tarjan(LC)

4： WHILE |LC.edges|≠ 0 do

5： IF APList ≠ ?:

6： node ←MAX(DC(APList))

7： ELSE

8： node ←MAX(DC(LC))

9： END IF

10： LC ← REMOVE(LC，node)

11： LC ←σ(LC)

12： Insert node into Score

13： APList←Tarjan(LC)

14： END WHILE

15： RETURN Scor

16：END FUNCTION

4 仿真研究

為評價基于割點移除節點重要性排序算法的有效性，本文在多個真實的，規模不一，差異較大的社交網絡中進行了仿真，實驗數據來自NR[13]提供的開源社交關系網絡。

其中Caltech36，simmons81屬于Facebook網絡數據集，wiki-Vote數據集包含從維基百科建立到2008年1月的所有投票鏈接數據。Advogato是某社交平臺信任關系網絡。仿真相關統計指標如下：

表1 仿真數據相關統計情況說明

4.1 結果對比

為了比較不同方法的重要節點排序結果，本文利用PageRank算法(PR)，度中心性(DC)，接近中心性(CC)，介數中心性(BC)，以及綜合評估方法TOPSIS，對上述網絡進行仿真，得到排名前十的重要節點。結果如表所示：

表2(a) Caltech36與wiki-Vote網絡各方法排序結果

表2(b) simmons81與advogatos網絡各方法排序結果

各個方法排序側重的依據不同，所以排序的結果也存在一定的差異，以Caltech36網絡為例，排名第一的節點就產生了不同，除了APRRank其它的方法均為709，APRRank方法首先關注的是割點，在此網絡中的度中心性最高的割點為90號，因此將90號節點作為排名第一的節點，在移除90號節點后，產生了多個聯通分量，在新的最大聯通分量中再進行對度中心性最高的割點便可得到223號節點。用APRRank排序是一個動態的過程，所以后續的排列也會和其它方法有較大的不同。

4.2 魯棒性測試

為了具體衡量本文算法的效果，本文對上述網絡分別使用中心性方法，PageRank方法，TOPSIS方法，以及APRR算法對五個不同網絡進行網絡魯棒性仿真。

在網絡魯棒性仿真中，首先，計算網絡中所有頂點的重要性，然后按照中心度量的順序從最高到最低去除指定的節點，即按照排序順序依次移除節點。為了考察攻擊一部分節點使之失去效果后，即移除該節點，網絡整體結構和功能上的變化，本文繪制了最大聯通分量相對規模(σ)隨各個方法排序結果按順序移除節點比例(n)的變化曲線。計算方式如式(9)所示

(9)

其中G為當前子圖，LC為當前子圖最大聯通分量。

Swami等人[14]應用4種不同的方法對節點進行排序并繪制魯棒性測試曲線。繪制曲線可以準確的得到依次移除這些節點對圖的影響過程，從而間衡量了節點重要性排序的效果。縱坐標為最大聯通分量規模占比，橫坐標為移除節點占比。若曲線降低的速度越快，則認為網絡在移除相應的節點后網絡功能衰減的越快，同時也就意味著這樣的節點重要性排序結果在魯棒性測試中效果越好。

圖5 Soc-wiki-Vote魯棒性曲線

圖6 Socfb-simmons81魯棒性曲線

圖7 Socfb-Caltech36魯棒性曲線

圖8 Soc-advogatos魯棒性曲線

如圖5-8所示，在魯棒性測試中，實線部分為APRR方法，其它方法均為虛線。可以從圖中看出，APRRank方法在規模不一的網絡中都有較好的效果，按照APRRank方法得到的節點重要性序列進行依次移除仿真社交網絡中的節點，4個社交網絡最大連通分量的規模衰減效果都最為明顯，絕大大分都處于其它曲線下方，可以使網絡更快的碎片化。因此在社交網絡中如果按照APRRank方法得到序列進行針對性攻擊，其打擊效果要好于常見中心性方法，PR方法以及綜合性評估方法TOPSIS，可以更加迅速的破壞網絡，瓦解網絡，證明了APRRank算法的有效性。

5 結束語

本文提出了一種基于割點移除的社交網絡重要節點評估方法，對復雜網絡中最大聯通分量里的度數高并且具備割點角色的節點進行了依次移除，并且按移除順序作為節點重要性的排序。在此基礎之上，本文對四個規模不一網絡進行了魯棒性仿真，實驗結果表明，按照本文所提出的APRRank方法依次攻擊相應的節點，可以更快的破壞網絡的整體功能，讓網絡的破碎程度更大，證實了本文所提方法的有效性。

但是，本文所提方法還有一定的不足，下一步工作將重點關注如何更快的找到割點并移除，提升算法的速度。