阮逸潤(rùn) 老松楊 王竣德 白亮 侯綠林

1)(國(guó)防科技大學(xué),信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室,長(zhǎng)沙 410073)

2)(國(guó)防大學(xué)聯(lián)合勤務(wù)學(xué)院,北京 100858)

一種改進(jìn)的基于信息傳播率的復(fù)雜網(wǎng)絡(luò)影響力評(píng)估算法?

阮逸潤(rùn)1)?老松楊1)王竣德1)白亮1)侯綠林2)

1)(國(guó)防科技大學(xué),信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室,長(zhǎng)沙 410073)

2)(國(guó)防大學(xué)聯(lián)合勤務(wù)學(xué)院,北京 100858)

復(fù)雜網(wǎng)絡(luò),傳播影響力,信息傳播率,傳播路徑

評(píng)價(jià)網(wǎng)絡(luò)中節(jié)點(diǎn)的信息傳播影響力對(duì)于理解網(wǎng)絡(luò)結(jié)構(gòu)與網(wǎng)絡(luò)功能具有重要意義.目前,許多基于最短路徑的指標(biāo),如接近中心性、介數(shù)中心性以及半局部(SP)指標(biāo)等相繼用于評(píng)價(jià)節(jié)點(diǎn)傳播影響力.最短路徑表示節(jié)點(diǎn)間信息傳播途徑始終選擇最優(yōu)方式,然而實(shí)際上網(wǎng)絡(luò)間的信息傳播過(guò)程更類似于隨機(jī)游走,信息的傳播途徑可以是節(jié)點(diǎn)間的任一可達(dá)路徑,在集聚系數(shù)高的網(wǎng)絡(luò)中,節(jié)點(diǎn)的局部高聚簇性有利于信息的有效擴(kuò)散,若只考慮信息按最優(yōu)傳播方式即最短路徑傳播,則會(huì)低估節(jié)點(diǎn)信息傳播的能力,從而降低節(jié)點(diǎn)影響力的排序精度.綜合考慮節(jié)點(diǎn)與三步內(nèi)鄰居間的有效可達(dá)路徑以及信息傳播率,提出了一種SP指標(biāo)的改進(jìn)算法,即ASP算法.在多個(gè)經(jīng)典的實(shí)際網(wǎng)絡(luò)和人工網(wǎng)絡(luò)上利用SIR模型對(duì)傳播過(guò)程進(jìn)行仿真,結(jié)果表明ASP指標(biāo)與度指標(biāo)、核數(shù)指標(biāo)、接近中心性指標(biāo)、介數(shù)中心性指標(biāo)以及SP指標(biāo)相比,可以更精確地對(duì)節(jié)點(diǎn)傳播影響力進(jìn)行排序.

1 引 言

自然界中諸多的復(fù)雜系統(tǒng)都可以網(wǎng)絡(luò)的形式存在,我們的生活被各種各樣的網(wǎng)絡(luò)所包圍[1?4],比如互聯(lián)網(wǎng)、電力網(wǎng)絡(luò)、社交網(wǎng)絡(luò)和航空網(wǎng)絡(luò).科學(xué)界真正開(kāi)啟網(wǎng)絡(luò)研究的熱潮是在網(wǎng)絡(luò)的無(wú)標(biāo)度特性[5]和小世界特性[6]被發(fā)現(xiàn)之后.網(wǎng)絡(luò)的無(wú)標(biāo)度特性說(shuō)明復(fù)雜系統(tǒng)內(nèi)部存在嚴(yán)重的不均勻分布,不同節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)和功能的影響大不相同;而小世界特性表示網(wǎng)絡(luò)中信息傳遞速度快,大部分節(jié)點(diǎn)通過(guò)少數(shù)幾步就可以到達(dá)其他節(jié)點(diǎn).當(dāng)前,越來(lái)越多的學(xué)者將研究的焦點(diǎn)放在網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)體的分析上,其中,如何準(zhǔn)確識(shí)別網(wǎng)絡(luò)節(jié)點(diǎn)的傳播影響力是當(dāng)前研究熱點(diǎn)之一,該工作對(duì)于控制謠言在社交網(wǎng)絡(luò)上的傳播[7,8]、傳染病控制[9,10]、設(shè)計(jì)有效廣告投放策略進(jìn)行病毒式營(yíng)銷等[11?14]具有非常重要的作用.

