探測(cè)和評(píng)估復(fù)雜網(wǎng)絡(luò)影響力節(jié)點(diǎn)的路徑多樣性核度中心方法①

楊 雄 黃德才 詹秀秀 張子柯

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

?

探測(cè)和評(píng)估復(fù)雜網(wǎng)絡(luò)影響力節(jié)點(diǎn)的路徑多樣性核度中心方法①

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

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

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

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

0 引 言

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

1 相關(guān)研究

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

最近，Kitsak[9]提出了一種K核分解(K-core decomposition)方法，他發(fā)現(xiàn)很多具有高連接度和高介數(shù)中心的節(jié)點(diǎn)往往并不一定能夠?qū)W(wǎng)絡(luò)中的信息傳播起到?jīng)Q定作用，恰恰相反，實(shí)驗(yàn)發(fā)現(xiàn)能夠?qū)π畔鞑テ鸬街匾饔玫墓?jié)點(diǎn)通常位于網(wǎng)絡(luò)核心位置。K核分解首先刪除圖G中所有連接度為1的節(jié)點(diǎn)及他們所有的邊，若剩余節(jié)點(diǎn)中仍有度值為1的點(diǎn)繼續(xù)將他們刪除，將這些刪除的節(jié)點(diǎn)劃入核層為1的核中(本文用kc表示節(jié)點(diǎn)的核層)；其次對(duì)剩余連接度為2的節(jié)點(diǎn)重復(fù)上面步驟，將它們劃入核層為2的核中(kc=2)；最后該過程一直循環(huán)下去直到所有節(jié)點(diǎn)均被刪除且分配了相對(duì)應(yīng)的核層數(shù)kc。

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

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

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

圖1 路徑多樣性的網(wǎng)絡(luò)核度示意圖

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

2 節(jié)點(diǎn)影響力評(píng)估方法描述

傳統(tǒng)的網(wǎng)絡(luò)節(jié)點(diǎn)影響力評(píng)估大都利用圖論中割點(diǎn)、割邊等概念對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行研究，而以社會(huì)網(wǎng)絡(luò)為代表的復(fù)雜網(wǎng)絡(luò)對(duì)節(jié)點(diǎn)影響力評(píng)估大都借助其結(jié)構(gòu)屬性和信息傳播動(dòng)力學(xué)模型進(jìn)行度量。G=(V,E)表示一個(gè)無權(quán)無向網(wǎng)絡(luò)圖，節(jié)點(diǎn)數(shù)n=|V|，借助已有研究成果對(duì)任意節(jié)點(diǎn)i的影響力評(píng)估指標(biāo)表示如下：度中心(CD(i))、介數(shù)中心(CB(i))[6]、接近中心(CC(i))[7]、K核中心(CKC(i))[9]、核度中心(Cnc(i))[13]。

2.1 路徑信息熵的節(jié)點(diǎn)影響力計(jì)算

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

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

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

(1)

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

步驟2 對(duì)式(1)進(jìn)行標(biāo)準(zhǔn)化處理得到公式

(2)

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

(3)

其中λ為可調(diào)參數(shù)。鑒于該思想，我們?cè)诤硕戎行脑u(píng)估方法Cnc基礎(chǔ)上考慮了節(jié)點(diǎn)鄰域信息，并且

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

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

(4)

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

步驟4 遍歷網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)，計(jì)算它們的路徑多樣性核度中心評(píng)估值Cncd(i)，并根據(jù)該值從大到小排序，即為節(jié)點(diǎn)的影響力排序。

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

表1 不同影響力中心評(píng)估方法下的節(jié)點(diǎn)排序

表2 不同影響力中心評(píng)估方法下的節(jié)點(diǎn)數(shù)值

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

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

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

2.3 路徑信息熵對(duì)節(jié)點(diǎn)影響力評(píng)估的意義

3 實(shí)驗(yàn)結(jié)果分析

3.1 實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)

實(shí)驗(yàn)過程中使用2個(gè)真實(shí)網(wǎng)絡(luò)進(jìn)行結(jié)果分析，分別為Gleiser[17]的爵士音樂家網(wǎng)絡(luò)(Jazz)和Duch[18]的細(xì)胞代謝網(wǎng)絡(luò)(C.elegans metabolic network)，兩個(gè)網(wǎng)絡(luò)基本拓?fù)涮匦匀绫?所示。

表3 兩個(gè)實(shí)驗(yàn)網(wǎng)絡(luò)的拓?fù)鋽?shù)據(jù)

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

(a)排序結(jié)果與實(shí)際傳播影響力的關(guān)系

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

圖3 不同影響力評(píng)估方法與節(jié)點(diǎn)實(shí)際傳播能力關(guān)系圖

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

圖4 不同評(píng)估方法的傳播影響力熱度比較圖

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

表4 不同評(píng)估方法與實(shí)際影響力排名之間的Kendall系數(shù)

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

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

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

4 結(jié) 論

本文針對(duì)當(dāng)前網(wǎng)絡(luò)節(jié)點(diǎn)影響力評(píng)估方法的不足，提出了一種基于路徑多樣性的節(jié)點(diǎn)核度中心評(píng)估方法，即路徑多樣性核度中心(Cncd)方法。該方法不同于已有網(wǎng)絡(luò)K核分解粗略定位核層最大的節(jié)點(diǎn)作為影響力節(jié)點(diǎn)，而是同時(shí)考慮了節(jié)點(diǎn)在網(wǎng)絡(luò)中的拓?fù)湮恢煤途植苦徲蛐畔?，通過引入路徑多樣性概念來提高影響力節(jié)點(diǎn)的定位效果。實(shí)驗(yàn)結(jié)果證明相對(duì)于度中心(CD)、介數(shù)中心(CB)、接近中心(CC)、K核中心(CKC)、核度中心(Cnc)等評(píng)估方法，本文提出的Cncd方法能夠更有效地對(duì)關(guān)鍵節(jié)點(diǎn)進(jìn)行定位和更細(xì)粒度地對(duì)節(jié)點(diǎn)影響力進(jìn)行有效排序。

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

圖5 不同時(shí)出現(xiàn)在各評(píng)估方法前20名的節(jié)點(diǎn)傳播效果差異圖

[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

①國家自然科學(xué)基金(11305043)，浙江省自然科學(xué)基金(LQ13F030015， LY14A050001)，江蘇省高校自然科學(xué)基金(13KJD520001)和常州市科技計(jì)劃應(yīng)用基礎(chǔ)研究(CJ20159013)資助項(xiàng)目。

2015-08-18)

②男，1980年生，博士生，講師；研究方向：復(fù)雜網(wǎng)絡(luò)，數(shù)據(jù)挖掘；E-mail: popobear801116@qq.com

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