考慮邊聚類(lèi)與擴(kuò)散特性的信息傳播網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化算法?

楊李 宋玉蓉2)? 李因偉

1)(南京郵電大學(xué)自動(dòng)化學(xué)院,南京 210023)

2)(江蘇省物聯(lián)網(wǎng)智能機(jī)器人工程實(shí)驗(yàn)室,南京 210023)

3)(南京郵電大學(xué)計(jì)算機(jī)學(xué)院,南京 210023)

(2018年3月6日收到；2018年7月18日收到修改稿)

1 引 言

復(fù)雜網(wǎng)絡(luò)研究蓬勃發(fā)展二十年以來(lái),諸多研究成果表明網(wǎng)絡(luò)結(jié)構(gòu)可對(duì)網(wǎng)絡(luò)上的各種動(dòng)力學(xué)行為產(chǎn)生重要影響[1?3],如無(wú)標(biāo)度網(wǎng)絡(luò)比隨機(jī)網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)同步能力弱[4,5].在病毒傳播動(dòng)力學(xué)的研究中,發(fā)現(xiàn)無(wú)標(biāo)度網(wǎng)絡(luò)傳播閾值趨向于零[6],網(wǎng)絡(luò)的高聚類(lèi)特性對(duì)病毒傳播具有抑制作用[7].文獻(xiàn)[8]在比較病毒傳播與信息傳播差異時(shí)表明,小世界網(wǎng)絡(luò)具有最有效的信息傳播能力.文獻(xiàn)[9]通過(guò)邊重寫(xiě)優(yōu)化網(wǎng)絡(luò)的幾何連通性來(lái)提高網(wǎng)絡(luò)對(duì)抗隨機(jī)故障和蓄意攻擊的能力.文獻(xiàn)[10]在費(fèi)米函數(shù)的基礎(chǔ)上提出了一種改寫(xiě)網(wǎng)絡(luò)中的邊以促進(jìn)信息傳播的策略.Peng等[11]發(fā)現(xiàn)針對(duì)網(wǎng)絡(luò)魯棒性的優(yōu)化將降低網(wǎng)絡(luò)的小世界特性,因此提出了一個(gè)啟發(fā)式算法來(lái)獲得網(wǎng)絡(luò)魯棒性和小世界特性的平衡.文獻(xiàn)[5]研究發(fā)現(xiàn),在多層網(wǎng)絡(luò)的擴(kuò)散特性是層間相似性的函數(shù),故而通過(guò)降低層間相似性達(dá)到提高網(wǎng)絡(luò)擴(kuò)散性能的目的.信息傳播一直是傳播動(dòng)力學(xué)中的一個(gè)重要研究?jī)?nèi)容[12].Liu等[13]通過(guò)對(duì)經(jīng)典的信息傳播事件進(jìn)行研究,發(fā)現(xiàn)信息傳播的行為會(huì)受到傳播中的內(nèi)在和外在因素影響,通過(guò)結(jié)合這種內(nèi)在和外在的因素能夠更加有效地促進(jìn)信息的傳播.此外,網(wǎng)絡(luò)中的病毒傳播和信息傳播通常具有一定耦合,Zhan等[14]發(fā)現(xiàn)當(dāng)病毒在網(wǎng)絡(luò)中進(jìn)行傳播時(shí),由病毒傳播衍生出的相關(guān)信息同樣會(huì)在網(wǎng)絡(luò)中進(jìn)行擴(kuò)散,反而能夠有效地抑制病毒的傳播.在該研究的基礎(chǔ)上提出了一種信息驅(qū)動(dòng)自適應(yīng)模型[15],在該模型中個(gè)體能夠感知病毒傳播的信息,可以破壞與感染個(gè)體之間的連邊.顯然,如何優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),從而更好地利于有益信息傳播、抑制病毒傳播是研究者們關(guān)注的熱點(diǎn)[9?11,15?17].然而在現(xiàn)實(shí)生活中,優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)需要考慮的是優(yōu)化網(wǎng)絡(luò)的成本與效益.如何用一種對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行局部性調(diào)整的方法以有效地促進(jìn)信息的擴(kuò)散也是我們關(guān)注的重點(diǎn).

