楊 雄 黃德才 詹秀秀 張子柯

(*浙江工業(yè)大學 計算機科學與技術學院、軟件學院 杭州 310023) (**常州工學院 計算機信息工程學院 常州 213002) (***杭州師范大學 阿里巴巴復雜科學研究中心 杭州 311121)

?

探測和評估復雜網絡影響力節(jié)點的路徑多樣性核度中心方法①

楊 雄②***黃德才③*詹秀秀***張子柯***

(*浙江工業(yè)大學 計算機科學與技術學院、軟件學院 杭州 310023) (**常州工學院 計算機信息工程學院 常州 213002) (***杭州師范大學 阿里巴巴復雜科學研究中心 杭州 311121)

針對當前復雜網絡影響力節(jié)點探測和評估方法不能精確定位影響力節(jié)點、計算復雜等不足，在傳統(tǒng)網絡K核分解方法的基礎上引入了路徑多樣性概念，從信息傳播角度進行了研究，提出了一種基于路徑多樣性信息熵進行影響力節(jié)點探測與評估的新的核度中心方法，即路徑多樣性核度中心(Cncd)方法。實驗結果顯示，相對于其他影響力節(jié)點探測與評估方法，如度中心法(CD)、介數中心法(CB)、接近中心法(CC)、K核中心法(KC)及核度中心法(Cncd)，Cncd方法能夠更精確地對影響力節(jié)點進行定位，并且能更細粒度地對節(jié)點影響力進行有效排序。

節(jié)點影響力， 度中心， 介數中心， 接近中心，K核分解

0 引 言

近年來對以社會網絡、計算機網絡、生物網絡、管理網絡為代表的復雜網絡科學的研究日益受到重視。挖掘和探測復雜網絡系統(tǒng)中的影響力節(jié)點已成為研究復雜網絡結構和動力學機制的基本方式，如何高效和準確地探測出網絡影響力節(jié)點已經成為復雜網絡研究領域的熱點方向之一。網絡影響力節(jié)點的挖掘和探測技術已經在包括傳染病疫情控制[1]、信息傳播[2]、市場廣告投放[3]、社會網絡領袖[4]、學術網絡評級[5]等領域產生了重要的理論和實際應用價值。然而當前網絡影響力節(jié)點的探測和挖掘技術存在明顯不足，例如高連接度方法和傳統(tǒng)的網絡K核分解方法不能很好地精確定位影響力節(jié)點，介數中心方法和接近中心方法雖能夠較準確定位，但計算復雜，不適用于大規(guī)模復雜網絡。針對這種情況，本文提出了一種基于路徑多樣性的網絡節(jié)點影響力探測和評估方法，該方法既考慮了節(jié)點核度，同時也考慮了路徑多樣性對復雜網絡節(jié)點的影響力，能夠更有效地對關鍵節(jié)點進行定位和更細粒度地對節(jié)點影響力進行有效的排序。本文將這種方法叫做路徑多樣性核度中心(Cncd)方法。

1 相關研究

傳統(tǒng)的網絡影響力節(jié)點探測評估方法通常采用節(jié)點的連接度屬性來衡量度中心(degree centrality,CD)，方法較為簡單，計算工作量較小，但忽視了網絡的全局結構，片面地關注于節(jié)點的局部屬性，因此準確度并不高。Freeman[6]和Sabidussi[7]提出了非常著名且使用廣泛的介數中心(betweenness centrality,CB)方法和接近中心(closeness centrality,CC)方法，這兩種方法很好地解決了度中心方法不能處理的全局問題，具有較好的探測效果，但是由于網絡規(guī)模的迅速擴大，這兩種全局中心探測方法的計算將會非常耗時，因此并不適用于較大規(guī)模網絡。2012年Chen[8]提出了一種半局部的節(jié)點探測方法，該方法不僅考慮了節(jié)點的連接度而且還考慮了鄰居的連接度屬性，這樣做的優(yōu)勢在于一定程度上考慮了網絡的全局結構又借鑒了度中心計算簡單的特點，解決了全局中心計算復雜性的問題。

