蘇臻 高超 李向華

(西南大學(xué)計(jì)算機(jī)與信息科學(xué)學(xué)院,重慶 400715)

節(jié)點(diǎn)中心性對(duì)復(fù)雜網(wǎng)絡(luò)傳播模式的影響分析?

蘇臻 高超?李向華

(西南大學(xué)計(jì)算機(jī)與信息科學(xué)學(xué)院,重慶 400715)

(2017年1月8日收到;2017年3月11日收到修改稿)

在眾多的重要節(jié)點(diǎn)評(píng)估方法研究中,具有較高中心性的節(jié)點(diǎn)一直是關(guān)注的焦點(diǎn),許多傳播行為的研究也主要圍繞高中心性節(jié)點(diǎn)展開(kāi),因此在一定程度上忽略了低中心性節(jié)點(diǎn)對(duì)傳播行為的影響.本文從傳播異構(gòu)性角度,通過(guò)初始感染最大中心性節(jié)點(diǎn)和最小中心性節(jié)點(diǎn)揭示網(wǎng)絡(luò)結(jié)構(gòu)異構(gòu)性對(duì)信息傳播的影響.實(shí)驗(yàn)結(jié)果表明,傳播過(guò)程中存在“鏈型”和“扇型”兩種傳播模式,在初始感染比例不斷提升的情況下,兩種傳播模式的相互轉(zhuǎn)換引發(fā)傳播速率的變化,進(jìn)一步促使非線性傳播規(guī)模交叉現(xiàn)象的產(chǎn)生.這一現(xiàn)象說(shuō)明,在宏觀的信息傳播過(guò)程中,最小中心性節(jié)點(diǎn)的影響力不容忽視,尤其在初始感染比例升高時(shí),最小中心性節(jié)點(diǎn)比最大中心性節(jié)點(diǎn)更具傳播優(yōu)勢(shì).

復(fù)雜網(wǎng)絡(luò),結(jié)構(gòu)異構(gòu)性,中心性,傳播速率

1 引 言

復(fù)雜網(wǎng)絡(luò)中的重要節(jié)點(diǎn)挖掘作為網(wǎng)絡(luò)科學(xué)的重要研究?jī)?nèi)容之一,已經(jīng)被應(yīng)用到諸多領(lǐng)域,尤其在各類傳播行為(如流行病爆發(fā)[1]、信息擴(kuò)散[2]、病毒傳播[3])的研究中體現(xiàn)得尤為重要.所謂重要節(jié)點(diǎn)是指相比于網(wǎng)絡(luò)中的其他節(jié)點(diǎn),能夠?qū)W(wǎng)絡(luò)的整體結(jié)構(gòu)(如網(wǎng)絡(luò)連通性、平均距離等)以及功能(如網(wǎng)絡(luò)的魯棒性、同步等)產(chǎn)生重要影響力的一類特殊節(jié)點(diǎn),其影響力主要體現(xiàn)在當(dāng)這部分占比極少的節(jié)點(diǎn)受到影響時(shí),會(huì)加速傳播過(guò)程,擴(kuò)大傳播規(guī)模[4,5].由此可見(jiàn),對(duì)于重要節(jié)點(diǎn)的挖掘非常重要.

目前,已有很多指標(biāo)用于評(píng)估節(jié)點(diǎn)中心性(或者說(shuō)影響力、重要性)[6,7],比如度數(shù)[8]、核數(shù)[9]、介數(shù)[10]以及特征向量中心性[11]等.盡管已有方法對(duì)傳播行為控制[12]、傳播源定位[13,14]以及傳播網(wǎng)絡(luò)推演[15]等起到了重要作用,但是這些研究都將研究的重點(diǎn)集中在具有較高中心性的節(jié)點(diǎn)上,在一定程度上忽視了具有較低中心性的節(jié)點(diǎn)對(duì)傳播行為的影響.因此,本著探究復(fù)雜網(wǎng)絡(luò)中傳播行為異構(gòu)性的思路,首先發(fā)現(xiàn)了兩種不同的傳播模式(“鏈型”和“扇型”),然后通過(guò)實(shí)驗(yàn)展現(xiàn)最大、最小中心性節(jié)點(diǎn)對(duì)傳播過(guò)程的影響.

本文基于四種常用的中心性評(píng)估指標(biāo)(度數(shù)、核數(shù)、介數(shù)和特征向量),通過(guò)大量的傳播仿真實(shí)驗(yàn),揭示了傳播過(guò)程中的兩種傳播模式(“鏈型”和“扇型”)以及傳播規(guī)模交叉現(xiàn)象,即隨著初始感染比例的升高,初始感染最小中心性節(jié)點(diǎn)情況下的病毒傳播規(guī)模以及傳播速率會(huì)超越初始感染最大中心性節(jié)點(diǎn)的情況.與此同時(shí),伴隨著初始感染比例的提升,兩種傳播過(guò)程下的傳播規(guī)模交叉時(shí)間點(diǎn)不斷提前.這一現(xiàn)象一方面說(shuō)明節(jié)點(diǎn)中心性的高低對(duì)信息傳播起著重要作用,另一方面也反映復(fù)雜網(wǎng)絡(luò)中傳播行為的復(fù)雜性.

2 結(jié)構(gòu)異構(gòu)性

2.1 網(wǎng)絡(luò)結(jié)構(gòu)異構(gòu)性分析