目前已提出許多經(jīng)典的中心性指標(biāo)用于對(duì)節(jié)點(diǎn)的傳播影響力進(jìn)行排序,包括度中心性[15]、半局部度中心性[16]、特征向量中心性[17,18]、接近中心性[19]、介數(shù)中心性[20]、HITS[21]、PageRank[22,23]、LeaderRank[24]與H指數(shù)等[25].其中度排序方法最為簡(jiǎn)單直觀,但其精度有待進(jìn)一步提高;半局部中心性指標(biāo)有限地?cái)U(kuò)大了源節(jié)點(diǎn)領(lǐng)域的覆蓋范圍,在提高算法精度的同時(shí)兼顧了算法的時(shí)間復(fù)雜度.Kitsak等[26]提出了K核分解算法,該算法通過(guò)逐步剝離網(wǎng)絡(luò)外圍度數(shù)小的節(jié)點(diǎn),可以較為準(zhǔn)確地識(shí)別網(wǎng)絡(luò)中最有影響力的內(nèi)核節(jié)點(diǎn),但該方法對(duì)于網(wǎng)絡(luò)整體節(jié)點(diǎn)的排序結(jié)果粒度較粗,節(jié)點(diǎn)間的傳播影響力區(qū)分度不夠.核數(shù)中心性指標(biāo)[27]認(rèn)為節(jié)點(diǎn)的影響力由其鄰居在網(wǎng)絡(luò)中的地位決定,節(jié)點(diǎn)與網(wǎng)絡(luò)中K核值大的節(jié)點(diǎn)間存在的連接越多,則其影響力越大.Liu等[28]考慮多階鄰居節(jié)點(diǎn)的中心性,提出了一種鄰域中心性指標(biāo)用于評(píng)價(jià)節(jié)點(diǎn)影響力,發(fā)現(xiàn)算法排序效果并不總是隨著鄰居階數(shù)的增大而變好.段杰明等[29]基于自規(guī)避隨機(jī)游走思想,提出一種綜合考慮網(wǎng)絡(luò)結(jié)構(gòu)局域信息和標(biāo)簽擴(kuò)散的影響力排序算法.Liu等[30]綜合考慮傳染率、康復(fù)率和有限的時(shí)間步三個(gè)因素用于評(píng)價(jià)網(wǎng)絡(luò)節(jié)點(diǎn)影響力.更多關(guān)于節(jié)點(diǎn)傳播影響力排序方面的研究可以參見(jiàn)文獻(xiàn)[31—33].

最近,Bao等[34]指出節(jié)點(diǎn)的傳播影響力由節(jié)點(diǎn)與鄰域節(jié)點(diǎn)間的最短路徑數(shù)、最短路徑長(zhǎng)度以及傳播概率決定,并基于此設(shè)計(jì)了一種半局部(SP)算法用于評(píng)價(jià)節(jié)點(diǎn)傳播影響力.最短路徑表示節(jié)點(diǎn)間信息傳播途徑始終選擇最優(yōu)方式,然而實(shí)際上網(wǎng)絡(luò)中的消息、謠言或者資訊等在節(jié)點(diǎn)間進(jìn)行傳播時(shí)并不會(huì)遵循最短路徑,信息擴(kuò)散的過(guò)程更類似于隨機(jī)游走[35].在集聚系數(shù)高的網(wǎng)絡(luò)中,節(jié)點(diǎn)的局部高聚簇性有利于信息的有效擴(kuò)散,若只考慮信息按最優(yōu)傳播方式即最短路徑傳播,則會(huì)低估節(jié)點(diǎn)信息傳播的能力,從而降低節(jié)點(diǎn)影響力的排序精度.綜合考慮節(jié)點(diǎn)與局域三步內(nèi)鄰居的有效可達(dá)路徑及信息傳播率,本文提出了一種SP指標(biāo)的改進(jìn)算法,即ASP算法.在多個(gè)真實(shí)世界網(wǎng)絡(luò)和人工網(wǎng)絡(luò)中的實(shí)驗(yàn)表明,ASP算法與SP指標(biāo)、核數(shù)中心性指標(biāo)、半局部度中心性指標(biāo)以及介數(shù)中心性指標(biāo)相比,更能準(zhǔn)確評(píng)估節(jié)點(diǎn)的傳播影響力.

2 相關(guān)研究

假設(shè)無(wú)向網(wǎng)絡(luò)G=(V,E)包含|V|=N個(gè)節(jié)點(diǎn)和|E|=M條邊,其網(wǎng)絡(luò)結(jié)構(gòu)可用鄰接矩陣A=(aij)N×N表示,當(dāng)節(jié)點(diǎn)i與節(jié)點(diǎn)j之間存在連接時(shí),aij=1,否則aij=0.

2.1 度指標(biāo)

度排序方法最為簡(jiǎn)單直觀[15],ki表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)數(shù):