最近，Kitsak[9]提出了一種K核分解(K-core decomposition)方法，他發(fā)現很多具有高連接度和高介數中心的節(jié)點往往并不一定能夠對網絡中的信息傳播起到決定作用，恰恰相反，實驗發(fā)現能夠對信息傳播起到重要作用的節(jié)點通常位于網絡核心位置。K核分解首先刪除圖G中所有連接度為1的節(jié)點及他們所有的邊，若剩余節(jié)點中仍有度值為1的點繼續(xù)將他們刪除，將這些刪除的節(jié)點劃入核層為1的核中(本文用kc表示節(jié)點的核層)；其次對剩余連接度為2的節(jié)點重復上面步驟，將它們劃入核層為2的核中(kc=2)；最后該過程一直循環(huán)下去直到所有節(jié)點均被刪除且分配了相對應的核層數kc。

然而K核中心(K-core centrality,CKC)法也有一定的局限性，比如這種方法經常會將具有不同傳播能力的節(jié)點劃入同一個核層，或者說同一核層中的不同節(jié)點往往對信息的傳播具有不同的重要性。針對這個問題，2013年Basaras[10]提出了一種融合介數中心和核層分解的綜合方法，該方法較好地彌補了傳統(tǒng)K核分解的不足之處。同年，Zeng[11]針對傳統(tǒng)K核中心方法只關注于節(jié)點核內連接度而不考慮核外連接度屬性的缺點，提出了一種混合度分解的節(jié)點中心評估算法，Liu[12]根據節(jié)點與網絡最大核層中核心節(jié)點的距離來給出待評測節(jié)點的影響力，指出與網絡核心距離越近的節(jié)點影響力越大的觀點，但是該方法由于需要計算距離仍然會導致較大的計算復雜性。

值得注意的是，2014年韓國慶北大學[13]的研究小組首次提出了一種基于節(jié)點核度中心(neighborhood core centrality，Cnc)的影響力評估方法，該工作給出的節(jié)點核度概念可以理解為該節(jié)點所有鄰居所處的網絡核層數之和，核度概念的提出一方面考慮了節(jié)點所處的網絡位置，同時也考慮了節(jié)點外部鄰域的信息。該方法解決了網絡邊緣連接度大的節(jié)點沒有獲得合理評估的缺陷，由于這種方法將注意力集中在節(jié)點的局部屬性——連接度，因此具有較好的計算效率。

但是在很多場合中僅用核度的概念并不能很好地解決節(jié)點影響力的判斷問題。如圖1所示，在該網絡中節(jié)點1、2、3、22均位于網絡中心核層3中(kc=3)，而其他節(jié)點均位于核層1中(kc=1)。當使用傳統(tǒng)的K核分解時并不能判斷出這4個節(jié)點之間的影響力有何差異，而使用文獻[13]中提出的核度方法，因為節(jié)點1和2的核度等于12，節(jié)點3和22的核度等于9，則可以得知節(jié)點1和2的影響力大于節(jié)點3和22。從圖1中可以非常明確地看出，由于節(jié)點1和2外連著核層1中所有的節(jié)點，因此這兩個節(jié)點的影響力將遠遠大于節(jié)點3和22。但是核度方法在判斷出節(jié)點1和2的影響力大于同核中的節(jié)點3和22后并不能對彼此進行更為細致的影響力判斷。由于兩者核度相同，節(jié)點1和2會被認為具有同等重要的地位。然而可以發(fā)現，雖然節(jié)點1和節(jié)點2各自外連著核層1中數量等同的3個鄰居節(jié)點和6個2級鄰居節(jié)點(節(jié)點1連著4～6和10～15，節(jié)點2連著7～9和16～21)，但是由于節(jié)點2將信息傳往核層為1的2級鄰居節(jié)點的路徑均 重疊于節(jié)點7，因此節(jié)點7和節(jié)點2之間路徑的狀態(tài)對于節(jié)點2來說對整個信息的傳遞具有非常重要的作用，如果該路徑崩潰則對于節(jié)點2來說能夠傳遞的節(jié)點數只有2個(節(jié)點8和9)。而對于節(jié)點1而言由于路徑多樣性、同樣將信息傳給核層為1的節(jié)點時，節(jié)點4、5、6和節(jié)點1之間同等情況任意單條路徑的崩潰卻仍然能夠保證信息可以到達其余6個節(jié)點(2個鄰居節(jié)點、4個2級鄰居節(jié)點)，即相對于節(jié)點2而言同等路徑損壞條件下節(jié)點1更容易使得信息傳播出去，因此具有更重要的傳播影響力。

