基于割點(diǎn)移除的社交網(wǎng)絡(luò)重要節(jié)點(diǎn)評(píng)估與仿真

王 安，顧益軍

(中國(guó)人民公安大學(xué)信息技術(shù)與網(wǎng)絡(luò)安全學(xué)院，北京 102600)

1 引言

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

對(duì)于社交網(wǎng)絡(luò)重要節(jié)點(diǎn)的評(píng)估，已有許多成熟的方法[2，3]，最為經(jīng)典的方法是應(yīng)用復(fù)雜網(wǎng)絡(luò)中的中心性[4，5]，基于隨機(jī)游走的PageRank[6]等方式從不同角度測(cè)定了各個(gè)節(jié)點(diǎn)的重要程度，進(jìn)而對(duì)節(jié)點(diǎn)進(jìn)行排序。

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

以上方法都關(guān)注了節(jié)點(diǎn)的不同特征，但上述算法大多都是從傳播動(dòng)力學(xué)模型進(jìn)行綜合評(píng)估，得到的重要節(jié)點(diǎn)在傳播影響力指標(biāo)上有一定的效果。對(duì)于社交網(wǎng)絡(luò)，一些節(jié)點(diǎn)對(duì)于網(wǎng)絡(luò)的魯棒性影響同樣是重要的指標(biāo)，依次移除這些節(jié)點(diǎn)后對(duì)網(wǎng)絡(luò)結(jié)構(gòu)和功能會(huì)有不同的影響。

本文從社交網(wǎng)絡(luò)中一些節(jié)點(diǎn)在結(jié)構(gòu)上具有的特殊性質(zhì)出發(fā)，重點(diǎn)關(guān)注這些節(jié)點(diǎn)在對(duì)整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)和功能上的影響，提出一種基于復(fù)雜網(wǎng)絡(luò)割點(diǎn)移除的節(jié)點(diǎn)重要度評(píng)估方法APRRank(ArticulationPointRemovalRank)

2 割點(diǎn)以及Tarjan算法

2.1 復(fù)雜網(wǎng)絡(luò)中的割點(diǎn)

定義1 割集：在一個(gè)無(wú)向圖中，如果有一個(gè)頂點(diǎn)集合，刪除這個(gè)頂點(diǎn)集合以及這個(gè)集合中所有頂點(diǎn)相關(guān)聯(lián)的邊以后，圖的連通分量增多，就稱這個(gè)點(diǎn)集為割集。

定義2 割點(diǎn)：在一個(gè)割集中，若該割集僅有一個(gè)節(jié)點(diǎn)，則稱該點(diǎn)為割點(diǎn)(Articulation Point)。

圖1 割點(diǎn)示意圖

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

2.2 利用Tarjan算法求取割點(diǎn)

求取割點(diǎn)有多種方法，其中最經(jīng)典的便是Tarjan算法[12]。Tarjan算法是一種基于深度優(yōu)先搜索(DFS)的，可以在線性時(shí)間內(nèi)得到無(wú)向圖割點(diǎn)的算法。在Tarjan算法中定義了兩個(gè)數(shù)值：

定義3 DFS時(shí)間戳(DFN)：對(duì)每一個(gè)節(jié)點(diǎn)在深度優(yōu)先搜索中被遍歷時(shí)的順序記作為節(jié)點(diǎn)的時(shí)間戳。記節(jié)點(diǎn)v的DFS時(shí)間戳為DFN[v]。

定義4回溯值(LOW)：一個(gè)節(jié)點(diǎn)或者它的子樹(shù)通過(guò)反向邊能到達(dá)的最小DFS時(shí)間戳。記節(jié)點(diǎn)v的回溯值為L(zhǎng)OW[v]。

Tarjan算法在一次深度優(yōu)先搜索過(guò)程中，得到所有節(jié)點(diǎn)的DFN和LOW值。利用以下規(guī)則判斷節(jié)點(diǎn)v的是否為割點(diǎn)：

1)v為根節(jié)點(diǎn)時(shí)v的子樹(shù)數(shù)量大于一顆?？梢岳斫鉃椋粢瞥摳?jié)點(diǎn)，則會(huì)產(chǎn)生多顆子樹(shù)，則圖便不再聯(lián)通。

2)v為非根節(jié)點(diǎn)，節(jié)點(diǎn)v存在一個(gè)子節(jié)點(diǎn)u使得節(jié)點(diǎn)v和節(jié)點(diǎn)u符合式(1)要求

DFN[v]≤LOW[u]

(1)

可以理解為從v的子節(jié)點(diǎn)u反向追溯，無(wú)法到達(dá)比 節(jié)點(diǎn)v更早被訪問(wèn)的節(jié)點(diǎn)。

圖2 Tarjan算法求取割點(diǎn)過(guò)程示意圖

