汪 宏,鮑中奎,張海峰

(安徽大學數(shù)學科學學院,合肥 230601)

基于標簽傳播識別網(wǎng)絡中的關鍵節(jié)點

汪 宏,鮑中奎,張海峰

(安徽大學數(shù)學科學學院,合肥 230601)

基于標簽傳播動力學提出了一種識別網(wǎng)絡關鍵節(jié)點的算法，主要思想是把每個節(jié)點接收到不同標簽的數(shù)量作為判斷節(jié)點重要性的指標。應用兩種不同的傳播模型，在不同網(wǎng)絡上與其它中心性指標作比較。結(jié)果表明：基于標簽傳播的中心性指標比其它的中心性方法可以更好地識別網(wǎng)絡中的關鍵節(jié)點。基于標簽傳播的中心性指標還具有以下優(yōu)勢：不需要利用網(wǎng)絡的結(jié)構(gòu)信息，因此可以推廣到大規(guī)模網(wǎng)絡上；揭示了一種現(xiàn)象——好的接收者往往也是好的傳播者。

復雜網(wǎng)絡；關鍵節(jié)點識別；標簽傳播算法

0 引言

面對大規(guī)模的網(wǎng)絡，能否有效識別其中具有影響力的關鍵節(jié)點，具有重要的理論意義和實際應用價值。選擇一個關鍵節(jié)點作為傳播源可以讓信息更加快速傳播、產(chǎn)品發(fā)布范圍更廣等，免疫了網(wǎng)絡中的關鍵節(jié)點，可以更好地防止疾病的蔓延和謠言的擴散等[1-5]。所以到目前為止已經(jīng)提出許多識別關鍵節(jié)點的方法，如：度中心性[6]、介數(shù)中心性[7]、接近中心性[8]、特征向量中心性[6]、k-核[9]以及各種改進的算法[10-14]。

雖然在識別網(wǎng)絡關鍵節(jié)點這個方向已經(jīng)取得了一定的成果，但對這個方向的研究依然是方興未艾。以前的算法都或多或少利用網(wǎng)絡的結(jié)構(gòu)信息，然后基于這些已知的結(jié)構(gòu)信息對節(jié)點的重要性進行排序。然而針對真實的大規(guī)模網(wǎng)絡，要獲取網(wǎng)絡完整的結(jié)構(gòu)信息相當困難，那么如何避免利用網(wǎng)絡的結(jié)構(gòu)信息而設計一種新的算法識別網(wǎng)絡中的關鍵節(jié)點是一個非常有意義的課題。在文獻[15]中，Zhu等人利用標簽傳播時間的信息來尋找網(wǎng)絡中的傳播源,而在文獻[16]，Liao等人基于標簽傳播時間定義節(jié)點的相似性，進而進行鏈路預測等。受此啟發(fā)，本文基于標簽傳播動力學提出了一種識別網(wǎng)絡中關鍵節(jié)點的算法，在該算法中節(jié)點的中心性指標通過節(jié)點獲取不同標簽的數(shù)量來衡量。針對Susceptible-Infected-Recovery(SIR)疾病傳播和謠言傳播兩者不同的傳播模型，在真實網(wǎng)絡和生成網(wǎng)絡上比較我們的中心性指標與幾個經(jīng)典的中心性指標。通過研究發(fā)現(xiàn)，相對于經(jīng)典的中心性指標本算法可以更好地識別網(wǎng)絡中的關鍵節(jié)點。同時本算法還有兩大優(yōu)勢：1)不需要利用網(wǎng)絡的結(jié)構(gòu)信息。因為每個節(jié)點在傳播標簽的時候，不需要知道哪些節(jié)點是自己的鄰居。類似于流行病傳播，每個感染節(jié)點即使不知道哪些人是自己的鄰居也可以把疾病傳播出去，因為只有鄰居才有可能被感染，不是鄰居不會被感染。也就是說，是否被傳播成功已經(jīng)蘊含著是否有可能是鄰居節(jié)點；2)揭示一個現(xiàn)象——易感染節(jié)點往往也是有影響力節(jié)點。因為本算法是通過收到不同標簽數(shù)量的多少來衡量節(jié)點的重要性，因此收到不同標簽數(shù)量越多就說明該節(jié)點也越容易被感染。

