胡慶成 尹龑燊 馬鵬斐 高旸 張勇 邢春曉

(清華大學(xué)計(jì)算機(jī)系,信息技術(shù)研究院,清華信息科學(xué)與技術(shù)國家實(shí)驗(yàn)室,北京 100084)

(2013年1月25日收到;2013年3月25日收到修改稿)

1 引言

現(xiàn)實(shí)世界中的諸多系統(tǒng)都以復(fù)雜網(wǎng)絡(luò)形式存在,比如互聯(lián)網(wǎng)、社會(huì)系統(tǒng)、計(jì)算網(wǎng)絡(luò)、生物網(wǎng)絡(luò)和社交網(wǎng)絡(luò)等.理解復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和功能是目前國際研究的熱點(diǎn).在很多科學(xué)領(lǐng)域中,都使用網(wǎng)中絡(luò)用來節(jié)表點(diǎn)示代系表統(tǒng)人中,邊成代員表之人間與的人關(guān)之系間,如的在聯(lián)社系交.由網(wǎng)絡(luò)于這些網(wǎng)絡(luò)具有很高的復(fù)雜性,因此被稱為“復(fù)雜網(wǎng)絡(luò)(complex network)”[1-3],它已成為當(dāng)前最重要的多學(xué)科交叉研究領(lǐng)域之一.在復(fù)雜網(wǎng)絡(luò)中,找出最具影響力的節(jié)點(diǎn)[4-9]或意見領(lǐng)袖[10]在理論和現(xiàn)實(shí)應(yīng)用中都有重大的意義,例如有效地控制疾病傳播[11]、流言散布[12,13]、計(jì)算機(jī)病毒擴(kuò)散,還可以傳播新產(chǎn)品[14]、新思想[15]以推進(jìn)社會(huì)化進(jìn)程.

在社會(huì)網(wǎng)絡(luò)分析中,常用“中心性(centrality)”來測量最有影響力的節(jié)點(diǎn).文獻(xiàn)[16,17]利用度中心性(degree centrality)來測量最有影響力的節(jié)點(diǎn),在符合冪律的非均勻網(wǎng)絡(luò)中,度數(shù)較大的hub節(jié)點(diǎn)的傳播影響力應(yīng)該相對較大,這也是目標(biāo)免疫和熟人免疫策略的基本依據(jù).文獻(xiàn)[18]利用了介數(shù)中心性(betweenness centrality)來評價(jià)影響力,介數(shù)中心性是以經(jīng)過某個(gè)節(jié)點(diǎn)的最短路徑的數(shù)目來刻畫節(jié)點(diǎn)的重要性.文獻(xiàn)[19]提出PageRank算法來評價(jià)網(wǎng)頁的重要性,它認(rèn)為一個(gè)網(wǎng)頁(節(jié)點(diǎn))的重要性取決于其前向鏈接的數(shù)量與質(zhì)量.文獻(xiàn)[20,21]利用緊密度指標(biāo)(closeness centrality)刻畫某個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的難易程度.文獻(xiàn)[22]提出通過K-shell(ks)[23]分解來確定最具有影響力的單源節(jié)點(diǎn).

本文認(rèn)為節(jié)點(diǎn)的影響力不只是由節(jié)點(diǎn)內(nèi)部屬性決定,而且其外部屬性緊密相關(guān),這與哲學(xué)范疇的內(nèi)因和外因思想一致.內(nèi)部屬性如度數(shù)、緊密性、介數(shù)等中心化指標(biāo),外部屬性如所屬社區(qū)的大小、社區(qū)內(nèi)關(guān)系緊密度等.社區(qū)[24,25]是一個(gè)有共同愛好的,或者位于一個(gè)共同地方的、或者同在某個(gè)工作場所的、或者具有家庭聯(lián)系的群體[26].社區(qū)內(nèi)的節(jié)點(diǎn)聯(lián)系緊密,社區(qū)間的節(jié)點(diǎn)聯(lián)系松散.