此外,網(wǎng)絡(luò)中重要節(jié)點(diǎn)對(duì)各種網(wǎng)絡(luò)的傳播影響巨大,如病毒營(yíng)銷(xiāo)正是利用了網(wǎng)絡(luò)中的一些有影響力的節(jié)點(diǎn)有效地進(jìn)行新產(chǎn)品推廣.在各種重要節(jié)點(diǎn)發(fā)現(xiàn)算法中[18],Malliaros等[19]利用K-truss分解算法能夠從網(wǎng)絡(luò)中提取出更精細(xì)、更密集的子圖,通過(guò)該子圖來(lái)識(shí)別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn),相比于K-shell[20]更精確而且時(shí)間復(fù)雜度也較低.然而,K-truss和K-shell分解都會(huì)受到網(wǎng)絡(luò)中局部聚類(lèi)結(jié)構(gòu)(即互相連接的假核結(jié)構(gòu))的影響[21],而這些假核結(jié)構(gòu)里的節(jié)點(diǎn)對(duì)信息或者病毒的擴(kuò)散能力通常較弱.文獻(xiàn)[22]在定義邊的權(quán)重時(shí),充分利用了邊的擴(kuò)散特性,極大地提高了識(shí)別最有影響力節(jié)點(diǎn)的準(zhǔn)確性和效率.因此,本文通過(guò)在K-truss分解原理的基礎(chǔ)上,同時(shí)考慮K-truss分解中邊的聚類(lèi)特性和擴(kuò)散特性,提出一種促進(jìn)信息傳播的網(wǎng)絡(luò)拓?fù)鋬?yōu)化算法.通過(guò)在真實(shí)的網(wǎng)絡(luò)中進(jìn)行仿真驗(yàn)證,結(jié)果表明使用提出的算法對(duì)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化后,可以加快信息在網(wǎng)絡(luò)中的傳播速度,使信息覆蓋的范圍更廣.此外,分析了該算法對(duì)網(wǎng)絡(luò)相關(guān)拓?fù)涮匦缘挠绊?

本文的內(nèi)容結(jié)構(gòu)安排如下:第2部分對(duì)邊的聚類(lèi)與擴(kuò)散特性進(jìn)行介紹；第3部分主要介紹算法的相關(guān)理論和算法詳細(xì)實(shí)現(xiàn)過(guò)程；第4部分主要進(jìn)行相關(guān)的實(shí)驗(yàn)仿真和分析；最后為結(jié)論.

2 邊的聚類(lèi)與擴(kuò)散特性

對(duì)于一個(gè)給定的無(wú)權(quán)無(wú)向網(wǎng)絡(luò) G=(V,E),V代表網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù),E是網(wǎng)絡(luò) G中的連邊數(shù).eij表示節(jié)點(diǎn) i和節(jié)點(diǎn) j之間的連邊,如果節(jié)點(diǎn) i與節(jié)點(diǎn)j有連邊,則eij等于1；否則eij等于0.節(jié)點(diǎn)i的度定義為ki.在K-truss分解中,邊eij的支持度[23]表示為

(1)式中,?ijk表示一個(gè)頂點(diǎn)分別為i,j,k的三角形,在圖1中,所有與節(jié)點(diǎn)i,j構(gòu)成三角形的另一個(gè)節(jié)點(diǎn)所構(gòu)成的節(jié)點(diǎn)集用Γ?ij表示,即圖1中由紅色虛線(xiàn)包圍的淺灰色節(jié)點(diǎn)所構(gòu)成的節(jié)點(diǎn)集,則有k∈Γ?ij；?G表示網(wǎng)絡(luò)G中由所有三角形構(gòu)成的集合；SD(eij)表示在網(wǎng)絡(luò)中由邊 eij構(gòu)成不同三角形的個(gè)數(shù).顯然,eij的支持度越高,該邊的聚類(lèi)特性越高,即邊的支持度是衡量一條邊聚類(lèi)特性的指標(biāo).

本文提出一種衡量邊擴(kuò)散特性的指標(biāo),并用DD(eij)表示邊eij的擴(kuò)散特性:

(2)式中,Γ(i,j)表示節(jié)點(diǎn) i和節(jié)點(diǎn) j的鄰居節(jié)點(diǎn)集,而Γ(i,j)i,j表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)集中除去節(jié)點(diǎn)i和節(jié)點(diǎn)j后的鄰居節(jié)點(diǎn)集.當(dāng)節(jié)點(diǎn)k∈Γ(i,j)i,j,并且節(jié)點(diǎn)k與節(jié)點(diǎn)i和節(jié)點(diǎn)j無(wú)法構(gòu)成一個(gè)三角形?ijk時(shí),θk=1；否則,θk=0.例如,在圖1中,節(jié)點(diǎn)i和節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)集Γ(i,j)i,j所包含的節(jié)點(diǎn)個(gè)數(shù)為4.而在鄰居節(jié)點(diǎn)中,被紅色虛線(xiàn)所標(biāo)記的深灰色節(jié)點(diǎn)無(wú)法與節(jié)點(diǎn)i和節(jié)點(diǎn)j構(gòu)成三角形.因此,當(dāng)信息經(jīng)過(guò)邊eij對(duì)外傳播時(shí),信息可以通過(guò)這些節(jié)點(diǎn)傳播到網(wǎng)絡(luò)中的其他節(jié)點(diǎn),而不是將信息又傳播回節(jié)點(diǎn)i或節(jié)點(diǎn)j從而構(gòu)成一個(gè)信息擴(kuò)散最小閉環(huán)路?ijk.