1 理論基礎與方法

1.1 標簽傳播動力學指標

假設網(wǎng)絡是一個無權(quán)無向網(wǎng)絡G(N,M)，其中N代表網(wǎng)絡中節(jié)點的數(shù)目，M代表網(wǎng)絡中邊的數(shù)目。從網(wǎng)絡中隨機選取比例為η(本文中η=0.1)的節(jié)點，每個被選中的節(jié)點各攜帶互不相同的標簽(攜帶標簽的節(jié)點數(shù)l取不大于ηN的最大整數(shù))，分別將標簽以概率ε傳播給它們的每個鄰居。當節(jié)點i收到鄰居節(jié)點j傳來的一個標簽時，節(jié)點i檢查是否接收過該標簽：如果沒有，則節(jié)點i接收該標簽并擁有該標簽，下一步可以再以概率ε將該標簽傳播給它的鄰居；如果節(jié)點i已經(jīng)接收過標簽，則不再接收該標簽。每個標簽之間的傳播是沒有關系的，不受彼此影響。同時對于每個標簽，每個節(jié)點最多只接收一次，也最多只向同一個鄰居傳出一次(無論是否被接收)。所以對于每個標簽傳播過程而言，類似于SIR傳播過程。等到網(wǎng)絡中每個標簽傳播過程停止，記錄節(jié)點i接收到不同的標簽數(shù)目為m(i)，把獨立重復t次平均后的m(i)作為i點的中心性指標，這就是本文所說的基于標簽傳播的中心性指標。本文中每個標簽的重復次數(shù)為t=100。

1.2 幾種中心性指標[2]

度中心性(Degree Centrality,DC)，被定義為節(jié)點的鄰居數(shù)目，即

(1)

介數(shù)中心性(Betweenness Centrality,BC)，是以經(jīng)過某個節(jié)點的最短路徑的數(shù)目來刻畫節(jié)點的重要性指標，即

(2)

k-shell方法(KS)的具體步驟如下：首先把網(wǎng)絡中度為1的節(jié)點及其所連接的邊去掉，剩下的網(wǎng)絡中會出現(xiàn)一些度為1的節(jié)點，再將這些度為1的節(jié)點去掉，直到所剩的網(wǎng)絡中沒有度為1的節(jié)點，則所有被去掉的節(jié)點稱為1-shell；然后繼續(xù)上面的方法，去掉剩下的網(wǎng)絡中度為2的節(jié)點及其相連的邊，直至不再有度值為2的節(jié)點為止，則這一輪所有被去除的節(jié)點稱為網(wǎng)絡的2-shell。依次類推，直到所有的節(jié)點都被分到相應的k-shell。

特征向量中心性(Eigenvector Centrality，EC)的基本思想是：一個節(jié)點的重要性既取決于其鄰居的數(shù)量(即該節(jié)點的度)，也取決于其鄰居節(jié)點的重要性。運用特征向量的性質(zhì)，可得每個節(jié)點的重要性對應于鄰接矩陣最大特征值對應的特征向量的分量。設λ1為網(wǎng)絡鄰接矩陣A的最大特征值，v為其對應的特征向量，則節(jié)點i的重要性EC(i)為向量v的第i個分量。

1.3 疾病傳播模型和謠言傳播模型

在以前的文獻中，通常利用SIR疾病傳播模型來反映節(jié)點的實際傳播能力[17]，然而如[18]所述，節(jié)點的影響力受到其上動力學的影響。文獻[18]指出，由于在謠言傳播中大度節(jié)點一旦被感染，它會很快導致它的鄰居變?yōu)橐阎?，因而大度?jié)點啟動了“防火墻”的作用，如果把這些節(jié)點作為傳播源反而不一定利用謠言傳播。因此在本文分別考慮兩種傳播動力學：疾病傳播的SIR模型和謠言傳播模型，進而更全面地反映節(jié)點的影響力。