從網(wǎng)絡(luò)的全局結(jié)構(gòu)特征考慮,常見(jiàn)的規(guī)則網(wǎng)絡(luò)模型(如全局耦合網(wǎng)絡(luò)、最近鄰耦合網(wǎng)絡(luò)以及星形耦合網(wǎng)絡(luò))在整體結(jié)構(gòu)上表現(xiàn)出網(wǎng)絡(luò)平均距離小、鏈接度比較高的特點(diǎn)[16],但節(jié)點(diǎn)間的差異性不明顯,無(wú)法對(duì)實(shí)際網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行很好的刻畫(huà).與規(guī)則網(wǎng)絡(luò)相反的隨機(jī)網(wǎng)絡(luò),雖然與實(shí)際網(wǎng)絡(luò)存在相似的稀疏性、最大塊特性以及小世界特性,但在聚類特性以及度分布上仍然存在明顯的差異.考慮到規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)分別在刻畫(huà)實(shí)際網(wǎng)絡(luò)小世界特征與聚類特性時(shí)的不足,小世界網(wǎng)絡(luò)模型作為過(guò)渡模型被提出[17].由于Erdos-Renyi隨機(jī)圖和Watts-Strogatz小世界模型中網(wǎng)絡(luò)的度分布可利用泊松分布來(lái)近似刻畫(huà),因此這類網(wǎng)絡(luò)也被稱為均勻網(wǎng)絡(luò)或指數(shù)網(wǎng)絡(luò)[18].與此同時(shí),Barabási和Albert[19]于1999年提出的Barabási-Albert(BA)無(wú)標(biāo)度網(wǎng)絡(luò)模型作為揭示復(fù)雜網(wǎng)絡(luò)無(wú)標(biāo)度特性的經(jīng)典模型,使得無(wú)標(biāo)度網(wǎng)絡(luò)成為當(dāng)今網(wǎng)絡(luò)科學(xué)研究的重要課題之一[20].

從網(wǎng)絡(luò)傳播的角度考慮,對(duì)于均勻網(wǎng)絡(luò),存在一個(gè)有限的正傳播臨界值表示網(wǎng)絡(luò)的平均度),當(dāng)且僅當(dāng)有效傳播率λ大于λc時(shí),傳播行為才能得以保證并最終達(dá)到某一平衡狀態(tài).在無(wú)標(biāo)度網(wǎng)絡(luò)中,傳播臨界值對(duì)于冪指數(shù)為2<γ≤3的無(wú)標(biāo)度網(wǎng)絡(luò),當(dāng)網(wǎng)絡(luò)規(guī)模無(wú)限增大時(shí),該臨界值趨于0,即只要存在傳播源,傳播行為就會(huì)在整個(gè)網(wǎng)絡(luò)中蔓延[21,22].但這些分析有個(gè)假設(shè),即利用平均場(chǎng)理論進(jìn)行分析,使用平均度來(lái)度量網(wǎng)絡(luò)異構(gòu)性.然而,鑒于節(jié)點(diǎn)位置差異導(dǎo)致網(wǎng)絡(luò)異構(gòu)性(如中心性大小),尚需進(jìn)行仿真分析.

2.2 節(jié)點(diǎn)結(jié)構(gòu)異構(gòu)性分析

從前面的分析可知,在規(guī)則網(wǎng)絡(luò)中節(jié)點(diǎn)間的差異性(如度差異性)不明顯,而在指數(shù)網(wǎng)絡(luò)以及無(wú)標(biāo)度網(wǎng)絡(luò)中這種差異性表現(xiàn)突出,正是源于這種差異性造成了各節(jié)點(diǎn)中心性的差異.

本文從眾多評(píng)估方法中選擇四種常用指標(biāo)(節(jié)點(diǎn)度、核數(shù)、介數(shù)和特征向量),討論結(jié)構(gòu)異構(gòu)性對(duì)傳播過(guò)程的影響.度中心性是刻畫(huà)節(jié)點(diǎn)重要性最簡(jiǎn)單的指標(biāo),節(jié)點(diǎn)的度數(shù)越大則認(rèn)為其影響力越高,因此度中心性主要是對(duì)節(jié)點(diǎn)的局部影響力進(jìn)行刻畫(huà)[8,23].k-core分解與k-shell分解相似[9],都是對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)重要性的一種粗?；瘎澐?同樣地,k-core值越大則認(rèn)為節(jié)點(diǎn)的影響力越高,利用k-core劃分在某些情況下能排除某些度中心性較高的節(jié)點(diǎn)從而找出具有更高影響力的節(jié)點(diǎn).介數(shù)中心性刻畫(huà)了節(jié)點(diǎn)對(duì)于網(wǎng)絡(luò)中沿最短路徑傳輸?shù)男畔⒘鞯目刂屏10],即經(jīng)過(guò)某一節(jié)點(diǎn)的最短路徑越多則認(rèn)為節(jié)點(diǎn)的重要性越高.介數(shù)中心性在控制網(wǎng)絡(luò)傳播[24]、對(duì)度中心性相同的節(jié)點(diǎn)進(jìn)行更精確的劃分等方面能起到重要作用[25].特征向量中心性在考慮節(jié)點(diǎn)度的同時(shí)也考慮了鄰居節(jié)點(diǎn)的重要性[11],所以特征向量中心性能夠?qū)?jié)點(diǎn)的長(zhǎng)期影響力進(jìn)行很好的刻畫(huà).

2.3 兩種傳播模式

基于已有的研究,從直觀的傳播效果來(lái)看,如果節(jié)點(diǎn)中心性越高,則認(rèn)為其影響力越大,傳播能力越強(qiáng),因此這類節(jié)點(diǎn)被作為傳播源的研究也相對(duì)廣泛.但是,在真實(shí)的傳播網(wǎng)絡(luò)中,并不是所有的傳播行為都是從高中心性節(jié)點(diǎn)開(kāi)始,從低中心性節(jié)點(diǎn)開(kāi)始的傳播行為在現(xiàn)實(shí)情況下也普遍存在.

本文通過(guò)前期實(shí)驗(yàn)發(fā)現(xiàn),在信息傳播過(guò)程中,由于網(wǎng)絡(luò)結(jié)構(gòu)的影響,存在兩種可相互轉(zhuǎn)換的傳播模式:“扇型”和“鏈型”,如圖1所示.

圖1 (網(wǎng)刊彩色)傳播過(guò)程中的兩種傳播模式 (a)“扇型”向“鏈型”轉(zhuǎn)變;(b)“鏈型”向“扇型”轉(zhuǎn)變Fig.1.(color online)Two kinds of propagation processes:(a)The change of di ff usion process from “fan-shaped”type to “single-strand”type if the highest-degree nodes are infected sources;(b)the change of di ff usion process from“single-strand” type to “fan-shaped” type if the lowest-degree nodes are infected sources.