式中Λi表示節(jié)點(diǎn)i一跳鄰域內(nèi)的鄰居.度指標(biāo)反映了節(jié)點(diǎn)的直接影響力,信息從度越大的節(jié)點(diǎn)發(fā)起,網(wǎng)絡(luò)中第一時(shí)間接收到該信息的節(jié)點(diǎn)數(shù)越多,但度指標(biāo)忽略了鄰居節(jié)點(diǎn)間的差異性,導(dǎo)致其排序精度不高.

2.2 接近中心性

接近中心性(CC)反映了節(jié)點(diǎn)到達(dá)其他節(jié)點(diǎn)的難易程度[19],可表示為

式中dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離,N代表網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù).

2.3 介數(shù)指標(biāo)

介數(shù)指標(biāo)(BC)以網(wǎng)絡(luò)中經(jīng)過(guò)某個(gè)節(jié)點(diǎn)的最短路徑的數(shù)目來(lái)量化節(jié)點(diǎn)在網(wǎng)絡(luò)中的地位[20],定義為

式中g(shù)st表示從節(jié)點(diǎn)s到節(jié)點(diǎn)t的最短路徑數(shù),nist表示其中經(jīng)過(guò)節(jié)點(diǎn)i的最短路徑數(shù).

2.4 核數(shù)指標(biāo)

Bae和Kim[27]同時(shí)考慮節(jié)點(diǎn)度與鄰居節(jié)點(diǎn)的K核值,提出了一種核數(shù)指標(biāo)(Cnc)用于評(píng)價(jià)節(jié)點(diǎn)傳播影響力.該指標(biāo)定義為

式中K(j)表示節(jié)點(diǎn)j的K核值.

2.5 SP指標(biāo)

Bao等[34]從信息傳播的角度分析認(rèn)為,從網(wǎng)絡(luò)中的某一節(jié)點(diǎn)i發(fā)起的信息要成功傳遞到另一個(gè)節(jié)點(diǎn)j,其概率由節(jié)點(diǎn)i和j之間的最短路徑數(shù)目、最短路徑長(zhǎng)度以及信息傳播率決定,他們將網(wǎng)絡(luò)平均度〈k〉的倒數(shù)近似為信息傳播率,設(shè)計(jì)了SP指標(biāo)用于評(píng)價(jià)節(jié)點(diǎn)傳播影響力,表示為

式中φi表示與節(jié)點(diǎn)i距離小于等于網(wǎng)絡(luò)半徑的節(jié)點(diǎn)集合,nij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的最短路徑數(shù)目,nij(1/〈k〉)dij近似表示節(jié)點(diǎn)i成功將信息傳播至節(jié)點(diǎn)j的概率.

2.6 ASP指標(biāo)

實(shí)際上,信息按照最短路徑傳播只是理想中的路由方式.從某一個(gè)節(jié)點(diǎn)i發(fā)起的信息要最終傳遞至另一個(gè)節(jié)點(diǎn)j,信息傳遞的路徑理論上可以是i和j之間的任一可達(dá)路徑,因此在計(jì)算節(jié)點(diǎn)i將信息傳播至節(jié)點(diǎn)j的可能性時(shí),若只考慮最短路徑,必然會(huì)降低算法的精度.以圖1為例,由于只考慮最短路徑,節(jié)點(diǎn)i和k將信息傳遞至節(jié)點(diǎn)a的概率都為3(1/〈k〉)3.依次計(jì)算信息從節(jié)點(diǎn)傳遞到其他鄰域鄰居的概率,最終得到節(jié)點(diǎn)i和k的SP指標(biāo)值相等.然而直觀上由于節(jié)點(diǎn)i的局部高聚簇性,節(jié)點(diǎn)i將信息傳遞至a的過(guò)程中相比于節(jié)點(diǎn)k具有更多的路徑選擇,因此可以推斷節(jié)點(diǎn)i的傳播影響力大于節(jié)點(diǎn)k.疾病傳播模型(SIR模型)信息傳播仿真實(shí)驗(yàn)也驗(yàn)證了我們的猜想.

圖1 11個(gè)節(jié)點(diǎn)組成的網(wǎng)絡(luò)圖,節(jié)點(diǎn)感染概率取β=0.2(傳播閾值βth=0.3409)時(shí)在SIR模型上進(jìn)行2000次獨(dú)立仿真實(shí)驗(yàn)得到11個(gè)節(jié)點(diǎn)的信息傳播影響力Fig.1.A simple network with 11 nodes.The spreading in fl uence of each node is obtained by simulation on the SIR model over 2000 independent runs with β =0.2(βth=0.3409).

基于以上分析,我們?cè)O(shè)計(jì)了SP指標(biāo)的改進(jìn)算法,即ASP算法,其表達(dá)式為