在疾病傳播模型中，網(wǎng)絡中的節(jié)點分成3類：易感者(S)、感染者(I)和恢復者(R)[14]。易感者是沒有感染疾病且會被感染者感染到的節(jié)點，感染者是傳播疾病的節(jié)點，恢復者是被感染過但不傳播疾病的節(jié)點[17]。當一個感染者遇到一個易感者的時候，易感者以β的概率變?yōu)楦腥菊撸瑐鞑ネ曜约核械泥従雍?，感染者以ξ的概率變?yōu)榛謴驼?。在本文中，我們均令?1。當利用SIR疾病傳播模型刻畫節(jié)點i的實際傳播能力σ(i)時，選擇這個節(jié)點作為感染者，而其它節(jié)點都是未感染者。然后按照SIR機制進行傳播，當傳播過程結(jié)束，即網(wǎng)絡中不存在感染者，計算出恢復者占整個網(wǎng)絡節(jié)點的比例，獨立重復s次試驗，把s次的平均值作為節(jié)點i的實際傳播能力σ(i)，本文中取s=100。

在謠言傳播模型中也可以把網(wǎng)絡的節(jié)點分成3類：無知者(S)，傳播者(I)，已知者(R)。無知者是沒有聽到謠言且易被傳播者傳播到的節(jié)點，傳播者是傳播謠言的節(jié)點，已知者是知道謠言且不傳播謠言的節(jié)點。當一個傳播者遇到一個無知者的時候無知者以β的概率變?yōu)閭鞑フ?。不同于疾病傳播的是：當一個傳播者接觸另一個傳播者或已知者時，最初的傳播者自身以ξ的概率變?yōu)橐阎撸藱C制是為了反映當傳播者的鄰居已經(jīng)已知此謠言時，傳播者就會失去傳播的興趣自身變?yōu)橐阎遊18]。在本文中，我們也令ξ=1。當利用謠言傳播模型刻畫節(jié)點i的影響力時，僅i自身是傳播者，而其它節(jié)點都是無知者，然后按照謠言傳播機制進行傳播。其它類似疾病傳播模型。

1.4 肯德爾相關系數(shù)

為了描述各種中心性指標識別有影響力的關鍵節(jié)點的能力，文中使用肯德爾相關系數(shù)來衡量。設有兩個集合X和Y，任意兩個節(jié)點對(xi,yi)和(xj,yj),如果滿足：xi>xj且yi≥yj或者xixj且yi≤yj或者xi

(3)

其中,n1為匹配一致的節(jié)點對數(shù)目，n2為匹配不一致的節(jié)點對數(shù)目，N為網(wǎng)絡的節(jié)點數(shù)[19]。計算節(jié)點各種中心性指標與節(jié)點實際傳播能力的匹配情況，τ值越大，說明匹配情況越好，進而說明該指標越能描述節(jié)點的中心性。

2 數(shù)值仿真

2.1 實驗數(shù)據(jù)及相關參數(shù)

為了說明本文算法的優(yōu)勢,我們在6個真實網(wǎng)絡上做了實驗,包括Email,TAP,Yeast,Power,Router,Internet，表1是網(wǎng)絡的一些參數(shù)[20]。其中，N是網(wǎng)絡的節(jié)點總數(shù)，M是邊的總數(shù)?！磌〉是網(wǎng)絡的平均度。C和r分別是網(wǎng)絡的聚類系數(shù)和同配系數(shù)。H=〈k2〉/〈k〉2是網(wǎng)絡的異質(zhì)性。βc=〈k〉/〈k2〉是傳播閾值。

表1 不同實際網(wǎng)絡的基本結(jié)構(gòu)信息Tab.1 Basic structural properties

2.2 主要結(jié)果

為了比較各種指標識別節(jié)點重要性的能力，先計算出每個節(jié)點i的實際傳播能力σ(i)(也即是以這個節(jié)點作為傳染源，以SIR疾病傳播或者謠言傳播進行，看最終傳播的范圍)，并根據(jù)這些節(jié)點實際傳播能力值進行從大到小排序。再根據(jù)各種中心性指標對網(wǎng)絡節(jié)點也進行從大到小排序，進而計算各種指標值與實際傳播能力值的肯德爾相關系數(shù)，如果某個中心性指標與實際傳播值越匹配則肯德爾相關系數(shù)值就越大，因此肯德爾相關系數(shù)值的大小可以反映某種中心性指標的優(yōu)劣性。標簽傳播率選擇太小則標簽很難在網(wǎng)絡中傳開，選擇太大則導致每個節(jié)點都能收到每個標簽，從而導致該指標的識別率不高，如圖1和圖2所示，本文選擇標簽傳播率ε=0.1,0.2和0.3進行對比，總體來看，取ε=0.2效果比較明顯。