當(dāng)傳播過(guò)程從高中心性節(jié)點(diǎn)開(kāi)始時(shí),如圖1(a)所示,紅色傳播源均是高度數(shù)的節(jié)點(diǎn),在短時(shí)間內(nèi),呈現(xiàn)出“扇型”的擴(kuò)散方式,所以信息傳播的速率相對(duì)較快.但是,隨著傳播的繼續(xù),一方面,越來(lái)越多的高鏈接度節(jié)點(diǎn)成為感染節(jié)點(diǎn),無(wú)法為后續(xù)傳播過(guò)程提供持續(xù)快速的傳播速率;另一方面,傳播過(guò)程中存在“扇型”模式轉(zhuǎn)化為“鏈型”的情況,從而降低了傳播速率;再者,如果在鏈?zhǔn)浇Y(jié)構(gòu)中出現(xiàn)由于免疫等因素引起的傳播“中斷”,如圖1(a)中藍(lán)色的“中斷”點(diǎn),后續(xù)節(jié)點(diǎn)則無(wú)法接收到傳播信息,從而進(jìn)一步降低了傳播速率.

從低中心性節(jié)點(diǎn)初始的傳播過(guò)程則剛好相反,如圖1(b)所示,紅色傳播源均是度最小的節(jié)點(diǎn),在傳播開(kāi)始的短時(shí)間內(nèi),傳播模式主要呈現(xiàn)“鏈型”,所以傳播速率相對(duì)較慢.隨著傳播的繼續(xù),一方面?zhèn)鞑ツＪ綍?huì)逐漸由“鏈型”轉(zhuǎn)化為“扇型”,從而提升傳播速率;另一方面,即使在“鏈型”傳播過(guò)程中出現(xiàn)“中斷”,只要任意一條傳播鏈得以繼續(xù)傳播,傳播速率都會(huì)得到增強(qiáng),如圖1(b)中左側(cè)傳播路徑由于藍(lán)色“中斷”點(diǎn)的影響無(wú)法繼續(xù),但是右側(cè)傳播路徑保證了傳播過(guò)程的繼續(xù).由于兩種傳播模式的相互轉(zhuǎn)化,在不同初始感染條件下的傳播過(guò)程中,可能存在傳播規(guī)模交叉的現(xiàn)象,即兩種初始條件下的傳播過(guò)程在某時(shí)刻出現(xiàn)交叉點(diǎn).

3 仿真分析

3.1 傳播模型

為了消除傳播模型對(duì)結(jié)果的影響從而驗(yàn)證實(shí)驗(yàn)結(jié)果的普適性,本文使用兩種不同信息傳播模型:交互式電子郵件模型[12]和傳統(tǒng)SI模型[26].

交互式電子郵件模型可以被看作是基于Agent的模型[12],在該模型中,傳播過(guò)程需要借助用戶的行為激發(fā)才能進(jìn)行.具體來(lái)說(shuō),當(dāng)網(wǎng)絡(luò)中的一個(gè)用戶被感染后,該用戶會(huì)試圖感染周圍用戶(即向郵件列表中的朋友發(fā)送郵件),而鄰居用戶只有在查看并點(diǎn)擊該用戶發(fā)送的郵件之后才會(huì)被感染.因此,傳播過(guò)程由兩種用戶行為決定:用戶查看郵件的時(shí)間和用戶是否點(diǎn)擊可疑郵件.定義N表示網(wǎng)絡(luò)中用戶的總數(shù),i表示網(wǎng)絡(luò)中的用戶(i=1,2,3,···,N),Ti表示用戶i查看電子郵件的時(shí)間(即用戶i檢查電子郵件的時(shí)間間隔為Ti),Pi表示用戶i點(diǎn)擊可疑郵件的概率.通過(guò)分析可知用戶i查看電子郵件的時(shí)間Ti主要取決于用戶的個(gè)人習(xí)慣,而用戶i點(diǎn)擊可疑郵件的概率Pi主要取決于用戶對(duì)電子郵件病毒的了解程度以及系統(tǒng)自身的防護(hù)功能.由于網(wǎng)絡(luò)中用戶各自的行為相互獨(dú)立,所以該模型假設(shè)不同用戶間查看郵箱的時(shí)間間隔T與點(diǎn)擊可疑郵件概率P服從高斯分布,即對(duì)于某一具體用戶i,在不同時(shí)刻查看郵箱的頻率分布服從以Ti為參數(shù)的分布.依據(jù)文獻(xiàn)[12],本文用戶查看郵件的概率服從指數(shù)分布,其冪指數(shù)服從正態(tài)分布N(40,202),而用戶點(diǎn)擊可疑郵件的概率服從正態(tài)分布N(0.5,0.32).

SI模型,作為典型的傳染病模型之一[26],在研究許多傳播行為時(shí)都具有一定的適用性.在該模型中,只存在兩種狀態(tài)的個(gè)體,易染狀態(tài)(S:個(gè)體在被感染之前處于易染狀態(tài),處于該狀態(tài)的個(gè)體可能被鄰居個(gè)體感染)和感染狀態(tài)(I:個(gè)體感染了病毒將處于感染狀態(tài),并且處于該狀態(tài)的個(gè)體會(huì)嘗試感染其鄰居個(gè)體).在任意時(shí)刻,感染個(gè)體都會(huì)以概率β感染與之接觸的易染個(gè)體,直到傳播系統(tǒng)處于穩(wěn)定狀態(tài).在傳播網(wǎng)絡(luò)中表現(xiàn)為感染節(jié)點(diǎn)會(huì)以概率β嘗試感染與之直接鏈接的所有節(jié)點(diǎn).為避免傳播速率過(guò)快的問(wèn)題,本文設(shè)定易染節(jié)點(diǎn)被感染的概率β為0.2.

3.2 數(shù)據(jù)集

仿真實(shí)驗(yàn)中采用的信息傳播網(wǎng)絡(luò)(G1—G12)均是具有無(wú)標(biāo)度特性的網(wǎng)絡(luò),在無(wú)標(biāo)度網(wǎng)絡(luò)下的仿真結(jié)論能更好地付諸實(shí)際應(yīng)用. 人工網(wǎng)絡(luò)(G1—G7)中,G1—G3、G4—G7分別是基于BA模型[19]和GLP(generalized linear preference)算法[27]生成的,其中G7包含多個(gè)社區(qū)結(jié)構(gòu).五個(gè)標(biāo)準(zhǔn)網(wǎng)絡(luò)(G8—G12)包含安然郵件網(wǎng)絡(luò)(G8)[28]、大學(xué)郵件網(wǎng)絡(luò)(G9)[29]、自治層Internet網(wǎng)絡(luò)(G10)[30]以及科學(xué)協(xié)作網(wǎng)絡(luò)(G11,G12)[31,32].所有網(wǎng)絡(luò)的結(jié)構(gòu)特征信息如表1所列.