本文提出了KSC(K-shell and community centrality)指標(biāo)模型.此模型不但考慮了節(jié)點(diǎn)的內(nèi)部屬性,而且還綜合考慮了節(jié)點(diǎn)的外部屬性,例如節(jié)點(diǎn)所屬的社區(qū)特性等.然后利用SIR(susceptible-infected-recovered)模型對傳播過程進(jìn)行仿真,實(shí)驗(yàn)證明本文提出的方法可以更好地發(fā)現(xiàn)最具有影響力的節(jié)點(diǎn).本文為這項(xiàng)具有挑戰(zhàn)性研究提供了新的思想和方法.

2 相關(guān)研究

在社會(huì)網(wǎng)絡(luò)中,發(fā)現(xiàn)最具有影響力的節(jié)點(diǎn)可以幫助我們有效地控制疾病傳播、流言散布、計(jì)算機(jī)病毒擴(kuò)散,還可以傳播新產(chǎn)品、新思想以推進(jìn)社會(huì)化進(jìn)程.

圖1 網(wǎng)絡(luò)分析樣例圖

2.1 度中心化

度中心化[27,28]是一種最簡單的方法,用于描述在靜態(tài)網(wǎng)絡(luò)中節(jié)點(diǎn)所產(chǎn)生的直接影響力.設(shè)網(wǎng)絡(luò)G=(V,E)具有n=|V|個(gè)節(jié)點(diǎn)和m=|E|條邊,節(jié)點(diǎn)v的度數(shù)是指與節(jié)點(diǎn)v連接的節(jié)點(diǎn)個(gè)數(shù),用Cd(v)表示

其中d(v)稱為該節(jié)點(diǎn)的度.如圖1所示,盡管節(jié)點(diǎn)14度數(shù)最大為7,但作為初始節(jié)點(diǎn),它最終的傳播范圍并不一定是最廣泛的,因?yàn)樗泥従庸?jié)點(diǎn)的度數(shù)都很小.

2.2 介數(shù)中心化

介數(shù)中心化刻畫了網(wǎng)絡(luò)中節(jié)點(diǎn)對于信息流動(dòng)的影響力.節(jié)點(diǎn)v的介數(shù)[18]定義為

σst表示源節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的最短路徑數(shù),σst(v)表示節(jié)點(diǎn)s經(jīng)過節(jié)點(diǎn)v到目標(biāo)節(jié)點(diǎn)t的最短路徑數(shù).

2.3 緊密度

緊密度[20,21]用于刻畫節(jié)點(diǎn)到達(dá)其他節(jié)點(diǎn)的難易程度：

dG(s,t)表示源節(jié)點(diǎn)s到節(jié)點(diǎn)t的最短距離.

2.4 K-shell分解方法

K-shell給出了網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的一種粗粒化的劃分,用Cks(v)表示.網(wǎng)絡(luò)邊緣節(jié)點(diǎn)的K-shell為1,然后往內(nèi)像剝洋蔥一樣一層層進(jìn)入網(wǎng)絡(luò)的核心.首先去除網(wǎng)絡(luò)中度數(shù)小于k的所有節(jié)點(diǎn)及其連邊;如果在剩下的節(jié)點(diǎn)中仍有度值小于k的節(jié)點(diǎn),那么就繼續(xù)去除這些節(jié)點(diǎn),直至網(wǎng)絡(luò)中剩下的節(jié)點(diǎn)的度值不小于k.依次取k=1,2,3,···,就得到了該網(wǎng)絡(luò)的K-shell分解.具體過程可參考圖一.Kitsak等[22]實(shí)驗(yàn)研究表明,對于單個(gè)傳播源感染率低的情形,度數(shù)大或者高介數(shù)的節(jié)點(diǎn)不一定是最有影響力的節(jié)點(diǎn),而通過K-shell分解分析確定的網(wǎng)絡(luò)核心節(jié)點(diǎn)(即K-shell值大的節(jié)點(diǎn))才是最有影響力的節(jié)點(diǎn);其研究表明,K-shell分解方法是一種比較好的影響力節(jié)點(diǎn)識別方法,可以更好地預(yù)測疾病等的傳播.當(dāng)傳染病在網(wǎng)絡(luò)的K-shell大的節(jié)點(diǎn)爆發(fā)時(shí),病毒總是可以在網(wǎng)絡(luò)核心通過許多種路徑開始感染其他部分,無論該節(jié)點(diǎn)度數(shù)的大與小,這個(gè)結(jié)論都是有效的.這些通路的存在反過來也意味著如果以一個(gè)隨機(jī)節(jié)點(diǎn)為源爆發(fā)疫情,有高K-shell值的節(jié)點(diǎn)更有可能早于其他節(jié)點(diǎn)被感染(疾病預(yù)測).