首先用SIR疾病傳播模型來計算節(jié)點的實際傳播能力，然后在真實網(wǎng)絡上比較了基于標簽傳播的中心性指標(Label Spreading Centrality,簡寫為LC。其中LC1,LC2和LC3分別對應ε=0.1,0.2和0.3的情況)和幾個經(jīng)典的中心性指標：度中心性指標,介數(shù)中心性指標，特征向量中心性以及K-shell分解，實驗結(jié)果如圖1所示。圖中的虛線表示疾病傳播閾值βc，如表1所示。對于Power網(wǎng)絡，由于其傳播閾值βc>0.2，所以插圖顯示了β從0到0.4的情況。

圖1 對于SIR疾病傳播模型，不同的中心性指標下肯德爾相關系數(shù)τ與疾病傳播率β的關系Fig.1 For SIR epidemic model and different indices, the values of τ as a function of the transmission rate β are implemented in six real networks

圖1給出了德爾相關系數(shù)τ與疾病傳播率β的函數(shù)關系，從圖1可以發(fā)現(xiàn)：針對SIR疾病傳播模型，當傳播率β大于傳播閾值(圖中虛線所示)的時候，不管ε=0.1,0.2或者0.3，基于標簽傳播的中心性指標可以更好地刻畫節(jié)點的實際傳播能力，即節(jié)點的重要性。當傳播率β小于傳播閾值的時候疾病很難傳播出去，導致很多節(jié)點都沒有被感染，因此節(jié)點的實際傳播能力無法刻畫。對于Power網(wǎng)絡，由于它的傳播閾值大于0.2，所以在插圖中顯示了β從0增加到0.4的情況。如插圖所示，當傳播率β大于傳播閾值的時候，基于標簽的算法又優(yōu)于其他中心性指標。圖中的虛線表示疾病傳播閾值βc，如表1所示。對于Power網(wǎng)絡，由于其傳播閾值βc>0.2，所以插圖顯示了β從0到0.4的情況。

進一步在圖2中以謠言傳播動力學來刻畫節(jié)點的實際傳播能力，然后考慮德爾相關系數(shù)τ隨著謠言傳播率β的變化情況。通過比較發(fā)現(xiàn)，基于標簽傳播中心性指標也明顯優(yōu)于其它4種中心性指標。而且總體而言介數(shù)中心性指標對于識別網(wǎng)絡關鍵節(jié)點的能力最不理想。圖1和圖2的結(jié)果也表明：基于標簽傳播的中心性不僅僅對于與標簽傳播機理類似的疾病傳播模型具有很好地識別關鍵節(jié)點的能力，對于謠言傳播模型同樣可以有效地識別關鍵節(jié)點。

圖2 對于謠言傳播模型，不同的中心性指標下肯德爾相關系數(shù)τ與疾病傳播率β的關系。Fig.2 For rumor spreading model and different indices, the values of τ as a function of the transmission rate β are implemented in six real networks

另外，本文也在節(jié)點數(shù)N=2 000，平均度〈k〉=8的隨機ER網(wǎng)絡[21]和BA網(wǎng)絡[22]上進行比較，圖3a和圖3b分別是SIR疾病傳播與謠言傳播在ER網(wǎng)絡上的結(jié)果，而圖3c和圖3d分別是SIR疾病傳播和謠言傳播在BA網(wǎng)絡上的結(jié)果。由于K-shell分解方法在BA網(wǎng)絡上會導致所有節(jié)點分到同一個層中，所以在生成網(wǎng)絡上我們不和KS算法進行比較?；谡鎸嵕W(wǎng)絡中標簽傳播率在0.2時總體效果較好，在此將LC指標傳播率ε固定為0.2。從圖3可以發(fā)現(xiàn)：總體而言，在SIR疾病傳播和謠言傳播模型中，基于標簽傳播的中心性指標在識別關鍵節(jié)點能力方面要優(yōu)于度中心、介數(shù)中心性以及特征向量中心性(圖3d中的特征向量中心性效果更好)指標。因而進一步證實了我們算法的優(yōu)越性。圖3a和3c是SIR疾病傳播模型下各種中心性指標的對比;3b和3d謠言傳播模型下各種中心性指標的對比。圖3a和3b的隨機網(wǎng)絡上進行實驗的結(jié)果；3c和3d是BA網(wǎng)絡上進行實驗的結(jié)果。網(wǎng)絡規(guī)模N=2 000，〈k〉=8。虛線代表傳播閾值。