3.3 傳播實(shí)驗(yàn)

本次傳播實(shí)驗(yàn)基于不同中心性評(píng)估方法(度數(shù)、核數(shù)、介數(shù)、特征向量),重點(diǎn)分析了最大中心性節(jié)點(diǎn)以及最小中心性節(jié)點(diǎn)對(duì)傳播速率以及傳播規(guī)模的影響.其中,初始感染最大中心性節(jié)點(diǎn)的情景包括最大度、最大節(jié)點(diǎn)介數(shù)、最大核值以及最大特征向量中心性初始感染,而初始感染最小中心性節(jié)點(diǎn)的情景包括最小度、最小節(jié)點(diǎn)介數(shù)以及最小特征向量中心性初始感染.在不同的初始感染策略下,重復(fù)傳播100次,每次傳播過(guò)程的仿真迭代次數(shù)t為2000,保證最終傳播系統(tǒng)的穩(wěn)定性的同時(shí)降低實(shí)驗(yàn)結(jié)果數(shù)據(jù)的波動(dòng)性,最后統(tǒng)計(jì)100次運(yùn)行結(jié)果的均值作為實(shí)驗(yàn)結(jié)果.

表1 網(wǎng)絡(luò)結(jié)構(gòu)特征Table 1.Networks with di ff erent structures used in our experiments.

實(shí)驗(yàn)結(jié)果包含兩部分:傳播交叉圖和交播交叉圖是對(duì)傳播規(guī)模與傳播速率交叉現(xiàn)象的直觀刻畫(huà),包含傳播感染圖(即t時(shí)刻被感染節(jié)點(diǎn)總數(shù)I(t))和傳播增量圖(即t時(shí)刻新增感染數(shù)目?I(t)),I(t)和?I(t)滿足:?I(t)=I(t+1)?I(t).而交叉點(diǎn)非線性變化圖則進(jìn)一步展現(xiàn)傳播規(guī)模交叉的時(shí)間點(diǎn)與初始感染比例間的變化關(guān)系.

3.3.1 傳播交叉現(xiàn)象

利用表1中的網(wǎng)絡(luò)數(shù)據(jù),以電子郵件模型以及SI模型為傳播實(shí)驗(yàn)平臺(tái),在不同中心性評(píng)估方法下分別以5%,10%,20%的初始感染比例進(jìn)行仿真實(shí)驗(yàn).以BA無(wú)標(biāo)度網(wǎng)絡(luò)(G1)作為仿真結(jié)果示例,得到如圖2和圖3中的傳播交叉圖,其他數(shù)據(jù)集下的仿真證明見(jiàn)補(bǔ)充材料(online).

3.3.1.1 傳播感染圖

傳播感染圖是對(duì)傳播過(guò)程中傳播規(guī)模交叉的直觀呈現(xiàn),在不同傳播初始比例下的四個(gè)傳播圖分別代表四種中心性評(píng)估方法下的傳播實(shí)驗(yàn),圖中的黑色標(biāo)記點(diǎn)代表傳播規(guī)模發(fā)生交叉的時(shí)間點(diǎn).圖2展現(xiàn)了不同傳播模型下BA無(wú)標(biāo)度網(wǎng)絡(luò)(G1)中的仿真結(jié)果,其中圖2(a1)—(a3)來(lái)自電子郵件模型,圖2(b1)—(b3)來(lái)自SI模型,其他數(shù)據(jù)集下的仿真結(jié)果見(jiàn)補(bǔ)充材料的圖S1—圖S6(online).圖2中不同傳播模型下的仿真結(jié)果顯示出以下兩點(diǎn)現(xiàn)象:

1)本次實(shí)驗(yàn)設(shè)計(jì)的初始感染比例下,在無(wú)標(biāo)度網(wǎng)絡(luò)中,存在傳播規(guī)模交叉的現(xiàn)象,即初始感染最小中心性節(jié)點(diǎn)情況下的病毒傳播規(guī)模超越初始感染最大中心性節(jié)點(diǎn)的情況;

2)隨著初始感染比例的提升,交叉時(shí)間點(diǎn)呈現(xiàn)出不斷提前的趨勢(shì),傳播規(guī)模交叉的現(xiàn)象也愈加明顯.

3.3.1.2 傳播增量圖

進(jìn)一步分析傳播過(guò)程中傳播速率的變化,統(tǒng)計(jì)每次迭代過(guò)程中新增感染節(jié)點(diǎn)數(shù)目.傳播增量圖從傳播速率的角度對(duì)傳播過(guò)程進(jìn)行刻畫(huà).圖3與圖2中的傳播實(shí)驗(yàn)一一對(duì)應(yīng),圖3(a1)—(a3)和圖3(b1)—(b3)分別展示了BA無(wú)標(biāo)度網(wǎng)絡(luò)(G1)下基于電子郵件模型和SI模型的傳播增量圖,其他數(shù)據(jù)集下的傳播增量圖見(jiàn)補(bǔ)充材料的圖S7—圖S12(online).圖3中不同傳播模型下的傳播增量圖,顯示以下兩點(diǎn)特性.

1)在初始感染最大中心性節(jié)點(diǎn)的情況下,初期的傳播速率相對(duì)較快,但是初始感染比例的提升對(duì)這種傳播優(yōu)勢(shì)有著明顯的抑制作用.相對(duì)地,在初始感染最小中心性節(jié)點(diǎn)的情況下傳播速率幾乎不受負(fù)面影響.