同時(shí),用集合?(i,j)表示圖1中被紅色虛線(xiàn)包圍的深灰色節(jié)點(diǎn)與節(jié)點(diǎn)i或節(jié)點(diǎn)j之間的連邊集合,其可以表示為

(3)式中,?i是節(jié)點(diǎn)i與其鄰居節(jié)點(diǎn)之間的連邊所構(gòu)成的邊集合；?j是節(jié)點(diǎn)j與其鄰居節(jié)點(diǎn)之間的連邊所構(gòu)成的邊集合；??ijk表示所有與邊eij構(gòu)成的三角形 ?ijk的邊 eik,eij和 ejk所構(gòu)成的邊集合.

通過(guò)(1)和(2)式,我們定義一個(gè)綜合邊的聚類(lèi)和擴(kuò)散特性的指標(biāo)SD?(eij)

(4)式中,α表示衡量邊的聚類(lèi)特性與擴(kuò)散特性之間的相對(duì)重要程度的比例因子,而比例因子α與綜合邊的聚類(lèi)和擴(kuò)散特性指標(biāo)SD?(eij)之間是線(xiàn)性比例關(guān)系,計(jì)算網(wǎng)絡(luò)中的所有邊的SD?(eij)指標(biāo)時(shí),α是相同的,其中α∈(0,1].并且,我們定義的綜合指標(biāo)SD?(eij)與文獻(xiàn)[22]中定義邊的權(quán)值的原理是相似的.文獻(xiàn)[22]指出,一條邊的重要性與邊的信息或病毒傳播過(guò)程有關(guān),為此在定義一條有向邊的邊權(quán)時(shí),使用源節(jié)點(diǎn)度值乘以目的節(jié)點(diǎn)擴(kuò)散能力來(lái)強(qiáng)調(diào)邊的非對(duì)稱(chēng)性.(4)式中SD(eij)與DD(eij)的相乘積形式也正是可以強(qiáng)調(diào):如果網(wǎng)絡(luò)中的邊的聚類(lèi)特性與擴(kuò)散特性不平衡,這些邊的綜合指標(biāo)SD?(eij)值就會(huì)相對(duì)較小.

通過(guò)從邊的拓?fù)涮卣魃戏治鲞叺木垲?lèi)特性與擴(kuò)散特性之間的關(guān)系,可以推出:

結(jié)合(5)和(6)式可以得到:

(7)式表示了邊的聚類(lèi)特性與邊的擴(kuò)散特性之間的關(guān)系,ki表示節(jié)點(diǎn)i的度,kj同理.通過(guò)(7)式可以發(fā)現(xiàn),邊的聚類(lèi)特性與邊的擴(kuò)散特性之間存在著互相制約的關(guān)系,即若保持一條邊的度不變,邊的一個(gè)特性提高,另一個(gè)特性就會(huì)相應(yīng)地下降.結(jié)合(4)和(7)式可以將SD?(eij)指標(biāo)重寫(xiě)為

分析(8)式可知,當(dāng)網(wǎng)絡(luò)中的一條邊eij的擴(kuò)散特性DD(eij)=0或DD(eij)=ki+kj?2時(shí),都有SD?(eij)=0.

3 信息傳播網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化算法

在信息傳播過(guò)程中,如果網(wǎng)絡(luò)中存在互相緊密連接的社團(tuán)結(jié)構(gòu),即假核結(jié)構(gòu),同時(shí)該假核結(jié)構(gòu)與網(wǎng)絡(luò)中其他部分之間的關(guān)聯(lián)較少,會(huì)促使信息在網(wǎng)絡(luò)局部?jī)?nèi)傳播,而不容易擴(kuò)散到網(wǎng)絡(luò)的其他部分.同時(shí),一些在網(wǎng)絡(luò)邊緣且不位于假核內(nèi)的邊的擴(kuò)散性相對(duì)較高,而這些邊的聚類(lèi)特性卻可能相對(duì)較低,也不利于信息的快速傳播.