最后在圖4、圖5和圖6分別比較了LC指標與DC指標、KS指標以及與EC指標的相關性，其中LC指標中的傳播率ε固定為0.2。從圖4、圖5和圖6可以看出，LC指標與DC指標、KS指標以及EC指標有正相關關系，但相關性比較弱。比如DC、KS、EC值大的節(jié)點，其LC值不一定也很大；反過來，LC相同的值可能有不同的DC值、KS值以及EC值。因此基于標簽傳播的中心性指標可以從另外一個角度反應節(jié)點的傳播能力。

圖3 各種中心性指標在生成網(wǎng)絡上的比較Fig.3 The comparison of different indices on synthetic networks

圖4 在6個真實網(wǎng)絡中，度中心性指標 (DC)與基于標簽傳播指標(LC)的相關性Fig.4 The correlation between DC index andLC index is analyzed on six real networks

圖5 在6個真實網(wǎng)絡中，K-shell中心性指標 (KS)與基于標簽傳播指標(LC)的相關性Fig.5 The correlation between KS index andLC index is analyzed on six real networks

圖6 在6個真實網(wǎng)絡中，特征向量中心性指標 (KS)與基于標簽傳播指標(LC)的相關性Fig.6 The correlation between EC index andLC index is analyzed on six real networks

3 結(jié)語

本文基于標簽傳播動力學提出了一種識別網(wǎng)絡關鍵節(jié)點的方法，在該方法中，節(jié)點的重要性通過節(jié)點收到不同標簽數(shù)量的多少來衡量。不同于以往的算法，該算法不需要知道網(wǎng)絡的結(jié)構(gòu)信息。通過研究表明，無論是針對SIR的疾病傳播模型還是謠言傳播模型，該算法都能很好地識別網(wǎng)絡中的關鍵節(jié)點。因此我們的算法也表明易感染節(jié)點往往也是重要節(jié)點。本文僅僅考慮無向無權(quán)的網(wǎng)絡，針對有權(quán)網(wǎng)絡可以把權(quán)重引入到傳播率中進而推廣我們的模型，而對于有向網(wǎng)絡，我們可以首先改變網(wǎng)絡中所有邊的方向然后進行標簽傳播，那么收到不同標簽數(shù)目多的節(jié)點也很可能就是傳播能力強的節(jié)點。

[1]Newman M E J. Networks: an Introduction[M]. Oxford: Oxford University Press, 2010.

[2]呂琳媛, 陸君安, 張子柯, 等. 復雜網(wǎng)絡觀察[J]. 復雜系統(tǒng)與復雜性科學, 2010, 7(2): 173-186. Lü LinYuan, Lu JunAn, Zhang ZiKe, et al. Looking into complex networks[J]. Complex Systems and Complexity Science, 2010, 7(2): 173-186.

[3] 劉建國，任卓明，郭強，等.復雜網(wǎng)絡中節(jié)點重要性排序的研究進展[J]. 物理學報，2013，62(17):178901. Liu JianGuo, Ren ZhuoMing, Guo Qiang, et al. Node importance ranking of complex networks[J]. Acta Phys Sin, 2013, 62(17): 178901.

[4] 任曉龍,呂琳媛.網(wǎng)絡重要節(jié)點排序方法綜述[J]. 科學通報，2014， 59(13):1175-1197. Ren XiaoLong, Lü Lin Yuan. Review of ranking nodes in complex networks[J]. Chin Sci Bull (Chin Ver), 2014, 59: 1175-1197.