在電子郵件病毒傳播模型下,隨著初始感染比例的提升,初始感染最小中心性節(jié)點(diǎn)的情況下,傳播速率保持相對(duì)穩(wěn)定.對(duì)比圖3(a1)—(a3)中的m1,m2和m3(即m1>m2>m3)可以發(fā)現(xiàn),初始感染最大中心性節(jié)點(diǎn)情況下的傳播過(guò)程受到明顯的影響:達(dá)到最大傳播速率前的傳播加速率逐漸減緩;傳播過(guò)程中的最大傳播速率逐漸降低;相同傳播時(shí)刻下的傳播速率逐漸減小.

圖2 (網(wǎng)刊彩色)基于(a1)—(a3)郵件病毒傳播模型和(b1)—(b3)SI模型,初始感染比例為5%,10%和20%時(shí)病毒在BA無(wú)標(biāo)度網(wǎng)絡(luò)(G1)中的傳播示意圖Fig.2.(color online)The illustration of dynamic propagation process in G1based on the(a1)–(a3)email propagation model and(b1)–(b3)SI model,in which 5%,10%and 20%nodes are selected as the initial infected nodes according to four di ff erent centralities(i.e.,degree,betweenness,k-core and eigenvector).

在SI模型中,通過(guò)對(duì)比圖3(b1)—(b3)中的n1,n2和n3(即n1>n2>n3)可以發(fā)現(xiàn),隨著初始感染比例的提升,初期傳播加速率在數(shù)值上呈現(xiàn)出升高的趨勢(shì),進(jìn)一步引起相同傳播時(shí)刻下的傳播速率逐漸減小.而在初始感染最小中心性節(jié)點(diǎn)的情況下,前期的傳播速率呈現(xiàn)增強(qiáng)的趨勢(shì).

圖3 (網(wǎng)刊彩色)基于(a1)—(a3)郵件病毒傳播模型和(b1)—(b3)SI模型,初始感染比例為5%,10%和20%時(shí)病毒在BA無(wú)標(biāo)度網(wǎng)絡(luò)(G1)中的傳播增量示意圖Fig.3.(color online)The illustration of dynamic changes of the incremental infected nodes in G1based on the(a1)—(a3)email propagation model and(b1)—(b3)SI model,in which 5%,10%and 20%nodes are selected as the initial infected nodes according to four di ff erent centralities(i.e.,degree,betweenness,k-core and eigenvector).

2)隨著初始感染比例的提升,初次傳播速率交叉點(diǎn)呈現(xiàn)出逐漸提前的趨勢(shì).

結(jié)合圖2中的傳播感染圖,得到以下與傳播速率和傳播規(guī)模交叉相關(guān)的傳播特性:

1)在無(wú)標(biāo)度網(wǎng)絡(luò)下,初始感染比例的不斷提高,會(huì)抑制初始感染最大中心性節(jié)點(diǎn)情況下的傳播速率,進(jìn)一步影響傳播規(guī)模的擴(kuò)散;相對(duì)地,初始感染最小中心性節(jié)點(diǎn)情況下的傳播速率幾乎不受負(fù)面影響;

2)兩種傳播過(guò)程受到的不同影響,促使其中的初次傳播速率交叉點(diǎn)呈現(xiàn)不斷提前的趨勢(shì),進(jìn)一步可能引起傳播規(guī)模交叉點(diǎn)的產(chǎn)生以及不斷提前;

3)不同結(jié)構(gòu)下的無(wú)標(biāo)度網(wǎng)絡(luò)中,傳播規(guī)模與傳播速率交叉點(diǎn)存在一定差異.

3.3.1.3 傳播模式分析

為了驗(yàn)證傳播過(guò)程中存在的兩種傳播模式(即“扇型”傳播和“鏈型”傳播),以BA無(wú)標(biāo)度網(wǎng)絡(luò)G1、人工網(wǎng)絡(luò)(G4)以及標(biāo)準(zhǔn)網(wǎng)絡(luò)(G9)為例,統(tǒng)計(jì)每次迭代過(guò)程中新增感染節(jié)點(diǎn)的平均度數(shù)?D(t).圖4給出了BA無(wú)標(biāo)度網(wǎng)絡(luò)G1下的統(tǒng)計(jì)結(jié)果,其他數(shù)據(jù)集下的傳播模式驗(yàn)證見(jiàn)補(bǔ)充材料的圖S13和圖S14(online).

圖4 (網(wǎng)刊彩色)基于(a1)—(a6)郵件病毒傳播模型和(b1)—(b6)SI傳播模型,初始感染比例為5%,10%和20%時(shí)病毒在BA無(wú)標(biāo)度網(wǎng)絡(luò)(G1)中的平均感染度示意圖Fig.4.(color online)The illustration of average degree of the incremental infected nodes in G1based on the(a1)–(a6)email propagation model and(b1)–(b6)SI model respectively,in which 5%,10%and 20%nodes are selected as the initial infected nodes according to four di ff erent centralities(i.e.,degree,betweenness,k-core and eigenvector).

圖4(a1)—(a6)和(b1)—(b6)分別來(lái)自電子郵件模型和SI模型,其中,圖4(a1)—(a3)和(b1)—(b3)、圖4(a4)—(a6)和(b4)—(b6)分別是初始感染最大、最小中心性節(jié)點(diǎn)情況下的統(tǒng)計(jì)結(jié)果,圖中〈ｋ〉值表示網(wǎng)絡(luò)G1的平均度.圖4揭示出無(wú)標(biāo)度網(wǎng)絡(luò)下,傳播過(guò)程中存在以下3點(diǎn)特性.

1)傳播過(guò)程中的平均感染度變化整體呈現(xiàn)下降趨勢(shì)直至傳播系統(tǒng)穩(wěn)定,但是即使在初始感染最小中心性節(jié)點(diǎn)的情況下,傳播行為趨向于優(yōu)先感染高鏈接度的節(jié)點(diǎn).

2)基于郵件病毒的傳播過(guò)程中,平均感染度具有兩處明顯的峰值變化.在相同初始感染比例與中心性評(píng)價(jià)指標(biāo)下,對(duì)比兩種傳播過(guò)程的平均感染度變化圖(如圖4(a1)和(a4),(a2)和(a5),(a3)和(a6))可以發(fā)現(xiàn),隨著初始感染比例的升高,初始感染最小中心性節(jié)點(diǎn)的情況下,處于兩個(gè)峰值間的平均感染度明顯高于網(wǎng)絡(luò)平均度〈ｋ〉,而初始感染最大中心性節(jié)點(diǎn)的情況下,整個(gè)傳播過(guò)程中的平均感染度明顯低于網(wǎng)絡(luò)平均度〈ｋ〉.與此同時(shí),對(duì)比圖4(a4)—(a6)可以發(fā)現(xiàn),初始感染最小中心性節(jié)點(diǎn)下的峰值間的平均感染度呈現(xiàn)增強(qiáng)的趨勢(shì).