2.5 社區(qū)劃分算法

社區(qū)[24,25]是一個(gè)有共同愛好的、或者位于一個(gè)共同地方的、或者同在某個(gè)工作場所的、或者具有家庭聯(lián)系的群體[26].社區(qū)內(nèi)的節(jié)點(diǎn)聯(lián)系緊密,社區(qū)間的節(jié)點(diǎn)聯(lián)系松散.社區(qū)劃分(community detecting)的概念前期在Lin的論文[29]中提出.如圖1,網(wǎng)絡(luò)劃分為4個(gè)社區(qū)(節(jié)點(diǎn)1—5,6—9,10—12,13—19).社區(qū)是復(fù)雜網(wǎng)絡(luò)信息傳播中最普遍和最重要的拓?fù)鋵傩灾?信息在同一社區(qū)內(nèi)傳播迅速,而在社區(qū)之間傳播緩慢.Kernighan-Lin(KL)算法[30]、快速Newman(FN)算法[31]和Guimera-Amaral(GA)算法[32]是經(jīng)典的復(fù)雜網(wǎng)絡(luò)社區(qū)劃分算法.

本文使用了FN算法.FN算法是Newman提出的基于局部搜索的快速社區(qū)劃分算法.其優(yōu)化目標(biāo)是極大化網(wǎng)絡(luò)模塊性(modularity)評價(jià)函數(shù)Q[26].FN算法屬于聚合算法,它初始假定所有節(jié)點(diǎn)各自成為一個(gè)社區(qū),然后每一步根據(jù)原有連接合并兩個(gè)社區(qū),計(jì)算Q值并記錄下來,直到所有社區(qū)都被合并成為一個(gè)社區(qū).最后根據(jù)記錄下的Q值,找到最優(yōu)的劃分結(jié)果.

3 算法模型

我們認(rèn)為節(jié)點(diǎn)的傳播力不但與節(jié)點(diǎn)的內(nèi)部自身屬性有關(guān),如度數(shù)、緊密度、介數(shù)、K-shell等,還與它的外部環(huán)境屬性相關(guān),如節(jié)點(diǎn)所處外部環(huán)境：社區(qū)大小,社區(qū)關(guān)聯(lián)緊密度等.本文提出節(jié)點(diǎn)的影響力是由內(nèi)因與外因同時(shí)決定的這一新穎思想和方法,即KSC中心化指標(biāo)模型.模型符合哲學(xué)內(nèi)因與外因?qū)κ挛锿瑯泳哂袥Q定作用這一思想理念.

復(fù)雜網(wǎng)絡(luò)G=(V,E)中,節(jié)點(diǎn)vo的KSC值定義如下：

其中 f internal(vo)為節(jié)點(diǎn)的內(nèi)部影響力,f external(vo)為節(jié)點(diǎn)的外部影響力,α為內(nèi)部影響因子,β為外部影響因子,且滿足α+β=1,α和β可以根據(jù)實(shí)際網(wǎng)絡(luò)結(jié)構(gòu)與功能設(shè)定.

f internal(v o)定義如下：