圖1 路徑多樣性的網絡核度示意圖

從上述討論中可以看到，單純依靠K核分解和核度計算并不總能對網絡節(jié)點影響力進行合理的評估，實際上路徑的多樣性也將對節(jié)點影響力評估產生深刻的影響。本文另辟蹊徑，在考慮節(jié)點核度的同時引入路徑多樣性概念來研究復雜網絡節(jié)點的影響力，相對于介數中心方法和接近中心方法需要全局屬性、不適合大規(guī)模網絡的缺點，本文方法具有聚焦于節(jié)點的局部屬性、計算簡單的優(yōu)點。實驗結果顯示，路徑多樣性核度評估方法相對于其他方法更能夠準確地評估節(jié)點影響力，同時對網絡信息傳播的高效性也有著重要的作用。

2 節(jié)點影響力評估方法描述

傳統(tǒng)的網絡節(jié)點影響力評估大都利用圖論中割點、割邊等概念對網絡拓撲進行研究，而以社會網絡為代表的復雜網絡對節(jié)點影響力評估大都借助其結構屬性和信息傳播動力學模型進行度量。G=(V,E)表示一個無權無向網絡圖，節(jié)點數n=|V|，借助已有研究成果對任意節(jié)點i的影響力評估指標表示如下：度中心(CD(i))、介數中心(CB(i))[6]、接近中心(CC(i))[7]、K核中心(CKC(i))[9]、核度中心(Cnc(i))[13]。

2.1 路徑信息熵的節(jié)點影響力計算

目前大多數研究工作都集中于利用局部信息如節(jié)點的度進行影響力評估，而本文采用核度中心評估方法并引入路徑多樣性的概念來提高節(jié)點影響力判斷的準確性和高效性。

步驟1 任意節(jié)點的路徑多樣性問題均可通過其鄰居節(jié)點連接度的不均衡性進行有效表達，本文采用信息熵[14]方法對任意節(jié)點i的路徑多樣性進行定量描述。

定義hi為節(jié)點i的路徑多樣性信息熵，N(i)為節(jié)點i的鄰居集合，j為節(jié)點i的鄰居(j∈N(i))，kj為節(jié)點j的連接度，pj為節(jié)點j的度占i所有鄰居節(jié)點度之和的百分比，公式如下：

(1)

hi值越大表明節(jié)點i的鄰居節(jié)點連接越均衡，也就是節(jié)點i的信息傳播路徑越多樣化，在隨機傳播時感染能力越強。

步驟2 對式(1)進行標準化處理得到公式

(2)

步驟3 在傳統(tǒng)度中心評估方法基礎上考慮鄰居節(jié)點的度來提升影響力評估的準確性，文獻[8，15]提出了節(jié)點i改進后的度中心評估指標如下式所示：

(3)

其中λ為可調參數。鑒于該思想，我們在核度中心評估方法Cnc基礎上考慮了節(jié)點鄰域信息，并且

圖2 節(jié)點路徑多樣性信息熵示意圖

引入路徑多樣性參數Hi，提出了節(jié)點i的一種路徑多樣性核度中心評估方法Cncd(i)(neighborhood core diversity centrality)和核度中心評估方法(Cnc)[13]和路徑多樣性核度中心評估方法公式如下：

(4)

其中CKC(i)表示經過K核分解后節(jié)點i所處的核層。