在SI模型下,對(duì)比圖4(b1)和(b4),(b2)和(b5),(b3)和(b6)可以發(fā)現(xiàn),初始感染最小中心性節(jié)點(diǎn)情況下的峰值依然高于初始感染最大中心性節(jié)點(diǎn)的情況.這一現(xiàn)象為傳播速率以及傳播規(guī)模交叉現(xiàn)象的產(chǎn)生提供了必要條件.

圖5 (網(wǎng)刊彩色)電子郵件病毒傳播模型下的交叉點(diǎn)非線性變化圖Fig.5.(color online)The relationship between tcand the i(0)based on the email propagation model.

3)基于郵件病毒的傳播過(guò)程中,兩處明顯的峰值現(xiàn)象以及傳播過(guò)程中的波動(dòng)現(xiàn)象,說(shuō)明傳播過(guò)程中的確存在兩種傳播模式.峰值間的傳播過(guò)程對(duì)應(yīng)于傳播增量圖中?I(t)大于0的階段,在這一階段,平均感染度呈現(xiàn)不低的水平,說(shuō)明傳播過(guò)程表現(xiàn)為“扇型”模式.當(dāng)傳播增量圖中的?I(t)逐漸趨于0時(shí),平均感染度從第二峰值處呈現(xiàn)降低趨勢(shì),說(shuō)明傳播過(guò)程表現(xiàn)為從“扇型”模式向“鏈型”模式的逐漸轉(zhuǎn)化.

3.3.2 初始感染比例對(duì)交叉點(diǎn)的影響

3.3.1小節(jié)中的仿真實(shí)驗(yàn)揭示出,傳播規(guī)模以及傳播速率的交叉時(shí)間點(diǎn)會(huì)隨著初始感染比例的提升而提前.基于相同的傳播模型以及中心性評(píng)估方法,下面進(jìn)一步探究交叉時(shí)間點(diǎn)與初始感染比例間的關(guān)系.

實(shí)驗(yàn)中,初始感染比例i(0)從1%開(kāi)始,分為兩段:1%—5%,按照1%的比例增長(zhǎng);5%—50%,按照5%的比例增長(zhǎng).不同初始感染比例下的交叉時(shí)間點(diǎn)tc與3.3.1小節(jié)中的交叉時(shí)間點(diǎn)對(duì)應(yīng),tc滿足:Imax(t)

不同的中心性評(píng)估方法、傳播模型以及網(wǎng)絡(luò)結(jié)構(gòu)下,圖5和圖6的交叉點(diǎn)非線性變化圖揭示出以下3點(diǎn)共性:

1)初始感染比例較低時(shí),存在傳播規(guī)模交叉的現(xiàn)象,但是,由于傳播過(guò)程具有一定的隨機(jī)性,當(dāng)初始感染比例提升至10%—20%才能保證這一現(xiàn)象的穩(wěn)定性;

2)交叉時(shí)間點(diǎn)隨著初始感染比例的提升逐漸提前,最后趨于穩(wěn)定;

圖6 (網(wǎng)刊彩色)SI模型下的交叉點(diǎn)非線性變化圖Fig.6.(color online)The relationship between tcand the i(0)based on SI model.

3)傳播過(guò)程受到網(wǎng)絡(luò)結(jié)構(gòu)的影響,進(jìn)一步影響傳播規(guī)模交叉點(diǎn)的變化;在電子郵件病毒傳播模型下,G8網(wǎng)絡(luò)的交叉點(diǎn)表現(xiàn)出明顯的波動(dòng)性,在SI模型下,初始感染比例提升至30%才產(chǎn)生傳播規(guī)模交叉的現(xiàn)象.

4 討 論

在第3部分的實(shí)驗(yàn)中,利用不同的傳播模型以及無(wú)標(biāo)度網(wǎng)絡(luò)證實(shí)了傳播過(guò)程中傳播速率與傳播規(guī)模交叉現(xiàn)象的存在.其中,3.3.1小節(jié)給出了這一現(xiàn)象的直觀驗(yàn)證,3.3.2小節(jié)則通過(guò)進(jìn)一步的實(shí)驗(yàn)分析驗(yàn)證了初始感染比例與傳播交叉現(xiàn)象間的關(guān)系.下面主要針對(duì)這一現(xiàn)象做進(jìn)一步的分析.

基于微分方程的傳播模型存在均勻混合的假設(shè),在一定程度上高估了傳播過(guò)程中的傳播速率[33].本文關(guān)注兩種極端情況下傳播過(guò)程中的傳播規(guī)模交叉現(xiàn)象,因此,采用離散化的方法對(duì)該現(xiàn)象進(jìn)行分析.

定義如下:N,P(k)和〈ｋ〉分別表示網(wǎng)絡(luò)中的節(jié)點(diǎn)總數(shù),度為k的節(jié)點(diǎn)的比例和網(wǎng)絡(luò)的平均度;t時(shí)刻度為k的節(jié)點(diǎn)被感染的概率ik(t),t時(shí)刻感染節(jié)點(diǎn)的密度i(t);t時(shí)刻感染節(jié)點(diǎn)數(shù)I(t),t?1時(shí)刻到t時(shí)刻新增感染節(jié)點(diǎn)數(shù)?I(t),與第3部分中的統(tǒng)計(jì)量一致;平均傳播率,在SI模型下,該傳播率與節(jié)點(diǎn)被傳染的概率β一致,而在郵件病毒模型中,可將人類行為因素等效為異構(gòu)化的傳播率,在分析過(guò)程中使用平均的傳播率.兩種傳播過(guò)程下,各變量分別采用上標(biāo)進(jìn)行區(qū)分.