因此,為了能夠有效地消除假核結(jié)構(gòu)對(duì)信息向外擴(kuò)散的影響,本文中通過(guò)(2)式定義了一種衡量邊的擴(kuò)散特性的指標(biāo),并結(jié)合(1)式表示的邊的聚類(lèi)特性,定義了一種綜合邊的聚類(lèi)特性與擴(kuò)散特性的指標(biāo)SD?(eij)來(lái)衡量在信息傳播過(guò)程中邊eij對(duì)信息向外快速擴(kuò)散的能力.根據(jù)(7)式發(fā)現(xiàn):網(wǎng)絡(luò)中的邊eij的聚類(lèi)特性SD(eij)與擴(kuò)散特性 DD(eij)之間存在著制約關(guān)系,即邊的聚類(lèi)特性與擴(kuò)散特性總和不會(huì)變化；兩者中有一個(gè)特性很高或者很低都會(huì)導(dǎo)致SD?(eij)指標(biāo)的值相對(duì)較?。欢鴮?duì)于一條邊的聚類(lèi)特性和擴(kuò)散特性?xún)烧卟痪饣蛘哌@兩個(gè)特性相比于網(wǎng)絡(luò)中的其他邊比較低時(shí),都會(huì)使得 SD?(eij)指標(biāo)的值很小.因此,通過(guò)SD?(eij)的能力強(qiáng)弱來(lái)甄選出這些需要優(yōu)化的邊,再結(jié)合邊eij的聚類(lèi)特性SD(eij)與擴(kuò)散特性DD(eij)的相對(duì)關(guān)系來(lái)判定是否需要優(yōu)化該邊以及提出相應(yīng)的優(yōu)化策略.詳細(xì)的算法步驟如下.

步驟1 參數(shù)初始化:給定待優(yōu)化的網(wǎng)絡(luò)拓?fù)銰、參數(shù)α和待優(yōu)化邊數(shù)m和優(yōu)化邊比例p,其中m=p?E,E為網(wǎng)絡(luò)總邊數(shù)；根據(jù)(1),(2)和(4)式分別計(jì)算網(wǎng)絡(luò)每條邊eij對(duì)應(yīng)的聚類(lèi)特性SD(eij)、擴(kuò)散特性DD(eij)和綜合邊的聚類(lèi)與擴(kuò)散能力SD?(eij).

步驟2 將網(wǎng)絡(luò)中的邊按照SD?(eij)值的大小進(jìn)行從小到大的進(jìn)行排序并加入備選邊集E′.

步驟3 刪邊:從E′中選擇SD?(eij)值最小的邊 eij,并將該邊從備選邊集 E′中剔除.比較該邊的支持度與擴(kuò)散性的關(guān)系,當(dāng)α?DD(eij)＜2?SD(eij)時(shí),將該邊在網(wǎng)絡(luò)G進(jìn)行刪除,否則在G中保留該邊.

步驟4 重復(fù)步驟3,直到從網(wǎng)絡(luò)中刪除掉m條邊,若滿(mǎn)足刪除條件的實(shí)際邊數(shù) m?＜m,則m=m?.

步驟5 從邊集E′中繼續(xù)選擇SD?(eij)值最小的邊eij,并將該邊從集合E′中剔除,判斷邊eij是否滿(mǎn)足條件α?DD(eij)＞2?SD(eij).若滿(mǎn)足,則執(zhí)行步驟6,否則繼續(xù)執(zhí)行步驟5.

步驟6 增邊:根據(jù)(3)式從集合 ?(i,j)中,選擇一條支持度最小的邊ejk,并連接節(jié)點(diǎn)i與節(jié)點(diǎn)k,使得增加的邊eik與邊eij,ejk構(gòu)成三角形,并更新網(wǎng)絡(luò)G.

步驟7 重復(fù)步驟5和步驟6,直到增加了m條邊.

4 仿真分析

4.1 數(shù)據(jù)源及信息傳播模型

在實(shí)驗(yàn)仿真中,采用的網(wǎng)絡(luò)為:1)Dophins網(wǎng)絡(luò)[24]；2)Polbooks網(wǎng)絡(luò)[25]；3)Email網(wǎng)絡(luò)[26]；4)Geom網(wǎng)絡(luò)[27].真實(shí)網(wǎng)絡(luò)的統(tǒng)計(jì)特征如表1,其中N 和E分別是網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)和連邊數(shù),?k?表示網(wǎng)絡(luò)的平均度,kmax表示最大度,?d?是網(wǎng)絡(luò)的平均最短路徑長(zhǎng)度,C是網(wǎng)絡(luò)的聚類(lèi)系數(shù),ΛN是網(wǎng)絡(luò)鄰接矩陣的最大特征值.