其中,K(v)為節(jié)點(diǎn)內(nèi)部屬性值,可取度數(shù)、介數(shù)、緊密度和K-shell等節(jié)點(diǎn)自身屬性,mv∈aVx(K(v))為歸一化因子.

f external(v o)定義如下：

其中C為FN算法劃分的社區(qū)集合,d(vo,c)為節(jié)點(diǎn)vo在社區(qū)c中的鄰居節(jié)點(diǎn)的總個(gè)數(shù),|c|為社區(qū)c的大小是歸一化因子.

本文實(shí)驗(yàn)中α與β可以根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)設(shè)定;其中 finternal(vo)選取K-shell為內(nèi)部屬性,也可以為度數(shù)、緊密度和介數(shù)等,fexternal(vo)選取為社區(qū)屬性,俗語“物以類聚,人以群分”說明社區(qū)內(nèi)部節(jié)點(diǎn)之間有共同的興趣愛好等,相似性更大.

表1給出了圖1各節(jié)點(diǎn)的各種指標(biāo),如節(jié)點(diǎn)14度數(shù)最大,但是由于處在網(wǎng)絡(luò)的邊緣,所以最終影響力為2,而節(jié)點(diǎn)7雖然度數(shù)為6,但是它是其他幾個(gè)社區(qū)連通的樞紐,結(jié)構(gòu)洞[33,34]概念中重要節(jié)點(diǎn).節(jié)點(diǎn)1—5雖然K-shell相同,但是節(jié)點(diǎn)1是2—5連接其他節(jié)點(diǎn)的橋接關(guān)系.從表1中可以看出各種方法得到的最具影響力節(jié)點(diǎn)排名各不相同.

表1 計(jì)算圖一中節(jié)點(diǎn)的傳播力

4 模型及實(shí)驗(yàn)分析

4.1 SIR模型

SIR模型在現(xiàn)實(shí)社會(huì)網(wǎng)絡(luò)中已廣泛應(yīng)用于疾病傳播、信息傳播及謠言傳播的研究.為了驗(yàn)證本文提出的模型,我們采用SIR模型[35-38]來模擬仿真?zhèn)鞑ミ^程,并將其結(jié)果與我們的模型實(shí)驗(yàn)結(jié)果做比較.

SIR模型中有三種狀態(tài),易感染狀態(tài)S(susceptible),感染狀態(tài)I(infected),免疫狀態(tài)(recovered).當(dāng)個(gè)體處于感染狀態(tài)時(shí),以β的概率感染處于易感染狀態(tài)鄰居個(gè)體,感染狀態(tài)的節(jié)點(diǎn)以γ的概率恢復(fù)為免疫狀態(tài).

如果β值較大,節(jié)點(diǎn)傳播能力很強(qiáng),節(jié)點(diǎn)將很快感染整個(gè)網(wǎng)絡(luò),從而很難區(qū)分單個(gè)個(gè)體的重要性;較小的β能在有限時(shí)間內(nèi)更好地顯示出感染范圍.本文中我們設(shè)定較小的β=0.04.

4.2 實(shí)驗(yàn)數(shù)據(jù)

考慮到不同的社會(huì)網(wǎng)絡(luò)類型所代表不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特性,我們選取了4個(gè)真實(shí)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集[39]進(jìn)行分析比較,表2給出各個(gè)網(wǎng)絡(luò)的屬性特征：1)Blogs網(wǎng)絡(luò)數(shù)據(jù)[40],MSN博客空間中交流的關(guān)系網(wǎng)絡(luò);2)Netscience合著關(guān)系網(wǎng)絡(luò)[41],選擇了其中最大連通子圖379個(gè)作者的關(guān)系網(wǎng)絡(luò);3)Router網(wǎng)絡(luò),數(shù)據(jù)是由Rocketfuel Project[42]收集的互聯(lián)網(wǎng)中路由連接層級關(guān)系網(wǎng)絡(luò);4)Email網(wǎng)絡(luò)[43],是洛維拉·依維爾基里大學(xué)成員郵件通信的關(guān)系網(wǎng)絡(luò).我們的模型也可應(yīng)用于其他類型的復(fù)雜網(wǎng)絡(luò).