仿真實(shí)驗(yàn)中只考慮節(jié)點(diǎn)從健康轉(zhuǎn)變?yōu)楦腥緺顟B(tài),根據(jù)文獻(xiàn)[33,34],傳播過(guò)程中t?1到t時(shí)刻:

其中,Θ(t)表示度為k的節(jié)點(diǎn)的感染鄰居的密度.進(jìn)一步得到t時(shí)刻傳播速率與t時(shí)刻傳播規(guī)模的離散化表示:

根據(jù)(1)式可知,初始感染狀態(tài)i(0)對(duì)整個(gè)傳播過(guò)程影響重大.同時(shí),(3)式表明,當(dāng)傳播系統(tǒng)中感染節(jié)點(diǎn)比例較大的情況下,此時(shí)傳播規(guī)模交叉點(diǎn)的存在性取決于i(t),因此,需要對(duì)初始感染狀態(tài)i(0)以及i(t)進(jìn)行分析.

初始狀態(tài)下滿足Imax(0)=Imin(0),由于無(wú)標(biāo)度網(wǎng)絡(luò)的度分布可以用冪律分布(即P(k)～k?γ)近似刻畫(huà),因此,在初始狀態(tài)下,存在感染密度的差異這必然會(huì)引起后續(xù)傳播行為的不一致性.

當(dāng)系統(tǒng)中的感染節(jié)點(diǎn)比例足夠大(即感染節(jié)點(diǎn)中包含不同度值的節(jié)點(diǎn)),對(duì)(1)式從初始狀態(tài)ik(0)推導(dǎo):

其中,fa(t)和fb(t)是關(guān)于t的多項(xiàng)式,

(4)式第三步推導(dǎo)忽略了關(guān)于Θ(0)的高次項(xiàng),第一項(xiàng)ik(0)描述初始狀態(tài),第二項(xiàng)是對(duì)傳播增量密度的刻畫(huà).傳播系統(tǒng)達(dá)到穩(wěn)定狀態(tài)前,構(gòu)建輔助函數(shù)Φ(t,Θ(0))=Imin(t)? Imax(t)且Imax(0)=Imin(0),則

當(dāng)某時(shí)刻t出現(xiàn)傳播規(guī)模交叉的現(xiàn)象,根據(jù)Φ(t,Θ(0))>0進(jìn)一步得到

隨著傳播行為的進(jìn)行,存在

因此,為了避免傳播系統(tǒng)短時(shí)間內(nèi)達(dá)到穩(wěn)定狀態(tài),當(dāng)網(wǎng)絡(luò)規(guī)模趨于無(wú)限時(shí),必然存在時(shí)刻tc使得(6)式成立.對(duì)于有限的網(wǎng)絡(luò)規(guī)模,通過(guò)提升初始感染密度i(0)同樣可以滿足(6)式,從而促使兩種傳播過(guò)程下傳播規(guī)模交叉現(xiàn)象的產(chǎn)生,并且隨著初始感染密度的提升,傳播規(guī)模交叉點(diǎn)的產(chǎn)生時(shí)間會(huì)得到提前.這一現(xiàn)象表明,初始感染最大中心性節(jié)點(diǎn)情況下,初始感染比例的提升會(huì)對(duì)傳播速率產(chǎn)生相對(duì)較強(qiáng)的負(fù)面影響.

結(jié)合第3部分的仿真實(shí)驗(yàn),無(wú)標(biāo)度網(wǎng)絡(luò)下,由于網(wǎng)絡(luò)結(jié)構(gòu)的影響,傳播過(guò)程中存在兩種傳播模式(“鏈型”和“扇型”),即使在初始感染最小中心性節(jié)點(diǎn)的情況下,傳播行為仍趨向于優(yōu)先感染高鏈接度的節(jié)點(diǎn),從而為傳播規(guī)模交叉點(diǎn)的產(chǎn)生創(chuàng)造了有利條件.再者,隨著初始感染比例的提升,初始感染最大中心性節(jié)點(diǎn)的情況下,高鏈接度的節(jié)點(diǎn)在初始狀態(tài)被感染,后續(xù)傳播速率受到相對(duì)抑制,進(jìn)一步增大這一現(xiàn)象產(chǎn)生的可能性.

5 結(jié) 論

本文從網(wǎng)絡(luò)結(jié)構(gòu)異構(gòu)性的角度,基于不同的節(jié)點(diǎn)中心性,分析了結(jié)構(gòu)異構(gòu)性對(duì)傳播過(guò)程的影響.通過(guò)對(duì)傳播過(guò)程的分析,詳細(xì)闡述了傳播過(guò)程中存在的“鏈型”和“扇型”兩種傳播模式以及兩種傳播模式之間可能的轉(zhuǎn)換過(guò)程.以此為出發(fā)點(diǎn),利用仿真實(shí)驗(yàn)?zāi)M病毒傳播過(guò)程,實(shí)驗(yàn)結(jié)果表明,由于結(jié)構(gòu)異構(gòu)性的影響,傳播過(guò)程中的確存在兩種傳播模式(“鏈型”和“扇型”),并且在初始感染比例相對(duì)較高的情況下,這兩種傳播模式的相互轉(zhuǎn)換引起兩種極端傳播過(guò)程下的非線性傳播交叉現(xiàn)象.該現(xiàn)象揭示出初始感染比例的提高可以改變最小中心性節(jié)點(diǎn)的影響力,同時(shí)也提醒我們?cè)诮窈蟮难芯抗ぷ髦杏斜匾獙⑦@一因素納入考慮范圍.

[1]Zhang H F,Zhang J,Zhou C S,Small M,Wang B H 2010 New J.Phys.12 023015

[2]Saito K,Kimura M,Ohara K,Motoda H 2016 Inform.Sci.329 985

[3]Fu C,Min L,Yang J,Xu D L,Liu X Y,Han L S 2015 Proceedings of IEEE International Conference on Computer and Information Technology;Ubiquitous Computing and Communications;Dependable,Autonomic and Secure Computing;Pervasive Intelligence and Computing Liverpool,United Kingdom,October 26–28,2015 p1725

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

[5]Zhao J,Yu L,Li J R,Zhou P 2015 Chin.Phys.B 24 058904

[6]Song B,Jiang G P,Song Y R,Xia L L 2015 Chin.Phys.B 24 100101

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