[5] Lü L Y, Chen D B, Ren X L, et al. Vital nodes identification in complex networks[J]. Physics Reports, 2016, 650: 1-63.[6] Bonacich P. Factoring and weighting approaches to status scores and clique identification[J]. Journal of Mathematical Sociology,1972, 2(1): 113-120.

[7] Freeman L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40: 35-41.

[8] Freeman L C. Centrality in social networks conceptual clarification[J]. Soc Netw, 1979, 1: 215-239.

[9] Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks[J]. Nat Phys, 2010, 6: 888-893.

[10] Chen D B, Lü L, Shang M S, et al. Identifying influential nodes in complex networks[J]. Physica A, 2012, 391: 1777-1787.

[11] Ma L L, Ma C, Zhang H F, et al. Identifying influential spreaders in complex networks based on gravity formula[J]. Physica A, 2016, 45: 1205-1212.

[12] Liu Y, Tang M, Zhou T, et al. Improving the accuracy of the k-shell method by removing redundant links: from a perspective of spreading dynamics[J].Scientific Reports, 2015, 5: 13172.

[13] Zeng A, Zhang C J. Ranking spreaders by decomposing complex networks[J].Physics Letters A, 2013, 377(14): 1031-1035.

[14] 舒盼盼, 王偉, 唐明, 等. 花簇分形無標度網(wǎng)絡中節(jié)點影響力的區(qū)分度[J]. 物理學報, 2015, 64(20): 208901. Shu Panpan, Wang Wei, Tang Ming, et al. Discriminability of node influence in flower fractal scale-free networks[J]. Acta Physica Sinica, 2015, 64(20): 208901.

[15] Kai Z, Lei Y. Information source detection in the SIR model: a sample path based approach[J]. IEEE/ACM Transactions on Networking, 2016, 24(1): 408-421.

[16] Liao H, Zeng A. Reconstructing propagation networks with temporal similarity[J].Scientific Reports, 2015, 5: 11404.

[17] 李睿琪，王偉，舒盼盼， 等. 復雜網(wǎng)絡上流行病傳播動力學的爆發(fā)閾值解析綜述[J]. 復雜系統(tǒng)與復雜性科學， 2016, 13(1): 1-39. Li RuiQi, Wang Wei, Shu PanPan, et al. Review of threshold theoretical analysis about epidemic spreading dynamics on complex networks[J]. Complex Systems and Complexity Science, 2016, 13(1): 1-39.

[18] Borge-Holthoefer Y, Moreno Y. Absence of influential spreaders in rumor dynamics[J]. Physical Review E, 2012, 85(2): 026116.

[19] Zhou T, Lü L Y, Zhang Y C. Predicting missing links via local Information[J].The European Physical Journal B, 2009, 71(4): 623-630.

[20] 呂琳媛，周濤. 鏈路預測[M]. 上海：高等教育出版社，2014.

[21] Erdos P, Renyi A. On the evolution of random graphs[J]. Publications of the Mathematical Institute of the Hungarian Academy of Sciences. 1960, 5: 17-61.

[22] Barabasi A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.

(責任編輯 耿金花)

Identifying Influential Nodes in Complex Networks Based on the Label Spreading Dynamics

WANG Hong, BAO Zhongkui, ZHANG Haifeng

(School of Mathematical Science, Anhui University, Hefei 230601, China)

In this paper, based on the label spreading dynamics, we propose a centrality index to identify influential nodes in complex networks, where the influence of a node is measured by how many different labels who have

. Under different spreading models, we compare our index with several traditional centrality indices in different networks, our results indicate that the performance of our index is better than others. Moreover, there are two typical advantages: 1), our algorithm does not use the structure information of networks, so which can be generalized to large-scale networks; 2), our algorithm implies a conclusion-a good receiver is also a good spreader.

complex networks; influential nodes; label spreading dynamics

1672-3813(2017)02-0019-07；

10.13306/j.1672-3813.2017.02.003

2016-08-29；

2016-10-11

國家自然科學基金(61473001), 博士啟動資金(01001951)

汪宏(1990-),男,安徽池州人,碩士研究生,主要研究方向為復雜網(wǎng)絡上的關鍵點識別。

鮑中奎(1982-),男，安徽合肥人，博士，講師，主要研究方向為復雜網(wǎng)絡科學。

N94

A