一種改進的基于信息傳播率的復雜網絡影響力評估算法?

阮逸潤 老松楊 王竣德 白亮 侯綠林

1)(國防科技大學,信息系統工程重點實驗室,長沙 410073)

2)(國防大學聯合勤務學院,北京 100858)

一種改進的基于信息傳播率的復雜網絡影響力評估算法?

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

1)(國防科技大學,信息系統工程重點實驗室,長沙 410073)

2)(國防大學聯合勤務學院,北京 100858)

復雜網絡,傳播影響力,信息傳播率,傳播路徑

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

1 引 言

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

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

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

2 相關研究

假設無向網絡G=(V,E)包含|V|=N個節點和|E|=M條邊,其網絡結構可用鄰接矩陣A=(aij)N×N表示,當節點i與節點j之間存在連接時,aij=1,否則aij=0.

2.1 度指標

度排序方法最為簡單直觀[15],ki表示節點i的鄰居節點數:

式中Λi表示節點i一跳鄰域內的鄰居.度指標反映了節點的直接影響力,信息從度越大的節點發起,網絡中第一時間接收到該信息的節點數越多,但度指標忽略了鄰居節點間的差異性,導致其排序精度不高.

2.2 接近中心性

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

式中dij為節點i到節點j的距離,N代表網絡節點總數.

2.3 介數指標

介數指標(BC)以網絡中經過某個節點的最短路徑的數目來量化節點在網絡中的地位[20],定義為

式中gst表示從節點s到節點t的最短路徑數,nist表示其中經過節點i的最短路徑數.

2.4 核數指標

Bae和Kim[27]同時考慮節點度與鄰居節點的K核值,提出了一種核數指標(Cnc)用于評價節點傳播影響力.該指標定義為

式中K(j)表示節點j的K核值.

2.5 SP指標

Bao等[34]從信息傳播的角度分析認為,從網絡中的某一節點i發起的信息要成功傳遞到另一個節點j,其概率由節點i和j之間的最短路徑數目、最短路徑長度以及信息傳播率決定,他們將網絡平均度〈k〉的倒數近似為信息傳播率,設計了SP指標用于評價節點傳播影響力,表示為

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

2.6 ASP指標

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

圖1 11個節點組成的網絡圖,節點感染概率取β=0.2(傳播閾值βth=0.3409)時在SIR模型上進行2000次獨立仿真實驗得到11個節點的信息傳播影響力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).

基于以上分析,我們設計了SP指標的改進算法,即ASP算法,其表達式為

式中fASP_ij表示節點i將信息傳播至節點j的成功率,Γi表示節點i三步內的鄰居節點集合,l表示節點i到節點j的可達路徑的長度,nl表示節點i到節點j可達路徑長度(不包括回路)為l的路徑總數.

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

對于一步鄰居節點,

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

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

對于二步鄰居節點,

對于節點i的二步鄰居節點j,節點i和節點j之間不存在長度為3且有回路的路徑,因此節點i到節點j的可達路徑數為A3(i,j).

對于三步鄰居節點,

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

為降低計算復雜度,SP指標只考慮三步內的鄰居節點.與SP指標相比,ASP指標多考慮了節點與一步鄰居中長度為2和3的可達路徑以及與二步鄰居中長度為3的可達路徑.盡管如此,通過表1中的算法框架依然可以看出,改進指標幾乎不增加計算的復雜度.

3 評價標準

實驗采用Kendall tau相關系數[39,40]衡量各指標排序結果的準確性,其表達式為

4 真實數據集實驗結果

為了驗證各指標評估節點傳播影響力的效果,實驗選取6個真實數據集,包括Word,Netscience[41],Email[42],Yeast[43],Blog[44]和Router[45],這些網絡的拓撲結構統計特征如表2所列.其中,N與M分別表示網絡節點數與連邊數,C表示網絡集聚系數,D為網絡直徑,β表示傳播概率,βth=〈k〉/〈k2〉表示傳播閾值,其中〈k〉表示節點平均度,〈k2〉表示節點二階平均度.

表2 6個真實網絡的拓撲參數Table 2.Topological parameters of six real networks.