Tarjan算法求取割點(diǎn)的過(guò)程如圖2所示，以節(jié)點(diǎn)e為DFS的根節(jié)點(diǎn)遍歷整個(gè)網(wǎng)絡(luò)的所有節(jié)點(diǎn)。圖中節(jié)點(diǎn)a為非根節(jié)點(diǎn)，它的子樹(shù)上節(jié)點(diǎn)b的回溯值LOW[b]大于等于a的時(shí)間戳DFN[a]，所以節(jié)點(diǎn)a為割點(diǎn)，同理節(jié)點(diǎn)d也為割點(diǎn)。

3 基于割點(diǎn)移除的節(jié)點(diǎn)重要性方法

本文對(duì)社交網(wǎng)絡(luò)重要節(jié)點(diǎn)的評(píng)估采用的是復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性排序的方法。在諸如話單網(wǎng)絡(luò)，朋友關(guān)系網(wǎng)絡(luò)等社交網(wǎng)絡(luò)中，通常需要得到一些重要的人物節(jié)點(diǎn)，這樣的人物節(jié)點(diǎn)通常具有核心的作用。在復(fù)雜網(wǎng)絡(luò)中最直觀的解釋是，一旦這樣的節(jié)點(diǎn)失去相應(yīng)的功能或者無(wú)法正常運(yùn)轉(zhuǎn)，會(huì)導(dǎo)致整個(gè)網(wǎng)絡(luò)受到較大的損傷。

實(shí)際上，由于割點(diǎn)的定義就是去掉后圖便不再連通，所以移除圖中的割點(diǎn)便能很好的破壞網(wǎng)絡(luò)的結(jié)構(gòu)。

而在一個(gè)圖中可能會(huì)有很多的割點(diǎn)，如何在這些割點(diǎn)中選擇“最好”的割點(diǎn)便是一個(gè)關(guān)鍵問(wèn)題。這里將“最好割點(diǎn)”定義為移除該割點(diǎn)后能使最大聯(lián)通分量規(guī)模減小最多的節(jié)點(diǎn)。筆者發(fā)現(xiàn)，通常這樣的節(jié)點(diǎn)具有較高的度中心性。度中心性的計(jì)算方式如式(2)所示

(2)

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

(3)

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

所以基于割點(diǎn)移除的節(jié)點(diǎn)重要性方法由以下幾個(gè)步驟組成：

1)構(gòu)建候選移除節(jié)點(diǎn)集合

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

AP={n|n∈V且n為割點(diǎn)}

(4)

2)獲得待移除節(jié)點(diǎn)

將當(dāng)前所有割點(diǎn)中具有度中心性最高的節(jié)點(diǎn)作為移除的節(jié)點(diǎn)，考慮到不是所有的圖都具有割點(diǎn)，因此若圖中無(wú)割點(diǎn)，則直接將該子圖中度中心性最高的節(jié)點(diǎn)作為移除節(jié)點(diǎn)。

圖3 割點(diǎn)移除過(guò)程示意圖

如圖3所示，移除割點(diǎn)a和割點(diǎn)d都可以破壞網(wǎng)絡(luò)的結(jié)構(gòu)，使網(wǎng)絡(luò)的最大聯(lián)通分量規(guī)模減少，但是，移除割點(diǎn)a后，最大聯(lián)通分量規(guī)模減少的更多，割點(diǎn)a比割點(diǎn)d更接近網(wǎng)絡(luò)的核心位置。通常，在具有多個(gè)割點(diǎn)的情況下，度中心性更高的節(jié)點(diǎn)更接近網(wǎng)絡(luò)的中心，所以在移除節(jié)點(diǎn)時(shí)優(yōu)先選擇度中心性更高的割點(diǎn)。移除節(jié)點(diǎn)的選擇如式(5)所示

(5)

其中AP為割點(diǎn)集，V為當(dāng)前子圖下節(jié)點(diǎn)集。

3)移除節(jié)點(diǎn)

移除步驟1)步得到的節(jié)點(diǎn)。得到不含有此節(jié)點(diǎn)子圖。

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

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

(6)

其中V’，E’分別表示移除節(jié)點(diǎn)后的節(jié)點(diǎn)集合與邊集合，ω(Nr)表示取Nr所有的連邊，其取值由以下公式?jīng)Q定

E′=E-ω(Nr)

(7)

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

(8)

4)更新當(dāng)前操作子圖

將移除節(jié)點(diǎn)后的圖中最大聯(lián)通分量作為新一輪移除的圖。

重復(fù)1)-4)直到整個(gè)圖中的最大聯(lián)通分量不再具有邊。

根據(jù)前文提到的步驟，本文所提出的節(jié)點(diǎn)重要度排序算法APRRank核心部分偽代碼如下所示。

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