實(shí)驗(yàn)中采用經(jīng)典的獨(dú)立級(jí)聯(lián)模型[28]來(lái)描述網(wǎng)絡(luò)中的信息傳播過(guò)程.在隨機(jī)傳播模型中,信息的傳播被描述成一個(gè)隨機(jī)過(guò)程,節(jié)點(diǎn)的狀態(tài)在這個(gè)過(guò)程中變化.具體而言,每個(gè)節(jié)點(diǎn)有兩個(gè)可能的狀態(tài):激活態(tài)和非激活態(tài).在獨(dú)立級(jí)聯(lián)模型中,一個(gè)節(jié)點(diǎn)u一旦在第t步被激活,它在第t+1步去激活它的鄰居節(jié)點(diǎn)v,即每個(gè)被激活的節(jié)點(diǎn)只有一次機(jī)會(huì)去激活它的鄰居節(jié)點(diǎn).假設(shè)種子節(jié)點(diǎn)為S0,節(jié)點(diǎn)v被節(jié)點(diǎn)u激活的概率為p(u,v).則獨(dú)立級(jí)聯(lián)模型按照如下的擴(kuò)散規(guī)則進(jìn)行傳播:假設(shè)第t?1步處于激活狀態(tài)的節(jié)點(diǎn)集合為 St?1,第 t步處于激活狀態(tài)的St則在第t+1步時(shí),每個(gè)節(jié)點(diǎn)u以概率p(u,v)去嘗試激活它的鄰居節(jié)點(diǎn)v.如果成功,則節(jié)點(diǎn)v被激活,否則,在接下來(lái)的信息傳播過(guò)程中,節(jié)點(diǎn)u不能夠再激活其鄰居節(jié)點(diǎn).重復(fù)這一過(guò)程,直到網(wǎng)絡(luò)中沒(méi)有具有激活其他節(jié)點(diǎn)的活躍節(jié)點(diǎn).而對(duì)于激活概率p(u,v),廣泛使用1/degree(v)作為節(jié)點(diǎn)v被激活的概率[29].

表1 各個(gè)真實(shí)網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)涮卣鱐able 1.Network topology features of each real network.

4.2 信息傳播仿真分析

按所提算法對(duì)上述4個(gè)網(wǎng)絡(luò)進(jìn)行邊改寫(xiě),改寫(xiě)邊的比例p取0.2,即改寫(xiě)邊數(shù)m為0.2E.對(duì)比網(wǎng)絡(luò)所有的邊在優(yōu)化前后網(wǎng)絡(luò)中SD(eij),DD(eij)和SD?(eij)的變化,結(jié)果列于表2.從表2中可以看出,4個(gè)網(wǎng)絡(luò)在優(yōu)化后,邊的支持度即聚類(lèi)特性下降,擴(kuò)散特性值增加,綜合聚類(lèi)與擴(kuò)散特性也呈現(xiàn)下降.這表明,經(jīng)過(guò)提出的算法優(yōu)化后網(wǎng)絡(luò)整體的聚類(lèi)特性和擴(kuò)散特性的變化具有一定的規(guī)律性,且具有相反的變化趨勢(shì).同時(shí)由于網(wǎng)絡(luò)整體的綜合聚類(lèi)與擴(kuò)散特性也呈現(xiàn)出較明顯的下降趨勢(shì),表明網(wǎng)絡(luò)的聚類(lèi)特性相比擴(kuò)散特性其下降的幅度更大,算法對(duì)網(wǎng)絡(luò)聚類(lèi)特性的改變效果更明顯.

表2 優(yōu)化前后網(wǎng)絡(luò)支持度、擴(kuò)散度與綜合特性對(duì)比Table 2.Comparison of∑SD,∑DD and∑KSD comprehensive characteristics before and after optimization.

為了觀察提出的算法對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)在結(jié)構(gòu)優(yōu)化前后其信息傳播能力的變化,通過(guò)在網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化前后分別在網(wǎng)絡(luò)中利用信息傳播模型IC獨(dú)立級(jí)聯(lián)模型中進(jìn)行800次蒙特卡羅仿真,記錄下將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)進(jìn)行獨(dú)立傳播的信息覆蓋最大范圍.定義衡量網(wǎng)絡(luò)結(jié)構(gòu)變化前后的信息最大覆蓋范圍的函數(shù)Diff(v),

(9)式中,v表示網(wǎng)絡(luò)的節(jié)點(diǎn),其中v∈[0,N]；COV(v)表示節(jié)點(diǎn)v的信息傳播的最大范圍,即當(dāng)信息傳播結(jié)束時(shí),網(wǎng)絡(luò)中的所有激活節(jié)點(diǎn)(接收到信息的節(jié)點(diǎn))占網(wǎng)絡(luò)中總節(jié)點(diǎn)數(shù)的比例；COVfi(v)是網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化后的節(jié)點(diǎn)v的信息傳播的最大覆蓋范圍.顯然,若Diff(v)大于0,則表示以節(jié)點(diǎn)v作為信息傳播源,在優(yōu)化后的網(wǎng)絡(luò)中進(jìn)行傳播相比于優(yōu)化前的網(wǎng)絡(luò),其信息傳播范圍擴(kuò)大；否則,傳播范圍縮小.