步驟4 遍歷網絡中各個節(jié)點，計算它們的路徑多樣性核度中心評估值Cncd(i)，并根據該值從大到小排序，即為節(jié)點的影響力排序。

下面以圖1的小規(guī)模樣本網絡為例，分別利用各種影響力評估方法(CD(i)、CB(i)、CC(i)、CKC(i)、Cnc(i)及Cncd(i))對節(jié)點影響力進行評估及排序。表1顯示了不同影響力評估方法排序的結果(λ=2)，可以看到有些評估方法同一位次上具有多個節(jié)點，因此采用一種優(yōu)化方法進行細粒度排序劃分就顯得非常重要；如利用核度中心方法Cnc評估在第一的節(jié)點1和2在改進后的路徑多樣性核度中心方法Cncd中進行了更細粒度的排序；同時利用度中心法CD排在第三位序的節(jié)點3、4、5、6和22也在路徑多樣性核度中心方法中進行了不同順序的劃分。表2顯示了節(jié)點1-7和節(jié)點22這8個重要節(jié)點在不同影響力評估方法中的計算值。

表1 不同影響力中心評估方法下的節(jié)點排序

表2 不同影響力中心評估方法下的節(jié)點數值

2.2 節(jié)點傳播信息的定義

影響力傳播節(jié)點對信息傳播具有促進作用，這里借鑒經典傳染病SI(susceptible infection)模型定義信息傳播過程。任意節(jié)點的狀態(tài)只有2個：感染(接收)狀態(tài)和未感染(未接收)狀態(tài)。

設t表示信息在網絡中傳播的輪次，V1(i,t)表示在t時刻被源點Vi感染的節(jié)點集合，V1(i,0)={Vi}表示t=0初始時刻感染節(jié)點只有Vi，V0(i,0)={V1,V2,V3,…,Vi-1,Vi+1,Vi+2,…,Vn}表示初始時刻未感染節(jié)點集合。規(guī)定節(jié)點一旦感染將從集合V0中刪除并被放入集合V1且V1中節(jié)點不可重新回到集合V0。當第t輪次(步)傳播時，遍歷V1(i,t-1)集合中每個節(jié)點及它們的未被感染鄰居節(jié)點，令?Vp∈V1(i,t-1); Vq={N(Vp)∈V0(i,t-1)}，針對每個Vp隨機選擇l個Vq中的節(jié)點將他們放入V1(i,t)集合，同時從V0(i,t-1)刪除這l個節(jié)點生成新的V0(i,t)集合。令f(Vi,t)表示節(jié)點Vi在t時刻的傳播影響力，也就是信源在經過t輪次(步)后能將信息感染傳播給網絡節(jié)點的總數，f(Vi,t)=|V1(i,t)|。

2.3 路徑信息熵對節(jié)點影響力評估的意義

3 實驗結果分析

3.1 實驗網絡拓撲數據

實驗過程中使用2個真實網絡進行結果分析，分別為Gleiser[17]的爵士音樂家網絡(Jazz)和Duch[18]的細胞代謝網絡(C.elegans metabolic network)，兩個網絡基本拓撲特性如表3所示。

表3 兩個實驗網絡的拓撲數據

從表3中可以看到Jazz網絡的節(jié)點個數比C.elegans網絡少了將近一半但邊數反而更多，這個現象說明該網絡節(jié)點之間的聯系較為緊密(簇系數更大)，同配系數相對C.elegans網絡更大說明Jazz網絡中同類節(jié)點易于互連，這個現象也符合社交網絡的實際規(guī)律。

3.2 實驗結果分析

從兩個角度對實驗結果進行分析：(a)采用2.2節(jié)所述傳播模型比較評估結果與節(jié)點實際傳播效果之間的關系，判斷不同方法的有效性；(b)使用SI模型和獨立級聯模型IC[19](independent cascade model)比較不同方法選取差異節(jié)點的信息傳播效果。實驗平臺為Intel Core i3-2348M、4G的Win7系統(tǒng)，編程環(huán)境為R 3.1-win。