[8]Freeman L C 1978 Soc.Networks 1 215

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

[10]Liu Y Y,Slotine J J,Barabási A L 2011 Nature 473 167

[11]Borgatti S P 2005 Soc.Networks 27 55

[12]Gao C,Liu J M,Zhong N 2011 Knowl.Inf.Syst.27 253

[13]Jiang J J,Wen S,Yu S,Xiang Y,Zhou W L 2016 IEEE Trans.Depend.Secure.pp 1

[14]Zhang X Z,Zhang Y B,Lü T Y,Yin Y 2014 Physica A 442 100

[15]Han X,Shen Z S,Wang W X,Di Z R 2015 Phys.Rev.Lett.114 028701

[16]Wang X F,Chen G R 2003 IEEE Circ.Syst.Mag.3 6

[17]Strogatz S H 2001 Nature 410 268

[18]Watts D J,Strogatz S H 1998 Nature 393 440

[19]Barabási A L,Albert R 1999 Science 286 509

[20]Wang X F,Li X,Chen G R 2012 Network Science:An Introduction(Beijing: Higher Education Press)pp270–275(in Chinese)[汪小帆,李翔,陳關(guān)榮2012 網(wǎng)絡(luò)科學(xué)導(dǎo)論(北京:高等教育出版社)第270—275頁(yè)]

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

[22]Barthélemy M,Barrat A,Pastor-Satorras R,Vespignani A 2004 Phys.Rev.Lett.92 178701

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

[24]Goh K I,Kahng B,Kim D 2001 Phys.Rev.Lett.87 278701

[25]Estrada E,Rodríguez-Velázquez J A 2006 Physica A 364 581

[26]Pastor-Satorras R,Vespignani A 2001 Phys.Rev.E 63 066117

[27]Bu T,Towsley D 2002 Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies New York,USA,June 23–27,2002 p638

[28]UCBerkeleyEnronEmailAnalysisProject,MIT http://bailando.sims.berkeley.edu/enron/enron.sql.gz[2017-4-18]

[29]http://deim.urv.cat/?aarenas/data/welcome.htm[2017-4-18]

[30]University of Oregon Route Views Archive Project,David Meyer http://routeviews.org/[2017-4-18]

[31]Stanford Network Analysis Project,Leskovec J https://snap.stanford.edu/data/ca-GrQc.html[2017-4-18]

[32]Stanford Network Analysis Project, Leskovec J https://snap.stanford.edu/data/ca-HepTh.html[2017-4-18]

[33]Zou C C,Towsley D,Gong W 2007 IEEE Trans.Depend.Secure.4 105

[34]Bogu?á M,Pastor-Satorras R,Vespignani A 2003 Statistical Mechanics of Complex Networks(Berlin:Springer-Verlag)p127

PACS:02.10.Ox,89.75.Fb,89.75.–kDOI:10.7498/aps.66.120201

Analysis of the effect of node centrality on diffusion mode in complex networks?

Su Zhen Gao Chao?Li Xiang-Hua

(College of Computer and Information Science,Southwest University,Chongqing 400715,China)

8 January 2017;revised manuscript

11 March 2017)

The centrality re fl ects the importance of a node in a complex network,which plays an important role in the propagation dynamics.Many researches in the fi eld of node ranking estimation have revealed the characteristics of higher centrality in the structural dynamics and propagation dynamics.However,there are few reports about the e ff ect of nodes with a relatively lower centrality on propagation process.In this paper,we focus on the e ff ect of heterogeneous structural characteristics on propagation dynamics.First,we select four centrality measurements(i.e.,degree,coreness,betweenness,and eigenvector)and initialize source nodes with the maximum and minimum centralities respectively.Then,based on the email propagation model and the SI model,the massive numbers of elaborate simulations are implemented in twelve scale-free networks.These networks include three networks generated by the Barabási-Albert model,four synthetic networks compiled by the GLP(generalized linear preference)algorithm,and fi ve benchmark networks.The simulation results contain two parts:one is the crossover phenomenon of two propagation processes,and the other is the correlation between the crossover point and the proportion of the initial source nodes.We present the crossover of two propagations by calculating the total infected nodes,the incremental infected nodes,and the average degree of the incremental infected nodes.The average degrees of the incremental infected nodes in both synthetic networks and benchmark networks show that there exist two kinds of di ff usion modes(i.e.,“fan-shaped” type and “single-strand”type).With the increase of the initial source nodes,the interaction between two modes results in the di ff erent dynamic changes of two propagations with respect to propagation speed,which may lead to the crossover of two propagations in terms of propagation scale in the propagation process.Speci fi cally,the increase of the initial source nodes would suppress the propagation process in which nodes with the maximum centralities are portrayed as propagating sources.However,such an e ff ect is not observed in the propagation process in which nodes with the minimum centralities are portrayed as propagating sources.Our further simulation indicates that the crossover points appear earlier as the proportion of the initial source nodes increases.And by employing the discrete-time method,we fi nd that such a phenomenon can be triggered exactly by increasing the initial source nodes.This work reveals that the in fl uence of the nodes with the minimum centralities should be taken into consideration because the initial infected nodes with a lower centrality will lead to a larger propagation scale if the initial proportion is high.

complex networks,heterogeneous structure,centrality measures,propagation speed

10.7498/aps.66.120201

?國(guó)家自然科學(xué)基金(批準(zhǔn)號(hào):61402379,61403315)、 中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金(批準(zhǔn)號(hào):XDJK2016A008,XDJK2016B029)和重慶市科技研發(fā)基地建設(shè)計(jì)劃(國(guó)際科技合作)項(xiàng)目(批注號(hào):cstc2015gjhz40002)資助的課題.

?通信作者.E-mail:cgao@swu.edu.cn

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

http://wulixb.iphy.ac.cn

*Project supported by the National Natural Science Foundation of China(Grant Nos.61402379,61403315),the Fundamental Research Funds for the Central Universities of Ministry of Education of China(Grant Nos.XDJK2016A008,XDJK2016B029),and the Chongqing Science and Technology R&D Base Construction(International Science and Technology Cooperation)Project,China(Grant No.cstc2015gjhz40002).

?Corresponding author.E-mail:cgao@swu.edu.cn