其中n是節(jié)點(diǎn)數(shù),m為邊數(shù),〈k〉表示網(wǎng)絡(luò)中平均度數(shù)據(jù),max(k)為節(jié)點(diǎn)中最大度數(shù),d為節(jié)點(diǎn)之間最短路徑的平均數(shù),max(Cks)為網(wǎng)絡(luò)中最大的K-shell,C為整個(gè)復(fù)雜網(wǎng)絡(luò)被劃分的社區(qū)數(shù).

表2 現(xiàn)實(shí)社會(huì)網(wǎng)絡(luò)的屬性情況

4.3 實(shí)驗(yàn)效果

我們應(yīng)用章節(jié)4.1中所提到的SIR模型,對所提出的KSC指標(biāo)與度、緊密性、介數(shù)和K-shell中心化指標(biāo)進(jìn)行了分析比較.實(shí)驗(yàn)?zāi)M傳播過程中,每次只選取網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)作為初始傳播節(jié)點(diǎn),設(shè)定較短傳播時(shí)間(t=10),對每個(gè)節(jié)點(diǎn)進(jìn)行1000次重復(fù)實(shí)驗(yàn)取均值,最終感染與恢復(fù)的節(jié)點(diǎn)總數(shù)定義為影響力F(t).

圖2 KSC模型中內(nèi)部影響因子α與外部影響因子β取不同對傳播影響力指標(biāo)的影響分析

圖2 表示了在KSC模型中選取不同的內(nèi)部影響因子α與外部影響因子β(α+β=1)對結(jié)果的影響程度.哲學(xué)范疇中事物的運(yùn)動(dòng)和變化,是由它本身固有的內(nèi)部矛盾引起的,又是同它所處的一定的外在條件相聯(lián)系的,內(nèi)因和外因在事物發(fā)展中的地位和作用是不同的.這與模型中內(nèi)部影響因子α與外部影響因子β對傳播影響假設(shè)完全一致.如在圖2(c)中局部放大了最具影響力的前10位,當(dāng)0≤α≤0.2,1≥β≥0.8,或1≥α≥0.8,0≤β≤0.2時(shí)可以看到,影響力曲線波動(dòng)較大,影響力排名靠后的節(jié)點(diǎn)影響反而大.即只是單純的考慮內(nèi)部屬性或外部屬性對發(fā)現(xiàn)最具有影響的節(jié)點(diǎn)來說準(zhǔn)確性,適用性較差.

經(jīng)實(shí)驗(yàn)分析得出四種不同拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)的內(nèi)、外影響因子經(jīng)驗(yàn)取值情況,如表3所示.可以看出在不同類型的網(wǎng)絡(luò)結(jié)構(gòu)中,內(nèi)、外因所起的權(quán)重是不同的,本文實(shí)驗(yàn)中的α,β根據(jù)表3中取較好的經(jīng)驗(yàn)值,這從另一方面證明了所提出模型的合理性及普遍性.

圖3所表示的是在不同的網(wǎng)絡(luò)中中心度指標(biāo)與實(shí)際影響力之間的關(guān)系.

在Blogs網(wǎng)絡(luò)中,度,K-shell,介數(shù)指標(biāo)與影響力F(t)關(guān)系都不是很明顯,例如在介數(shù)指標(biāo)結(jié)果中,一些介數(shù)大的節(jié)點(diǎn)F(t)比一些介數(shù)很小的節(jié)點(diǎn)影響力還要低,但KSC指標(biāo)可以較好地區(qū)分出最具影響力的節(jié)點(diǎn).Email網(wǎng)絡(luò)中,所有指標(biāo)表現(xiàn)都較好,緊密度與KSC更為理想,這與網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)有關(guān)系.在Netscience網(wǎng)絡(luò)中,介數(shù)衡量結(jié)果最差,緊密度,K-shell與節(jié)點(diǎn)F(t)影響力關(guān)系也不明顯,KSC的效果要優(yōu)于度數(shù).在路由網(wǎng)絡(luò)(Router)中K-shell與KSC結(jié)果接近,其他指標(biāo)結(jié)果很難得到傳播力較大的節(jié)點(diǎn).總之,在不同的網(wǎng)絡(luò)中傳統(tǒng)的中心度指標(biāo)各有優(yōu)缺點(diǎn),但是我們提出的KSC整體效果最好,都能有效地區(qū)分出最具有影響力的節(jié)點(diǎn),通用性較強(qiáng).