Input：Graph

Output：節(jié)點(diǎn)排序以及評(píng)分 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 仿真研究

為評(píng)價(jià)基于割點(diǎn)移除節(jié)點(diǎn)重要性排序算法的有效性，本文在多個(gè)真實(shí)的，規(guī)模不一，差異較大的社交網(wǎng)絡(luò)中進(jìn)行了仿真，實(shí)驗(yàn)數(shù)據(jù)來(lái)自NR[13]提供的開(kāi)源社交關(guān)系網(wǎng)絡(luò)。

其中Caltech36，simmons81屬于Facebook網(wǎng)絡(luò)數(shù)據(jù)集，wiki-Vote數(shù)據(jù)集包含從維基百科建立到2008年1月的所有投票鏈接數(shù)據(jù)。Advogato是某社交平臺(tái)信任關(guān)系網(wǎng)絡(luò)。仿真相關(guān)統(tǒng)計(jì)指標(biāo)如下：

表1 仿真數(shù)據(jù)相關(guān)統(tǒng)計(jì)情況說(shuō)明

4.1 結(jié)果對(duì)比

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

表2(a) Caltech36與wiki-Vote網(wǎng)絡(luò)各方法排序結(jié)果

表2(b) simmons81與advogatos網(wǎng)絡(luò)各方法排序結(jié)果

各個(gè)方法排序側(cè)重的依據(jù)不同，所以排序的結(jié)果也存在一定的差異，以Caltech36網(wǎng)絡(luò)為例，排名第一的節(jié)點(diǎn)就產(chǎn)生了不同，除了APRRank其它的方法均為709，APRRank方法首先關(guān)注的是割點(diǎn)，在此網(wǎng)絡(luò)中的度中心性最高的割點(diǎn)為90號(hào)，因此將90號(hào)節(jié)點(diǎn)作為排名第一的節(jié)點(diǎn)，在移除90號(hào)節(jié)點(diǎn)后，產(chǎn)生了多個(gè)聯(lián)通分量，在新的最大聯(lián)通分量中再進(jìn)行對(duì)度中心性最高的割點(diǎn)便可得到223號(hào)節(jié)點(diǎn)。用APRRank排序是一個(gè)動(dòng)態(tài)的過(guò)程，所以后續(xù)的排列也會(huì)和其它方法有較大的不同。

4.2 魯棒性測(cè)試

為了具體衡量本文算法的效果，本文對(duì)上述網(wǎng)絡(luò)分別使用中心性方法，PageRank方法，TOPSIS方法，以及APRR算法對(duì)五個(gè)不同網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)魯棒性仿真。

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

(9)

其中G為當(dāng)前子圖，LC為當(dāng)前子圖最大聯(lián)通分量。

Swami等人[14]應(yīng)用4種不同的方法對(duì)節(jié)點(diǎn)進(jìn)行排序并繪制魯棒性測(cè)試曲線。繪制曲線可以準(zhǔn)確的得到依次移除這些節(jié)點(diǎn)對(duì)圖的影響過(guò)程，從而間衡量了節(jié)點(diǎn)重要性排序的效果?？v坐標(biāo)為最大聯(lián)通分量規(guī)模占比，橫坐標(biāo)為移除節(jié)點(diǎn)占比。若曲線降低的速度越快，則認(rèn)為網(wǎng)絡(luò)在移除相應(yīng)的節(jié)點(diǎn)后網(wǎng)絡(luò)功能衰減的越快，同時(shí)也就意味著這樣的節(jié)點(diǎn)重要性排序結(jié)果在魯棒性測(cè)試中效果越好。

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

圖6 Socfb-simmons81魯棒性曲線

圖7 Socfb-Caltech36魯棒性曲線

圖8 Soc-advogatos魯棒性曲線

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

5 結(jié)束語(yǔ)

本文提出了一種基于割點(diǎn)移除的社交網(wǎng)絡(luò)重要節(jié)點(diǎn)評(píng)估方法，對(duì)復(fù)雜網(wǎng)絡(luò)中最大聯(lián)通分量里的度數(shù)高并且具備割點(diǎn)角色的節(jié)點(diǎn)進(jìn)行了依次移除，并且按移除順序作為節(jié)點(diǎn)重要性的排序。在此基礎(chǔ)之上，本文對(duì)四個(gè)規(guī)模不一網(wǎng)絡(luò)進(jìn)行了魯棒性仿真，實(shí)驗(yàn)結(jié)果表明，按照本文所提出的APRRank方法依次攻擊相應(yīng)的節(jié)點(diǎn)，可以更快的破壞網(wǎng)絡(luò)的整體功能，讓網(wǎng)絡(luò)的破碎程度更大，證實(shí)了本文所提方法的有效性。

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