圖2中,分別在不同的真實(shí)網(wǎng)絡(luò)Dophins,Polbooks,Email和Geom網(wǎng)絡(luò)中進(jìn)行信息傳播實(shí)驗(yàn),算法待優(yōu)化的邊數(shù)m設(shè)為網(wǎng)絡(luò)邊數(shù)E的10%.對(duì)比分析在網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化前后,以網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)作為初始傳播源觀測(cè)其傳播范圍差.從圖2中可以看到:在所有的真實(shí)網(wǎng)絡(luò)中,在橫坐標(biāo)線(xiàn)上的節(jié)點(diǎn)數(shù)量比坐標(biāo)線(xiàn)下的節(jié)點(diǎn)數(shù)更多,即表示優(yōu)化后的網(wǎng)絡(luò)整體上更有利于增大信息傳播的覆蓋范圍.在Dophins網(wǎng)絡(luò)中,優(yōu)化后的網(wǎng)絡(luò)結(jié)構(gòu)中提高信息傳播范圍的節(jié)點(diǎn)所占的比例為69.4%；Polboks網(wǎng)絡(luò)中提高信息傳播范圍的節(jié)點(diǎn)所占的比例為79.1%；在Email網(wǎng)絡(luò)中,提高信息傳播范圍的節(jié)點(diǎn)所占的比例為72.4%；而在Geom網(wǎng)絡(luò)中,該節(jié)點(diǎn)所占的比例為76.7%,即通過(guò)算法優(yōu)化后的網(wǎng)絡(luò)有利于促進(jìn)信息傳播的節(jié)點(diǎn)數(shù)總體上不低于網(wǎng)絡(luò)所有節(jié)點(diǎn)的70%.

圖2 網(wǎng)絡(luò)優(yōu)化前后每個(gè)節(jié)點(diǎn)作為傳播源的傳播范圍差Fig.2.The spread range of each node as a source of propagation before and after network optimization.

為了觀察經(jīng)過(guò)算法優(yōu)化后網(wǎng)絡(luò)的平均信息傳播范圍和平均傳播速度的變化,對(duì)結(jié)構(gòu)優(yōu)化前后的4個(gè)真實(shí)網(wǎng)絡(luò)進(jìn)行傳播能力的仿真實(shí)驗(yàn).實(shí)驗(yàn)中,將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)單獨(dú)作為信息傳播源進(jìn)行傳播,記錄下節(jié)點(diǎn)每個(gè)傳播時(shí)刻t的信息傳播情況,并將某一時(shí)刻t網(wǎng)絡(luò)中所有節(jié)點(diǎn)傳播能力的平均值作為t時(shí)刻網(wǎng)絡(luò)整體對(duì)信息的擴(kuò)散能力.在圖3中,通過(guò)在4個(gè)真實(shí)網(wǎng)絡(luò)中對(duì)比分析網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化前后的傳播情況可以發(fā)現(xiàn),整體上經(jīng)過(guò)提出的算法優(yōu)化后的網(wǎng)絡(luò)對(duì)于各個(gè)傳播時(shí)刻t而言,其傳播的范圍都較為明顯地?cái)U(kuò)大了.信息傳播速度刻畫(huà)的是節(jié)點(diǎn)作為傳播源進(jìn)行傳播時(shí),網(wǎng)絡(luò)中被激活節(jié)點(diǎn)的變化率,即圖3中的曲線(xiàn)斜率.而在4個(gè)真實(shí)網(wǎng)絡(luò)中傳播到達(dá)穩(wěn)態(tài)之前優(yōu)化網(wǎng)絡(luò)的時(shí)間演化曲線(xiàn)的斜率要高于原始網(wǎng)絡(luò),表明優(yōu)化后的網(wǎng)絡(luò)信息擴(kuò)散速度要快于原網(wǎng)絡(luò).因此,經(jīng)過(guò)算法優(yōu)化后的網(wǎng)絡(luò)對(duì)信息的傳播能力在傳播范圍和傳播速度上都得到了相應(yīng)的提高.

圖3 網(wǎng)絡(luò)優(yōu)化前后的信息傳播時(shí)間演化曲線(xiàn)Fig.3.Evolution curve of information propagation time before and after network optimization.

4.3 網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化前后網(wǎng)絡(luò)統(tǒng)計(jì)特性對(duì)比分析

為了更明顯地觀察算法對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響,對(duì)網(wǎng)絡(luò)中20%的邊進(jìn)行改寫(xiě).網(wǎng)絡(luò)結(jié)構(gòu)在優(yōu)化前后的變化情況如表3所列,從表3中可見(jiàn),網(wǎng)絡(luò)最大度變化不大,網(wǎng)絡(luò)的最大特征根在Dophins,Polbooks和Geom網(wǎng)絡(luò)中相應(yīng)地減小了,而在Email網(wǎng)絡(luò)中基本保持不變.網(wǎng)絡(luò)的平均聚類(lèi)系數(shù)、平均路徑長(zhǎng)度都有下降.從信息傳播過(guò)程的角度來(lái)看,越短的平均路徑長(zhǎng)度也會(huì)使得信息更快速和更高效地傳播到網(wǎng)絡(luò)的其他部分.而提出的算法能夠較為明顯地改變網(wǎng)絡(luò)的平均路徑長(zhǎng)度,即從網(wǎng)絡(luò)拓?fù)涮卣鞯慕嵌闰?yàn)證了算法對(duì)促進(jìn)信息傳播的有效性.