表3 內(nèi)、外影響因子取值情況

圖3 節(jié)點(diǎn)影響力分析比對,列代表5種不同中心化指標(biāo),行表示為4種不同的復(fù)雜網(wǎng)絡(luò)環(huán)境,傳播影響力F(t)(t=10),每個(gè)初始節(jié)點(diǎn)重復(fù)運(yùn)行1000次取均值

對于單個(gè)傳播源的情形,最具有影響力的節(jié)點(diǎn)并非度數(shù)最大的節(jié)點(diǎn)或者介數(shù)最大的節(jié)點(diǎn),而是K-shell最大的節(jié)點(diǎn),這一結(jié)論在Kitsak等[22]已在《Nature Physics》指出.圖4比較了KSC與K-shell的實(shí)驗(yàn)效果,KSC比K-shell增加了外部屬性的影響因素.例如在Email網(wǎng)絡(luò)中,當(dāng)K-shell為10時(shí),傳播影響力F(t)(t=10)并不穩(wěn)定,而且變化范圍較大,并且影響力隨著KSC值的增大呈現(xiàn)增大趨勢.在4種復(fù)雜網(wǎng)絡(luò)中明顯可以看出當(dāng)KSC一定時(shí)F(t)相對穩(wěn)定,顏色變化范圍較小.

圖4 KSC與K-shell指標(biāo)在4種不同復(fù)雜網(wǎng)絡(luò)中的分析比較,橫軸表示KSC的指標(biāo)值,縱軸表示K-shell的指標(biāo)值,顏色坐標(biāo)代表SIR模型仿真出的實(shí)際影響力大小F(t)

圖5 比較了KSC與介數(shù)的實(shí)驗(yàn)效果.可出看出在Email網(wǎng)絡(luò)中,KSC與介數(shù)表現(xiàn)正向同步較好,都能較好地發(fā)出最具影響力的節(jié)點(diǎn),但在其他三個(gè)網(wǎng)絡(luò)環(huán)境中KSC表現(xiàn)明顯優(yōu)于介數(shù)指標(biāo).實(shí)驗(yàn)結(jié)果表明KSC方法明顯優(yōu)于已有的4種典型方法.由此可見,考慮節(jié)點(diǎn)的外部屬性對于找出最有影響力的節(jié)點(diǎn)意義重大,且具有較強(qiáng)的通用性,驗(yàn)證了我們所提出模型的合理性與普遍性.

如圖6所示,在Blogs網(wǎng)絡(luò)中,KSC曲線的某一點(diǎn)(x,y),橫坐標(biāo)表示此點(diǎn)用KSC指標(biāo)值得出的排名為x,縱坐標(biāo)表示此點(diǎn)在SIR仿真的實(shí)際影響力為y.理論上,一個(gè)好的指標(biāo)方法應(yīng)該表現(xiàn)為向右傾斜單調(diào)下降的曲線.因?yàn)閷τ谝粋€(gè)好的指標(biāo)方法,如果某個(gè)節(jié)點(diǎn)按該指標(biāo)得出的排名越靠后,其實(shí)際影響力F(t)應(yīng)該隨之減小.

