基于標(biāo)簽傳播識(shí)別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)

汪 宏,鮑中奎,張海峰

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

基于標(biāo)簽傳播識(shí)別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)

汪 宏,鮑中奎,張海峰

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

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

復(fù)雜網(wǎng)絡(luò)；關(guān)鍵節(jié)點(diǎn)識(shí)別；標(biāo)簽傳播算法

0 引言

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

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

1 理論基礎(chǔ)與方法

1.1 標(biāo)簽傳播動(dòng)力學(xué)指標(biāo)

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

1.2 幾種中心性指標(biāo)[2]

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

(1)

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

(2)

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

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

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

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

在疾病傳播模型中，網(wǎng)絡(luò)中的節(jié)點(diǎn)分成3類：易感者(S)、感染者(I)和恢復(fù)者(R)[14]。易感者是沒有感染疾病且會(huì)被感染者感染到的節(jié)點(diǎn)，感染者是傳播疾病的節(jié)點(diǎn)，恢復(fù)者是被感染過但不傳播疾病的節(jié)點(diǎn)[17]。當(dāng)一個(gè)感染者遇到一個(gè)易感者的時(shí)候，易感者以β的概率變?yōu)楦腥菊?，傳播完自己所有的鄰居后，感染者以ξ的概率變?yōu)榛謴?fù)者。在本文中，我們均令ξ=1。當(dāng)利用SIR疾病傳播模型刻畫節(jié)點(diǎn)i的實(shí)際傳播能力σ(i)時(shí)，選擇這個(gè)節(jié)點(diǎn)作為感染者，而其它節(jié)點(diǎn)都是未感染者。然后按照SIR機(jī)制進(jìn)行傳播，當(dāng)傳播過程結(jié)束，即網(wǎng)絡(luò)中不存在感染者，計(jì)算出恢復(fù)者占整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的比例，獨(dú)立重復(fù)s次試驗(yàn)，把s次的平均值作為節(jié)點(diǎn)i的實(shí)際傳播能力σ(i)，本文中取s=100。

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

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

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

(3)

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

2 數(shù)值仿真

2.1 實(shí)驗(yàn)數(shù)據(jù)及相關(guān)參數(shù)

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

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

2.2 主要結(jié)果

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

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

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

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

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

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

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

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

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

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

3 結(jié)語

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

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

[2]呂琳媛, 陸君安, 張子柯, 等. 復(fù)雜網(wǎng)絡(luò)觀察[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 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] 劉建國，任卓明，郭強(qiáng)，等.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性排序的研究進(jìn)展[J]. 物理學(xué)報(bào)，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)絡(luò)重要節(jié)點(diǎn)排序方法綜述[J]. 科學(xué)通報(bào)，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] 舒盼盼, 王偉, 唐明, 等. 花簇分形無標(biāo)度網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的區(qū)分度[J]. 物理學(xué)報(bào), 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] 李睿琪，王偉，舒盼盼， 等. 復(fù)雜網(wǎng)絡(luò)上流行病傳播動(dòng)力學(xué)的爆發(fā)閾值解析綜述[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 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] 呂琳媛，周濤. 鏈路預(yù)測[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.

(責(zé)任編輯 耿金花)

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

國家自然科學(xué)基金(61473001), 博士啟動(dòng)資金(01001951)

汪宏(1990-),男,安徽池州人,碩士研究生,主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)上的關(guān)鍵點(diǎn)識(shí)別。

鮑中奎(1982-),男，安徽合肥人，博士，講師，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)科學(xué)。

N94

A