式中fASP_ij表示節(jié)點(diǎn)i將信息傳播至節(jié)點(diǎn)j的成功率,Γi表示節(jié)點(diǎn)i三步內(nèi)的鄰居節(jié)點(diǎn)集合,l表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的可達(dá)路徑的長(zhǎng)度,nl表示節(jié)點(diǎn)i到節(jié)點(diǎn)j可達(dá)路徑長(zhǎng)度(不包括回路)為l的路徑總數(shù).

Fowler和Christakis[36]認(rèn)為節(jié)點(diǎn)的影響范圍不僅限于直接相鄰的節(jié)點(diǎn),還能間接影響與鄰居節(jié)點(diǎn)相鄰的節(jié)點(diǎn),三階以內(nèi)都可能產(chǎn)生影響,并提出了三階影響力原則.同時(shí)由于(1/〈k〉)l隨著l的增大會(huì)快速衰減,因此考慮所有的可達(dá)路徑并不必要,ASP算法只將節(jié)點(diǎn)與鄰域節(jié)點(diǎn)間長(zhǎng)度不大于3的可達(dá)路徑納入計(jì)算范圍.

對(duì)于一步鄰居節(jié)點(diǎn),

表1 ASP算法框架Table 1.The framework of ASP algorithm.

式中A代表網(wǎng)絡(luò)鄰接矩陣,A3(i,j)表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間長(zhǎng)度為3的所有可達(dá)路徑,A3(i,j)?|n(i)|?|n(j)|+1為消除可達(dá)路徑中的回路后剩下的路徑數(shù),|n(i)∩n(j)|表示節(jié)點(diǎn)i與節(jié)點(diǎn)j的共同鄰居數(shù),即長(zhǎng)度為2的路徑數(shù).

對(duì)于二步鄰居節(jié)點(diǎn),

對(duì)于節(jié)點(diǎn)i的二步鄰居節(jié)點(diǎn)j,節(jié)點(diǎn)i和節(jié)點(diǎn)j之間不存在長(zhǎng)度為3且有回路的路徑,因此節(jié)點(diǎn)i到節(jié)點(diǎn)j的可達(dá)路徑數(shù)為A3(i,j).

對(duì)于三步鄰居節(jié)點(diǎn),

以圖1中節(jié)點(diǎn)i與節(jié)點(diǎn)c為例說(shuō)明ASP計(jì)算過(guò)程.節(jié)點(diǎn)i到節(jié)點(diǎn)c路徑長(zhǎng)度為2的路徑有3條,路徑長(zhǎng)度為3的路徑有4條,根據(jù)ASP指標(biāo),可計(jì)算節(jié)點(diǎn)i成功傳遞信息至節(jié)點(diǎn)m的可能性為3(1/〈k〉)2+4(1/〈k〉)3, 同理, 可依次計(jì)算節(jié)點(diǎn)i傳遞信息至節(jié)點(diǎn)j,h,g與a的可能性,由此得到節(jié)點(diǎn)i的影響力值.

為降低計(jì)算復(fù)雜度,SP指標(biāo)只考慮三步內(nèi)的鄰居節(jié)點(diǎn).與SP指標(biāo)相比,ASP指標(biāo)多考慮了節(jié)點(diǎn)與一步鄰居中長(zhǎng)度為2和3的可達(dá)路徑以及與二步鄰居中長(zhǎng)度為3的可達(dá)路徑.盡管如此,通過(guò)表1中的算法框架依然可以看出,改進(jìn)指標(biāo)幾乎不增加計(jì)算的復(fù)雜度.

3 評(píng)價(jià)標(biāo)準(zhǔn)

實(shí)驗(yàn)采用Kendall tau相關(guān)系數(shù)[39,40]衡量各指標(biāo)排序結(jié)果的準(zhǔn)確性,其表達(dá)式為

4 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

為了驗(yàn)證各指標(biāo)評(píng)估節(jié)點(diǎn)傳播影響力的效果,實(shí)驗(yàn)選取6個(gè)真實(shí)數(shù)據(jù)集,包括Word,Netscience[41],Email[42],Yeast[43],Blog[44]和Router[45],這些網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)統(tǒng)計(jì)特征如表2所列.其中,N與M分別表示網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)與連邊數(shù),C表示網(wǎng)絡(luò)集聚系數(shù),D為網(wǎng)絡(luò)直徑,β表示傳播概率,βth=〈k〉/〈k2〉表示傳播閾值,其中〈k〉表示節(jié)點(diǎn)平均度,〈k2〉表示節(jié)點(diǎn)二階平均度.

表2 6個(gè)真實(shí)網(wǎng)絡(luò)的拓?fù)鋮?shù)Table 2.Topological parameters of six real networks.