從圖6結(jié)果中分析,可以看到已有的4種典型方法在不同網(wǎng)絡(luò)中影響力均有所波動(dòng),這些方法在不同網(wǎng)絡(luò)中各有優(yōu)劣,通用性不強(qiáng),特別是在影響力前10中波動(dòng)范圍最為明顯.指標(biāo)值小的傳播影響力反而比指標(biāo)值大的傳播影響力要大,特別是在Blogs網(wǎng)絡(luò)中,已有的4種指標(biāo)方法結(jié)果都不太精確,而我們提出的KSC指標(biāo)幾乎在所有的網(wǎng)絡(luò)中都符合向右傾斜單調(diào)下降的理論曲線.

本實(shí)驗(yàn)充分論證了節(jié)點(diǎn)影響力不但由內(nèi)部屬性決定,而且還與其外部屬性密切相關(guān),說明我們提出的KSC模型的合理性及普遍適用性.

圖5 KSC與介數(shù)指標(biāo)在4種不同復(fù)雜網(wǎng)絡(luò)中的分析比較,橫軸表示KSC的指標(biāo)值,縱軸表示介數(shù)的指標(biāo)值,顏色坐標(biāo)代表SIR模型仿真出的實(shí)際影響力大小F(t)

5 結(jié)論

在復(fù)雜網(wǎng)絡(luò)中發(fā)現(xiàn)最具影響力的節(jié)點(diǎn),可以幫助我們提高新知識、新產(chǎn)品的傳播效率,同時(shí)可以有效地制定相應(yīng)的策略來阻止疾病及謠言傳播.復(fù)雜網(wǎng)絡(luò)中鑒別最具影響力的節(jié)點(diǎn)一直以來是研究的熱點(diǎn)與難點(diǎn),我們提出了KSC中心化指標(biāo)模型.實(shí)驗(yàn)選取現(xiàn)實(shí)生活中常見的四種復(fù)雜網(wǎng)絡(luò)博客網(wǎng)、郵件網(wǎng)、路由網(wǎng)和科學(xué)合著網(wǎng),通過SIR模型模擬節(jié)點(diǎn)傳播過程,并對各種中心化指標(biāo)得出的影響力進(jìn)行排序分析,驗(yàn)證了方法的高效性和正確性.

與傳統(tǒng)的度、緊密度、介數(shù)和K-shell方法相比,傳統(tǒng)方法在不同網(wǎng)絡(luò)中各有優(yōu)劣,通用性不強(qiáng).而我們提出的KSC模型綜合考慮了節(jié)點(diǎn)的內(nèi)部屬性與外部屬性,實(shí)驗(yàn)證明用此方法鑒別節(jié)點(diǎn)的影響力要精確得多,適用范圍更大.我們所提出的模型為這項(xiàng)具有挑戰(zhàn)性研究提供了新的思想和方法.

感謝審稿人對本文提出的寶貴意見和建議,使得文章邏輯更加完整合理.

[1]Watts D J,Strogatz SH 1998 Nature393 440

[2]Barab′asi A L,Albert R 1999 Science 286 509

[3]Barab′asi A L,Albert R,Jeong H,Bianconi G 2000 Science287 2115a

[4]Pastor-Satorras R,Vespignani A 2002 Phys.Rev.E 65 036104

[5]Kempe D,Kleinberg J,Tardos E 2003 Proc.9th ACM SIGKDD Intl.Conf.on Knowledge Discovery and Data Mining New Washington,DC,USA,August 24—27,2003 p137

[6]Gomez-Rodriguez M,Leskovec J,Krause A 2010 Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining Washington,DC,USA,July 25—28,2010 p1019

[7]Budak C,Agrawal D,El Abbadi A 2011 Proceedings of the 20th International Conference on World Wide Web Hyderabad,India,March 28—April 1,2011 p665

[8]Mislove A,Marcon M,Gummadi K P,Druschel P,Bhattacharjee B 2007 Proceedings of the ACM SIGCOMM 2007 Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications Kyoto,Japan,August 27—31,2007 p29

[9]Yuan W G,Liu Y,Cheng J J 2013 Acta Phys.Sin.62 038901(in Chinese)[苑衛(wèi)國,劉云,程軍軍2013物理學(xué)報(bào)62 038901]