(a)排序結果與實際傳播影響力的關系

依次遍歷網絡中每個節(jié)點Vi作為單獨的初始傳播源，在指定時間(t=5)計算該節(jié)點的實際傳播能力f(Vi,t=5)。圖3顯示了不同評估方法在2個網絡中與節(jié)點實際傳播影響力f之間的關系。從圖3(a)～(d)，(g)～(j)可以看到度中心方法和接近中心方法的臨近節(jié)點之間傳播影響力差異較大，因此散點圖分布發(fā)散且不隨評估值呈現單調遞增趨勢；介數中心方法和K核中心方法不能對相同評估值(橫坐標值)的節(jié)點實際影響力進行有效區(qū)分，而 且可以看到隨著介數中心值的增加，一些節(jié)點的傳播影響力也并非呈現遞增趨勢，可見傳統(tǒng)的度中心、接近中心、介數中心、K核中心方法均不能對節(jié)點影響力進行細粒度區(qū)分。圖3(e)和(k)顯示了核度中心方法的效果，相對于前述方法，雖然總體呈現單調遞增趨勢但是仍然有臨近節(jié)點間傳播影響力差異較大的現象，散點圖依然較為發(fā)散。從圖3(f)和(l)可以看到，本文提出的路徑多樣性核度中心(Cncd)方法呈現單調遞增走勢，且臨近節(jié)點間的傳播影響力差異較小、散點圖較為收攏，因此可以有效對節(jié)點影響力進行細粒度排序。

圖3 不同影響力評估方法與節(jié)點實際傳播能力關系圖

圖4為Jazz和C.elegans網絡節(jié)點的路徑多樣性核度中心方法與其他幾種方法在傳播影響力方面的熱度圖，橫軸分別為節(jié)點的度中心、介數中心、K核中心、核度中心；縱軸為節(jié)點的路徑多樣性核度中心；顏色坐標表示節(jié)點的實際傳播影響力f。從圖4(a)、(b)、(d)、(e)可以看到度中心、介數中心、K核中心與本文方法相關性并不強，例如jazz網絡度中心和介數中心最大的節(jié)點并非實際傳播影響力最大的節(jié)點，而且兩個網絡中絕大多數節(jié)點都重疊在度中心和介數中心(橫坐標)較小的區(qū)域，無法有效區(qū)分這些節(jié)點的影響力；而在C.elegans網絡的K核中心方法中大量不同傳播影響力的節(jié)點被賦予相同核層，同樣無法通過K核中心方法進行細粒度區(qū) 分；從圖4(c)、(f)可以發(fā)現本文方法與核度中心方法相關性較強，隨著核度中心值的增加、節(jié)點路徑多樣性核度中心值也會相應增加并且傳播影響力也越大，但是在核度中心值(橫坐標)較小的區(qū)域依舊無法對重疊節(jié)點的傳播影響力進行有效區(qū)分。但從圖4(a)～(f)可以看到數據點在本文方法表示的縱坐標上分布較為均勻且隨著縱坐標值的增加，節(jié)點傳播影響力也越大(顏色越深)，因此本文方法能夠對網絡節(jié)點傳播影響力進行更細粒度地探測。

圖4 不同評估方法的傳播影響力熱度比較圖

為了對不同評估方法的有效性進行分析，這里還采用Kendall系數[20](τ)衡量不同評估排序方法與節(jié)點實際影響力(f)排序之間的相關性。τ取值最大為1表示兩種排序方法完全正相關，取值最小為-1表示兩種排序方法完全負相關，τ值越大說明評估方法排序的結果越接近于節(jié)點實際影響力排序、該評估方法越準確。表4顯示了不同評估方法與實際傳播影響力排序之間的Kendall系數，可以看到路徑多樣性核度中心方法Cncd的性能均優(yōu)于其他方法，并且隨著網絡節(jié)點規(guī)模和感染率β的增加，評估方法的準確性有所下降，這個現象可以解釋為隨著感染率β的增加，在固定時間有越來越多的節(jié)點均達到飽和傳播感染狀態(tài)，從而無法辨別彼此間的實際傳播能力，導致排名順序精確度的下降。