圖2 六個(gè)真實(shí)網(wǎng)絡(luò)中不同指標(biāo)評(píng)估值與SIR模型感染節(jié)點(diǎn)數(shù)的相關(guān)性 (a)Word;(b)Netscience;(c)Yeast;(d)Email;(e)Blog;(f)RouterFig.2.Correlation between different ranking values and number of SIR model infected nodes in six real-world networks:(a)Word;(b)Netscience;(c)Yeast;(d)Email;(e)Blog;(f)Router.

圖2 六個(gè)真實(shí)網(wǎng)絡(luò)中不同指標(biāo)評(píng)估值與SIR模型感染節(jié)點(diǎn)數(shù)的相關(guān)性(續(xù)) (a)Word;(b)Netscience;(c)Yeast;(d)Email;(e)Blog;(f)RouterFig.2.Correlation between different ranking values and number of SIR model infected nodes in six real-world networks(continued):(a)Word;(b)Netscience;(c)Yeast;(d)Email;(e)Blog;(f)Router.

在6個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和3個(gè)模擬數(shù)據(jù)集上,比較提出的ASP指標(biāo)與SP指標(biāo)、度指標(biāo)、核數(shù)指標(biāo)、介數(shù)中心性指標(biāo)以及接近中心性指標(biāo).圖2描述了不同網(wǎng)絡(luò)中心性指標(biāo)與實(shí)際影響力Φ(i)之間的相關(guān)性,相關(guān)程度越高,表明算法對(duì)節(jié)點(diǎn)傳播影響力的測(cè)量越準(zhǔn)確.由于節(jié)點(diǎn)的影響力由最終被感染的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量決定,因此為了正確評(píng)價(jià)節(jié)點(diǎn)的真實(shí)影響力,感染概率β的值不宜選得過(guò)大或過(guò)小,若β值過(guò)小,信息傳播容易局限于節(jié)點(diǎn)鄰域.相反,若β值過(guò)大,不論傳染過(guò)程從哪個(gè)節(jié)點(diǎn)發(fā)起,整個(gè)網(wǎng)絡(luò)都很快被感染,很難區(qū)分單個(gè)個(gè)體的影響力.為保證傳播能夠進(jìn)行,實(shí)驗(yàn)設(shè)定感染概率β等于網(wǎng)絡(luò)傳播閾值βth,SIR實(shí)驗(yàn)獨(dú)立運(yùn)行1000次取平均結(jié)果.

圖3 (網(wǎng)刊彩色)不同指標(biāo)評(píng)估準(zhǔn)確性對(duì)比 (a)Word數(shù)據(jù)集;(b)Netscience數(shù)據(jù)集;(c)Email數(shù)據(jù)集;(d)Yeast數(shù)據(jù)集;(e)Blog數(shù)據(jù)集;(f)Router數(shù)據(jù)集Fig.3.(color online)Comparison of accuracy evaluation among various indices:(a)Word;(b)Netscience;(c)Email;(d)Yeast;(e)Blog;(f)Router.

從圖2可以看出,接近中心性和介數(shù)中心性指標(biāo)與SIR影響節(jié)點(diǎn)數(shù)的相關(guān)性相對(duì)較弱,接近中心性與SIR影響節(jié)點(diǎn)數(shù)總體呈正相關(guān),介數(shù)中心性的結(jié)果較為發(fā)散.這是因?yàn)樯鐣?huì)化網(wǎng)絡(luò)的社區(qū)化使得絕大多數(shù)節(jié)點(diǎn)的介數(shù)很小,通過(guò)介數(shù)進(jìn)行影響力排序,節(jié)點(diǎn)間區(qū)分度不大,而實(shí)際上網(wǎng)絡(luò)中介數(shù)相近的節(jié)點(diǎn)的傳播能力存在較大差異.SP指標(biāo)、核數(shù)中心性和ASP指標(biāo)的評(píng)估值與SIR影響節(jié)點(diǎn)數(shù)則呈現(xiàn)較強(qiáng)的正相關(guān)性,其中ASP指標(biāo)的相關(guān)性結(jié)果比SP指標(biāo)好,可見(jiàn)ASP指標(biāo)在評(píng)價(jià)節(jié)點(diǎn)傳播影響力時(shí)具有優(yōu)勢(shì).