表3 網(wǎng)絡(luò)優(yōu)化前后網(wǎng)絡(luò)統(tǒng)計(jì)特征對(duì)比Table 3.Comparison of network statistical characteristics before and after network optimization.

圖4 網(wǎng)絡(luò)優(yōu)化前后,網(wǎng)絡(luò)度分布變化比較Fig.4.Comparison of network degree distribution before and after network optimization.

圖5 網(wǎng)絡(luò)聚類(lèi)系數(shù)與改寫(xiě)邊比例p的關(guān)系Fig.5.The relationship between the network clustering cofiicient and p.

進(jìn)一步對(duì)網(wǎng)絡(luò)度分布變化進(jìn)行分析,實(shí)驗(yàn)結(jié)果如圖4所示.在圖4中,可以發(fā)現(xiàn)在網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化之后,節(jié)點(diǎn)的度分布的特性沒(méi)有太大變化.從圖4(a)、圖4(c)和圖4(d)可以看出,網(wǎng)絡(luò)中葉子節(jié)點(diǎn),即k=1的節(jié)點(diǎn)比例均有下降.即算法能夠較為明顯地改變網(wǎng)絡(luò)中葉子節(jié)點(diǎn)數(shù),使得網(wǎng)絡(luò)中葉子節(jié)點(diǎn)減小,網(wǎng)絡(luò)中其他度的節(jié)點(diǎn)數(shù)量增加.進(jìn)一步分析網(wǎng)絡(luò)聚類(lèi)特性的變化,從圖5可以看出,在進(jìn)行邊改寫(xiě)后,網(wǎng)絡(luò)聚類(lèi)系數(shù)均下降,在改寫(xiě)邊的比例p小于0.2時(shí),聚類(lèi)系數(shù)與p呈反比關(guān)系.當(dāng) p大于0.2時(shí),聚類(lèi)系數(shù)不再有明顯下降.

通過(guò)研究算法對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響可以發(fā)現(xiàn),經(jīng)過(guò)算法優(yōu)化后的網(wǎng)絡(luò)拓?fù)涮卣鳟a(chǎn)生了一定的變化,例如平均路徑長(zhǎng)度、聚類(lèi)系數(shù)和度分布等.然而對(duì)于不同網(wǎng)絡(luò)優(yōu)化的效果也不同,這與網(wǎng)絡(luò)本身存在一定關(guān)系.因?yàn)樘岢龅乃惴▌h邊的思路是破壞網(wǎng)絡(luò)中擴(kuò)散性很低而聚類(lèi)能力很高的邊,在假核(互相緊密連接的局部拓?fù)浣Y(jié)構(gòu))中的邊大多數(shù)是擴(kuò)散性很低而聚類(lèi)能力很高的邊.因此,當(dāng)刪除這類(lèi)邊時(shí),會(huì)瓦解網(wǎng)絡(luò)中的假核,從而破壞了網(wǎng)絡(luò)中很多的三角形結(jié)構(gòu),使得信息能夠從假核內(nèi)有效地傳播到網(wǎng)絡(luò)的其他部分.而對(duì)于Email網(wǎng)絡(luò),其網(wǎng)絡(luò)的聚類(lèi)系數(shù)較低,因此算法的整體操作性相對(duì)較低,即能夠破壞的假核結(jié)構(gòu)較少,對(duì)網(wǎng)絡(luò)結(jié)構(gòu)上的改變不夠顯著.

4.4 相關(guān)參數(shù)對(duì)信息傳播的影響分析

在(4)式中α主要是用來(lái)調(diào)節(jié)邊的擴(kuò)散特性與聚類(lèi)特性之間重要程度的比例因子,其中α∈(0,1].而在算法中會(huì)利用邊的擴(kuò)散特性與聚類(lèi)特性之間的比例關(guān)系來(lái)判斷是否需要優(yōu)化一條邊.因此,我們研究了比例因子α對(duì)信息傳播的影響,實(shí)驗(yàn)結(jié)果如圖6所示.在圖6中,縱坐標(biāo)中的穩(wěn)態(tài)時(shí)的信息傳播能力,是指當(dāng)信息傳播結(jié)束時(shí)網(wǎng)絡(luò)中被激活的節(jié)點(diǎn)占所有節(jié)點(diǎn)的比例.在Dophins網(wǎng)絡(luò)中,α=0.5時(shí)信息傳播效果最好；在Polbooks網(wǎng)絡(luò)中,α在0.4到0.6之間時(shí),傳播效果相對(duì)更好；對(duì)于Email網(wǎng)絡(luò),最優(yōu)的α主要分布在α=0.2和α∈[0.45,0.55]；Geom網(wǎng)絡(luò)中,最優(yōu)的α分布在α∈[0.4,0.5]之間.因此,對(duì)于不同的網(wǎng)絡(luò)最優(yōu)的比例因子有一定的不同,然而最優(yōu)的比例因子主要集中在0.4到0.6之間.為了使得算法對(duì)不同的網(wǎng)絡(luò)具有普適性,在算法中采用的比例因子α=0.5.