表4 不同評估方法與實際影響力排名之間的Kendall系數

(b)評估方法之間的差異分析

為了分析本文提出的路徑多樣性核度中心方法(Cncd)與其他方法對節(jié)點影響力評估的差異，分別將本文方法與度中心(CD)、介數中心(CB)、核度中心(Cnc)方法進行了比較(由于K核中心(CKC)方法將大量不同影響力節(jié)點賦予相同值，準確度較差，因此直接排除)。實驗將Cncd方法分別與其他三種方法進行兩兩比較，選取非同時出現在兩種方法排名前20位的節(jié)點作為各自的傳播源節(jié)點(前20位中Cncd與CD有3個不同節(jié)點、Cncd與CB有6個不同節(jié)點、Cncd與Cnc有1個不同節(jié)點)，因為僅僅出現在一種評估方法的節(jié)點一定程度反映了該方法對影響力評估的側重點。為了比較傳播效果，實驗分別采用獨立級聯(IC)模型和SI模型進行信息傳播，實驗中將IC模型的成功激活概率設置為0.2，SI模型傳播率β=0.6，λ=2。限于篇幅，這里只給出了規(guī)模較大的C.elegans網絡的實驗結果。

從圖5(a)(b)(c)可以看到，相比于其他三種方法，僅被Cncd方法發(fā)現的節(jié)點在獨立級聯(IC)模型的傳播效果均優(yōu)于其他方法，而圖5(d)(e)(f)中僅被Cncd發(fā)現的節(jié)點在SI模型的傳播速度均快于其他方法，達到同樣傳播效果所需的時間更少。綜上可知，由于(Cncd)方法引入了核度概念，對處于網絡邊緣但連接度大的節(jié)點也給予了正確的定位，同時考慮了傳播路徑的多樣性，因此能夠更有效地對節(jié)點影響力進行評估。

4 結 論

本文針對當前網絡節(jié)點影響力評估方法的不足，提出了一種基于路徑多樣性的節(jié)點核度中心評估方法，即路徑多樣性核度中心(Cncd)方法。該方法不同于已有網絡K核分解粗略定位核層最大的節(jié)點作為影響力節(jié)點，而是同時考慮了節(jié)點在網絡中的拓撲位置和局部鄰域信息，通過引入路徑多樣性概念來提高影響力節(jié)點的定位效果。實驗結果證明相對于度中心(CD)、介數中心(CB)、接近中心(CC)、K核中心(CKC)、核度中心(Cnc)等評估方法，本文提出的Cncd方法能夠更有效地對關鍵節(jié)點進行定位和更細粒度地對節(jié)點影響力進行有效排序。

和當前絕大多數研究工作一樣，本文主要針對單個節(jié)點的影響力進行評估排序，實驗過程中也發(fā)現挖掘多個最具傳播影響力的節(jié)點并非簡單地定位一組排名靠前的節(jié)點，網絡結構和社區(qū)特性均會對其產生重要的影響，因此如何挖掘網絡(特別是帶有社區(qū)結構的網絡)中可使影響力最大化的一組關鍵節(jié)點值得未來進一步研究。

圖5 不同時出現在各評估方法前20名的節(jié)點傳播效果差異圖

[1] Pastor-Satorras R, Vespignani A. Epidemic spreading in scale-free networks.PhysicalReviewLetters, 2001,86(14):3200-3203

[2] Lü L Y, Chen D B, Zhou T. The small world yields the most effective information spreading.NewJournalofPhysical,2011,13(12) :123005

[3] Yang J, Yao C, Ma W, et al. A study of the spreading scheme for viral marketing based on a complex network model.PhysicaAStatisticalMechanics&ItsApplication,2010, 389(4): 859-870

[4] Lü L Y, Zhang Y C, Yeung C H, et al. Leaders in social networks, the delicious case.PLoSOne, 2011,6(6): e21202