在相關(guān)性實(shí)驗(yàn)中,信息傳播率為網(wǎng)絡(luò)傳播閾值,實(shí)驗(yàn)結(jié)果只體現(xiàn)特定傳播率下的相關(guān)性情況.為了更全面地評(píng)價(jià)各個(gè)指標(biāo)在不同傳播率下的排序準(zhǔn)確性,設(shè)置傳播率區(qū)間為[|βth|?7%,|βth|+7%](若βth≤0.07,傳播率區(qū)間取為[0.01,0.15]),并且將τ值作為準(zhǔn)確性度量值進(jìn)行實(shí)驗(yàn),結(jié)果如圖3所示.從圖中可以看出,傳播率較小時(shí)核數(shù)指標(biāo)準(zhǔn)確率普遍較高,這是由于核數(shù)指標(biāo)考慮了節(jié)點(diǎn)度與核數(shù),當(dāng)傳播率較小時(shí),從源節(jié)點(diǎn)發(fā)起的SIR傳播過(guò)程容易局限于局部鄰域,此時(shí)節(jié)點(diǎn)度越大感染到的節(jié)點(diǎn)也越多,核數(shù)指標(biāo)正好適合這一情況.當(dāng)傳播率在傳播閾值附近時(shí),除了Router網(wǎng)絡(luò),ASP指標(biāo)的準(zhǔn)確性比其他指標(biāo)高,這是因?yàn)閭鞑ヂ蔬m中時(shí),節(jié)點(diǎn)局部高聚簇性能夠使節(jié)點(diǎn)獲得更多的將信息擴(kuò)散出去的途徑,ASP指標(biāo)充分考慮了這種因素.當(dāng)傳播率更大時(shí),可以發(fā)現(xiàn)ASP指標(biāo)的優(yōu)勢(shì)與SP指標(biāo)相比在逐漸削弱,這是因?yàn)閭鞑ヂ蚀蟮揭欢ǔ潭葧r(shí),信息可以輕易地?cái)U(kuò)散出去,此時(shí)節(jié)點(diǎn)的局部聚簇性對(duì)信息的擴(kuò)散作用并不明顯.在Router網(wǎng)絡(luò)中,由于網(wǎng)絡(luò)結(jié)構(gòu)較為稀疏,節(jié)點(diǎn)間的冗余鏈接少,因此ASP指標(biāo)與SP指標(biāo)的實(shí)驗(yàn)結(jié)果相差不多.

5 模擬數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

除了真實(shí)數(shù)據(jù)集,實(shí)驗(yàn)還使用了Lancichinetii-Fortunato-Radicchi(LFR)[46]數(shù)據(jù)模型生成的人工數(shù)據(jù)集.通過(guò)設(shè)置不同的LFR參數(shù),可以生成不同拓?fù)涮卣鞯木W(wǎng)絡(luò)結(jié)構(gòu).設(shè)置LFR參數(shù)如下:N=2000,cmin=20,cmax=50,kmax=30,μ=0.1,其中N為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù),cmin和cmax分別代表社區(qū)的最小和最大規(guī)模,kmax表示網(wǎng)絡(luò)的最大度,μ為混合參數(shù).調(diào)整平均度〈k〉來(lái)調(diào)節(jié)網(wǎng)絡(luò)的緊密程度,分別生成〈k〉=5,10,15的三個(gè)網(wǎng)絡(luò)數(shù)據(jù)集.

三個(gè)模擬數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如圖4所示,實(shí)驗(yàn)結(jié)果證明隨著網(wǎng)絡(luò)稀疏性與信息傳播率的變化,ASP指標(biāo)與SP指標(biāo)對(duì)節(jié)點(diǎn)影響力排序的相對(duì)準(zhǔn)確性也發(fā)生變化.在〈k〉=5與〈k〉=10的LFR數(shù)據(jù)集中,傳播率較小時(shí),SP指標(biāo)略優(yōu)于ASP指標(biāo),這個(gè)結(jié)果與真實(shí)數(shù)據(jù)集上的原因類似,都是因?yàn)閭鞑ヂ势r(shí)節(jié)點(diǎn)的真實(shí)影響力接近于度;當(dāng)傳播率更大時(shí),ASP指標(biāo)相比其他指標(biāo)有明顯的優(yōu)勢(shì).尤其在集聚程度高的網(wǎng)絡(luò)中,如圖4(c)所示,ASP指標(biāo)在不同傳播率下比SP指標(biāo)更具有優(yōu)勢(shì).

圖4 (網(wǎng)刊彩色)LFR模擬數(shù)據(jù)集上各指標(biāo)影響力排序準(zhǔn)確性對(duì)比 (a)〈k〉=5;(b)〈k〉=10;(c)〈k〉=15Fig.4.(color online)Comparison of accuracy evaluation among different centralities on three LFR datasets:(a) 〈k〉=5;(b) 〈k〉=10;(c) 〈k〉=15.

6 考慮不同階次內(nèi)的鄰居對(duì)算法排序結(jié)果的影響