圖2 六個真實網絡中不同指標評估值與SIR模型感染節點數的相關性 (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 六個真實網絡中不同指標評估值與SIR模型感染節點數的相關性(續) (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個真實網絡數據集和3個模擬數據集上,比較提出的ASP指標與SP指標、度指標、核數指標、介數中心性指標以及接近中心性指標.圖2描述了不同網絡中心性指標與實際影響力Φ(i)之間的相關性,相關程度越高,表明算法對節點傳播影響力的測量越準確.由于節點的影響力由最終被感染的網絡節點數量決定,因此為了正確評價節點的真實影響力,感染概率β的值不宜選得過大或過小,若β值過小,信息傳播容易局限于節點鄰域.相反,若β值過大,不論傳染過程從哪個節點發起,整個網絡都很快被感染,很難區分單個個體的影響力.為保證傳播能夠進行,實驗設定感染概率β等于網絡傳播閾值βth,SIR實驗獨立運行1000次取平均結果.

圖3 (網刊彩色)不同指標評估準確性對比 (a)Word數據集;(b)Netscience數據集;(c)Email數據集;(d)Yeast數據集;(e)Blog數據集;(f)Router數據集Fig.3.(color online)Comparison of accuracy evaluation among various indices:(a)Word;(b)Netscience;(c)Email;(d)Yeast;(e)Blog;(f)Router.

從圖2可以看出,接近中心性和介數中心性指標與SIR影響節點數的相關性相對較弱,接近中心性與SIR影響節點數總體呈正相關,介數中心性的結果較為發散.這是因為社會化網絡的社區化使得絕大多數節點的介數很小,通過介數進行影響力排序,節點間區分度不大,而實際上網絡中介數相近的節點的傳播能力存在較大差異.SP指標、核數中心性和ASP指標的評估值與SIR影響節點數則呈現較強的正相關性,其中ASP指標的相關性結果比SP指標好,可見ASP指標在評價節點傳播影響力時具有優勢.

在相關性實驗中,信息傳播率為網絡傳播閾值,實驗結果只體現特定傳播率下的相關性情況.為了更全面地評價各個指標在不同傳播率下的排序準確性,設置傳播率區間為[|βth|?7%,|βth|+7%](若βth≤0.07,傳播率區間取為[0.01,0.15]),并且將τ值作為準確性度量值進行實驗,結果如圖3所示.從圖中可以看出,傳播率較小時核數指標準確率普遍較高,這是由于核數指標考慮了節點度與核數,當傳播率較小時,從源節點發起的SIR傳播過程容易局限于局部鄰域,此時節點度越大感染到的節點也越多,核數指標正好適合這一情況.當傳播率在傳播閾值附近時,除了Router網絡,ASP指標的準確性比其他指標高,這是因為傳播率適中時,節點局部高聚簇性能夠使節點獲得更多的將信息擴散出去的途徑,ASP指標充分考慮了這種因素.當傳播率更大時,可以發現ASP指標的優勢與SP指標相比在逐漸削弱,這是因為傳播率大到一定程度時,信息可以輕易地擴散出去,此時節點的局部聚簇性對信息的擴散作用并不明顯.在Router網絡中,由于網絡結構較為稀疏,節點間的冗余鏈接少,因此ASP指標與SP指標的實驗結果相差不多.

5 模擬數據集上的實驗結果

除了真實數據集,實驗還使用了Lancichinetii-Fortunato-Radicchi(LFR)[46]數據模型生成的人工數據集.通過設置不同的LFR參數,可以生成不同拓撲特征的網絡結構.設置LFR參數如下:N=2000,cmin=20,cmax=50,kmax=30,μ=0.1,其中N為網絡節點數,cmin和cmax分別代表社區的最小和最大規模,kmax表示網絡的最大度,μ為混合參數.調整平均度〈k〉來調節網絡的緊密程度,分別生成〈k〉=5,10,15的三個網絡數據集.

三個模擬數據集上的實驗結果如圖4所示,實驗結果證明隨著網絡稀疏性與信息傳播率的變化,ASP指標與SP指標對節點影響力排序的相對準確性也發生變化.在〈k〉=5與〈k〉=10的LFR數據集中,傳播率較小時,SP指標略優于ASP指標,這個結果與真實數據集上的原因類似,都是因為傳播率偏小時節點的真實影響力接近于度;當傳播率更大時,ASP指標相比其他指標有明顯的優勢.尤其在集聚程度高的網絡中,如圖4(c)所示,ASP指標在不同傳播率下比SP指標更具有優勢.

圖4 (網刊彩色)LFR模擬數據集上各指標影響力排序準確性對比 (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 考慮不同階次內的鄰居對算法排序結果的影響

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

圖5 (網刊彩色)不同階次內鄰居對算法排序結果的影響(S表示算法中鄰居節點的最高層級)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 結 論

準確度量復雜系統中節點的傳播影響力,對于控制流言在網絡中的傳播、預防網絡攻擊、設計有效的廣告投放策略等具有現實意義.綜合考慮節點與三步內鄰居間的有效可達路徑以及信息傳播率,本文提出了一種SP指標的改進算法,ASP算法.在同樣只考慮三步內鄰居的條件下,與SP指標相比,ASP指標幾乎不增加算法復雜度.在多個真實數據集和人工數據集上的實驗證明,本文提出的指標可以在更廣的信息傳播率下取得更為準確的排序結果.本文算法對于理解節點局部聚簇性對節點傳播影響力的影響具有一定意義.

[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物理學報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)[劉建國,任卓明,郭強,汪秉宏2013物理學報62 178901]

[32]Ren X L,Lü L Y 2014Chin.Sci.Bull.59 1175(in Chinese)[任曉龍,呂琳媛 2014科學通報 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

?國家自然科學基金(批準號:61302144,61603408)資助的課題.

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

?2017中國物理學會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