[10]Weng J,Lim EP,Jiang J,He Q 2010 Proceedingsof the Third International Conferenceon Web Search and Web Data Mining,WSDM 2010 New York,NY,USA,February 4—6,2010 p261

[11]Xu D,Li X,Wang X F 2007 Acta Phys.Sin.56 1313(in Chinese)[許丹,李翔,汪小帆2007物理學(xué)報(bào)56 1313]

[12]Naveed N,Gottron T,Kunegis J,Alhadi A C 2011 Proceedingsof the 20th ACM International Conference on Information and Knowledge Management Koblenz,Germany,June 14—17,2011 p1

[13]Gu Y R,Xia L L 2012 Acta Phys.Sin.61 238701(in Chinese)[顧亦然,夏玲玲2012物理學(xué)報(bào)61 238701]

[14]Swamynathan G,Wilson C,Boe B,Almeroth K,Zhao B Y 2008 Proceedings of the First Workshop on Online Social Networks ACM New York,USA,August 18,2008 p1

[15]Mislove A,Marcon M,Krishna PG,Druschel P,Bhattacharjee B 2007 Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement(IMC’07)ACM New York,USA,October 24—26,2007 p29

[16]Albert R,Jeong H,Barabasi A L 2000 Nature406 378

[17]Pastor-Satorras R,Vespignani A 2001 Phys.Rev.Lett.86 3200

[18]Freeman L C 1977 Sociometry 40 35

[19]Brin S,Page L 1998 Comput.Netw.ISDNSyst.30 107

[20]Opsahl T,Agneessens F,Skvoretz J2010 Soc.Networks32 245

[21]Sabidussi G 1966 Psychometrika 31 581

[22]Kitsak M,Gallos L K,Havlin S,Liljeros F,Muchnik L,Stanley H E,Makse H A 2010 Tech.Rep.Phys.Soc.1001 5285

[23]Carmi S,Havlin S,Kirkpatrick S,Shavitt Y,Shir E 2007 Proc.Natl.Acad.Sci.USA 104 p1150

[24]Girvan M,Newman M EJ2002 Proc.Natl.Acad.Sci.USA 99 7821

[25]Fortunato S2010 Phys.Rep.486 75

[26]Newman M EJ,Girvan M 2004 Phys.Rev.E 69 026113

[27]Freeman L C 1979 Social Networks1 215

[28]Sabidussi G 1966 Psychometrika 31 581

[29]Lin K 1970 Bell Syst.Tech.J.49 291

[30]Newman M EJ2004 Phys.J.B 38 321

[31]Newman M EJ2004 Phys.Rev.E 69 066133

[32]Guimera R,Amaral L A N 2005 Nature 433 7028

[33]Burt R 2004 Am.J.Soc.110 349

[34]Granovetter M 1973 Am.J.Soc.78 1360

[35]Roy M Anderson,Robert M May 1992 Infectious Diseasesof Humans:Dynamicsand Control.(New York：Oxford University Press)p66

[36]Diekmann O,Heesterbeek JA P 2001 Mathematical Epidemiology of Infectious Diseases：Model Building,Analysisand Interpretation(New York：Wiley Seriesin Mathematical&Computational Biology)

[37]Hethcote H W 2000 Soc.Industr.Appl.Math.42 599

[38]Bernoulli D,Blower S 2004 Rev.Med.Virol.14 275

[39]Chen D B,Lu L Y,Shang M S,Zhang Y C,Zhou T 2012 Physica A 391 1777

[40]Xie N 2006 M.S.Dissertation(Bristo：University of Bristol)

[41]Newman M EJ2006 Phys.Rev.E 74 36104

[42]Spring N,Mahajan R,Wetherall D,Anderson T 2004 Acm.Sigcomm.Comp.Commu.Rev.32 3

[43]Guimer`a R,Danon L,D′?az-Guilera A,Giralt F,Arenas A 2003 Phys.Rev.E 68 065103