最后比較了ASP算法考慮不同階次內(nèi)鄰居時(shí)的排序效果,考慮到(1/〈k〉)l隨著l的增大會(huì)快速衰減,因此對(duì)于4階及4階以上的鄰居,只將其最短路徑納入計(jì)算范圍.結(jié)果如圖5所示,算法效果并不總是隨著階次的提高而變好,大多在3階處取得最優(yōu).可見(jiàn)考慮更高階的鄰居,只會(huì)增大算法的計(jì)算復(fù)雜度,對(duì)算法精度的提升幫助并不大,因此ASP算法只將節(jié)點(diǎn)與鄰域節(jié)點(diǎn)間三步內(nèi)的鄰居納入計(jì)算范圍.

圖5 (網(wǎng)刊彩色)不同階次內(nèi)鄰居對(duì)算法排序結(jié)果的影響(S表示算法中鄰居節(jié)點(diǎn)的最高層級(jí))Fig.5.(color online)The e ff ect of neighbors in different orders on the results of algorithm sorting(S represents the highest order of neighbor nodes in the algorithm).

7 結(jié) 論

準(zhǔn)確度量復(fù)雜系統(tǒng)中節(jié)點(diǎn)的傳播影響力,對(duì)于控制流言在網(wǎng)絡(luò)中的傳播、預(yù)防網(wǎng)絡(luò)攻擊、設(shè)計(jì)有效的廣告投放策略等具有現(xiàn)實(shí)意義.綜合考慮節(jié)點(diǎn)與三步內(nèi)鄰居間的有效可達(dá)路徑以及信息傳播率,本文提出了一種SP指標(biāo)的改進(jìn)算法,ASP算法.在同樣只考慮三步內(nèi)鄰居的條件下,與SP指標(biāo)相比,ASP指標(biāo)幾乎不增加算法復(fù)雜度.在多個(gè)真實(shí)數(shù)據(jù)集和人工數(shù)據(jù)集上的實(shí)驗(yàn)證明,本文提出的指標(biāo)可以在更廣的信息傳播率下取得更為準(zhǔn)確的排序結(jié)果.本文算法對(duì)于理解節(jié)點(diǎn)局部聚簇性對(duì)節(jié)點(diǎn)傳播影響力的影響具有一定意義.

[1]Dorogovtsev S N,Mendes J F F,Samukhin A N 2000Phys.Rev.Lett.85 4633

[2]Lü L Y,Medo M,Yeung C H,Zhang Y C,Zhang Z K,Zhou T 2012Phys.Rep.59 1

[3]Papadopoulos F,Kitsak M,Serrano M A,Boguna M,Krioukov D 2012Nature489 537

[4]Tang J,Piera M A,Guasch T 2016Transport Res.C67 357

[5]Barabási A L,Albert R 1999Science286 509

[6]Watts D J,Strogatz S H 1998Nature393 440

[7]Lü L Y,Chen D B,Zhou T 2011New J.Phys.13 123005

[8]Medo M,Zhang Y C,Zhou T 2009Europhys.Lett.88 38005

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

[10]Albert R,Barabási A L 2002Rev.Modern Phys.74 47

[11]Castellano C,Fortunato S,Loreto V 2009Rev.Modern Phys.81 591

[12]Yang J,Yao C,Ma W,Chen G 2010Physica A389 859

[13]Morone F,Makse H A 2015Nature524 65

[14]Zhang J X,Chen D B,Zhao Z D 2016Sci.Rep.6

[15]Albert R,Jeong H,Barabási A L 1999Nature401 130

[16]Chen D B,Lu L Y,Shang M S,Zhang Y C,Zhou T 2012Physica A391 1777

[17]Stephenson K,Zelen M 1989Soc.Netw.1 11

[18]Borgatti S P 2005Soc.Netw.27 55

[19]Sabidussi G 1966Psychometrika31 581

[20]Freeman L C 1977Sociometry40 35

[21]Kleinberg J M 1999JACM46 604

[22]Brin S,Page L 1998Comput.Networks.Isdn.30 107

[23]Radicchi F,Fortunato S,Markines B,Vespignani A 2009Phys.Rev.E80 056103

[24]Lü L Y,Zhang Y C,Yeung C H,Zhou T 2011PLoS ONE6 e21202

[25]Lü L Y,Zhou T,Zhang Q M,Stanley H E 2016Nat.Commun.7 10168

[26]Kitsak M,Gallos L K,Havlin S,Liljeros F,Muchnik L,Stanley H E,Makse H A 2010Nat.Phys.6 888

[27]Bae J,Kim S 2014Physica A395 549

[28]Liu Y,Tang M,Zhou T,Do Y 2016Physica A452 289

[29]Duan J M,Shang M S,Cai S M,Zhang Y X 2015Acta Phys.Sin.64 200501(in Chinese)[段杰明,尚明生,蔡世民,張玉霞2015物理學(xué)報(bào)64 200501]

[30]Liu J G,Lin J H,Guo Q,Zhou T 2016Sci.Rep.6 21380