圖6 比例因子α對(duì)信息傳播能力的影響Fig.6.The influence of proportional factor α on information propagation.

圖7 邊優(yōu)化比例p對(duì)信息傳播的影響Fig.7.The influence of edge optimization proportion p on information propagation.

此外,信息傳播的效果與網(wǎng)絡(luò)中待優(yōu)化的邊數(shù)也具有一定的關(guān)系.因此,通過(guò)優(yōu)化不同的邊的比例 p來(lái)觀察其對(duì)信息傳播的影響,實(shí)驗(yàn)結(jié)果如圖7所示.在圖7中,橫坐標(biāo)優(yōu)化比例p的范圍為p∈(0,0.25).通過(guò)實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn),對(duì)于不同的真實(shí)網(wǎng)絡(luò)而言,隨著優(yōu)化邊比例的提高,即網(wǎng)絡(luò)中被改寫(xiě)的邊結(jié)構(gòu)越多,網(wǎng)絡(luò)整體對(duì)信息的傳播能力也在逐漸提高.對(duì)于Dophins和Polbooks網(wǎng)絡(luò),其網(wǎng)絡(luò)中的邊數(shù)較少,能夠滿(mǎn)足優(yōu)化條件的邊也相應(yīng)比較少,因此在優(yōu)化比例p到達(dá)0.2時(shí),基本達(dá)到實(shí)際可優(yōu)化的邊比例,繼續(xù)提高優(yōu)化比例后促進(jìn)信息傳播的效果提升并不大.對(duì)于Email和Geom網(wǎng)絡(luò),隨著優(yōu)化比例p的提高,促進(jìn)信息傳播的效果也越來(lái)越好.特別是對(duì)于Geom網(wǎng)絡(luò),促進(jìn)信息傳播效果與優(yōu)化比例p之間呈現(xiàn)出接近于線(xiàn)性的比例關(guān)系.

5 結(jié) 論

本文通過(guò)保證節(jié)點(diǎn)的總數(shù)和邊的總數(shù)不變的前提下,提出了一種基于擴(kuò)散K-truss分解的信息傳播網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化算法.該算法分析了邊的聚類(lèi)特性與擴(kuò)散特性之間的相互關(guān)系,并根據(jù)邊的聚類(lèi)特性與擴(kuò)散特性之間的差異性來(lái)優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu),通過(guò)在4個(gè)真實(shí)的網(wǎng)絡(luò)中進(jìn)行信息傳播的蒙特卡羅仿真發(fā)現(xiàn),網(wǎng)絡(luò)中的所有節(jié)點(diǎn)中,優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)后提高信息傳播范圍的節(jié)點(diǎn)占所有節(jié)點(diǎn)的比例至少為70%,證明了經(jīng)所提算法優(yōu)化后的網(wǎng)絡(luò)使得信息傳播覆蓋范圍更大.網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化后,網(wǎng)絡(luò)的度分布沒(méi)有太大變化,但網(wǎng)絡(luò)的聚類(lèi)特性下降較為明顯,同時(shí)網(wǎng)絡(luò)平均路徑長(zhǎng)度也有所下降,這些網(wǎng)絡(luò)特征的變化使得網(wǎng)絡(luò)中的信息擴(kuò)散范圍擴(kuò)大.在現(xiàn)實(shí)生活中,優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)需要考慮優(yōu)化網(wǎng)絡(luò)的成本與帶來(lái)的效益.而提出的優(yōu)化算法主要是在需要優(yōu)化邊的局部范圍內(nèi)進(jìn)行調(diào)整,而非全局性調(diào)整.這可以大幅的降低優(yōu)化成本,提高優(yōu)化效益.因此,可以將優(yōu)化算法應(yīng)用在優(yōu)化成本低、網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)可變的網(wǎng)絡(luò)中,例如自適應(yīng)Ad hoc移動(dòng)網(wǎng)絡(luò),通過(guò)提出的算法進(jìn)行分析和動(dòng)態(tài)調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)有利于促進(jìn)節(jié)點(diǎn)與節(jié)點(diǎn)之間更有效地通信、防止信道過(guò)載和提高信息的傳輸范圍.