[5] Zhou Y B, Lü L Y, Li M. Quantifying the influence of scientists and their publications: distinguishing between prestige and popularity.NewJournalofPhysical, 2012,14(3) :033033

[6] Freeman L C. Centrality in social networks conceptual clarification.SocialNetworks, 1979,1(3) :215-239

[7] Sabidussi G. The centrality index of a graph.Psychometrika, 1966, 31(4): 581-603

[8] Chen D B, Lü L Y, Shang M S, et al. Identifying influential nodes in complex networks.JournaloftheAmericanStatisticalAssociation, 2012, 391(4):1777-1787

[9] Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks.NaturePhysical, 2010, 6(11): 888-893

[10] Basaras P, Katsaros D, Tassiulas L. Detecting influential spreaders in complex, dynamic networks.IEEEComputer, 2013, 46(4): 24-29

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

[12] Liu J G, Ren Z M, Guo Q. Ranking the spreading influence in complex networks.PhysicaAStatisticalMechanics&ItsApplication,2013, 392(18): 4154-4159

[13] Joonhyun B, Sangwook K. Identifying and ranking influential spreaders in complex networks by neighborhood coreness.PhysicaAStatisticalMechanics&ItsApplication, 2014, 395(4): 549-559

[14] Shannon C E. A mathematical theory of communication.BellSystemTechnicalJournal, 1948, 27(3): 379-423

[15] Chen D B, Gao H, Lü L Y, et al. Identifying influential nodes in large-scale directed networks: The role of clustering.PLoSOne,2013, 8(10): e77455

[16] Zhang Z K, Zhang C X, Han X P, et al. Emergence of Blind Areas in Information Spreading.PLoSOne, 2014,9(4): e95785

[17] Gleiser P, L Danon. Community structure in Jazz.AdvancesinComplexSystems, 2003, 6(4): 565-573

[18] Duch J, A Arenas.Community identification using extremal optimization.PhysicalReviewE, 2005, 72(2):027104

[19] Kempe D, Kleinberg J, Tardos E. Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington, USA, 2003. 137-146

[20] Knight W R. A computer method for calculating Kendall’s tau with ungrouped data.JournaloftheAmericanStatisticalAssociation,1966, 61(314): 436-439

A method for identifying and ranking influential spreading nodes in complex networks based on neighborhood core diversity centrality

Yang Xiong***, Huang Decai*, Zhan Xiuxiu***, Zhang Zike***

(*School of Computer science and Technology,School of Software,Zhejiang University of Technology, Hangzhou 310023) (**School of Computer & Information Engineering, Changzhou Institute of Technology, Changzhou 213002) (***Alibaba Research Center for Complexity Sciences,Hangzhou Normal University, Hangzhou 311121)

The study aimed to find an improved technique for identifying and ranking influencial nodes in complex networks. In consideration of current techniques’ problems of lower node locating accuracy, higher computing complexity, etc., a method to desect and extimate influential spreading nodes based on the information entropy of path diversity, called the neighborhood core diversity centrality (Cncd) method, was put forward by introducing the conception of path diversity into the traditionalK-core decomposition method to conduct the study from the perspective of information propagation. The experimental results show that, compared with other methods like degree centrality (CD), betweennes centrality (CB), closeness centrality (CC),K-core centrality (CKC) and neighborhood core centrality (Cnc), the proposed Cncdmethod can identify influential nodes more accurately and rank influential nodes more finely.

influence of nodes, degree centrality, betweenness centrality, closeness centrality,K-core decomposition

10.3772/j.issn.1002-0470.2016.02.003

①國家自然科學基金(11305043)，浙江省自然科學基金(LQ13F030015， LY14A050001)，江蘇省高校自然科學基金(13KJD520001)和常州市科技計劃應用基礎研究(CJ20159013)資助項目。

2015-08-18)

②男，1980年生，博士生，講師；研究方向：復雜網絡，數據挖掘；E-mail: popobear801116@qq.com

③通訊作者，E-mail: hdc@zjut.edu.cn