[31]Liu J G,Ren Z M,Guo Q,Wang B H 2013Acta Phys.Sin.62 178901(in Chinese)[劉建國(guó),任卓明,郭強(qiáng),汪秉宏2013物理學(xué)報(bào)62 178901]

[32]Ren X L,Lü L Y 2014Chin.Sci.Bull.59 1175(in Chinese)[任曉龍,呂琳媛 2014科學(xué)通報(bào) 59 1175]

[33]Lü L Y,Chen D B,Ren X L,Zhang Q M,Zhang Y C,Zhou T 2016Phys.Rep.650 1

[34]Bao Z K,Ma C,Xiang B B,Zhang H F 2017Physica A468 391

[35]Newman M E J 2005Soc.Netw.27 39

[36]Fowler J H,Christakis N A 2008Br.Med.J.337 a2338

[37]Newman M E J 2002Phys.Rev.E66 016128

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

[39]Kendall M G 1945Biometrika33 239

[40]Knight W R 1966J.Amer.Statist.Assoc.61 436

[41]Newman M E J 2006Phys.Rev.E74 036104

[42]Guimera R,Danon L,Diaz-Guilera A,Giralt F,Arenas A 2003Phys.Rev.E68 065103

[43]Jeong H,Mason S P,Barabasi A,Oltvai Z N 2001Nature1 41

[44]Xie N 2006M.S.Dissertation(Bristol:University of Bristol)

[45]Spring N,Mahajan R,Wetherall D 2002IEEEACM Trans.Netw.1 2

[46]Lancichinetti A,Fortunato S,Radicchi F 2008Phys.Rev.E78 046110

An improved evaluating method of node spreading in fl uence in complex network based on information spreading probability?

Ruan Yi-Run1)?Lao Song-Yang1)Wang Jun-De1)Bai Liang1)Hou Lü-Lin2)
1)(Science and Technology on Information Systems Engineering Laboratory,National University of Defense Technology,Changsha 410073,China)
2)(Joint Service College,National Defense University,Beijing 100858,China)

19 May 2017;revised manuscript

4 July 2017)

How to evaluate the node spreading ability and how to fi nd in fl uential nodes in complex networks are crucial to controlling diseases and rumors,accelerating or hindering information from di ff using,and designing e ff ective advertising strategies for viral marketing,etc.At present,many indicators based on the shortest path,such as closeness centrality,betweenness centrality and the(SP)index have been proposed to evaluate node spreading in fl uence.The shortest path indicates that the information transmission path between nodes always selects the optimal mode.However,information does not know the ideal route from one place to another.The message does not fl ow only along geodesic paths in most networks,and information transmission path may be any reachable path between nodes.In the network with high clustering coefficient,the local high clustering of the nodes is bene fi cial to the large-scale dissemination of information.If only the information is transmitted according to the optimal propagation mode,which is the shortest path propagation,the ability to disseminate the node information would be underestimated,and thus the sorting precision of node spreading in fl uence is reduced.By taking into account the transmission rate and the reachable path between a node and its threestep inner neighbors,we design an improved method named ASP to generate ranking list to evaluate the node spreading ability.We make use of the susceptible-infected-recovered(SIR)spreading model with tunable transmission rate to check the e ff ectiveness of the proposed method on six real-world networks and three arti fi cial networks generated by the Lancichinetii-Fortunato-Radicchi(LFR)benchmark model.In the real data sets,the proposed algorithm can achieve a better result than other metrics in a wide range of transmission rate,especially in networks with high clustering coefficients.The experimental results of the three LFR benchmark datasets show that the relative accuracy of ranking result of the ASP index and the SP index changes with the sparseness of the network and the information transmission rate.When the information dissemination rate is small,SP index is slightly better than the ASP index.The reason for this result is that when the transmission rate is small,the node in fl uence is close to the degree.However,when the transmission rate is greater,the accuracy of the ASP index is higher than those of other indicators.This work can shed light on how the local clustering exerts an in fl uence on the node propagation.

complex network,spreading in fl uence,information spreading probability,transmission path

(2017年5月19日收到;2017年7月4日收到修改稿)

10.7498/aps.66.208901

?國(guó)家自然科學(xué)基金(批準(zhǔn)號(hào):61302144,61603408)資助的課題.

?通信作者.E-mail:ruanyirun@163.com

?2017中國(guó)物理學(xué)會(huì)Chinese Physical Society

http://wulixb.iphy.ac.cn

PACS:89.75.Fb,89.75.HcDOI:10.7498/aps.66.208901

*Project supported by the National Natural Science Foundation of China(Grant Nos.61302144,61603408).

?Corresponding author.E-mail:ruanyirun@163.com