劉樹新季新生②劉彩霞湯紅波鞏小銳

?

局部拓撲信息耦合促進網(wǎng)絡(luò)演化

劉樹新*①季新生①②劉彩霞①湯紅波①鞏小銳①

①(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 鄭州 450002)②(移動互聯(lián)網(wǎng)安全技術(shù)國家工程實驗室 北京 100876)

為了研究局部拓撲信息耦合對網(wǎng)絡(luò)演化的促進作用，該文提出一種局部拓撲加權(quán)方法，用于表征節(jié)點間聯(lián)系的緊密性及拓撲信息的耦合程度，并從演化模型的宏觀統(tǒng)計和實際網(wǎng)絡(luò)數(shù)據(jù)測試兩方面驗證了局部拓撲信息耦合促進網(wǎng)絡(luò)演化的有效性。首先將該加權(quán)方法應(yīng)用于BA模型，提出TwBA模型及局域世界模型TwLW。仿真實驗表明，TwBA的度分布隨連邊數(shù)目的增多，迅速從指數(shù)分布轉(zhuǎn)變?yōu)閮缏煞植?，驗證了現(xiàn)實網(wǎng)絡(luò)加速增長產(chǎn)生冪律分布的現(xiàn)象，并基于此提出一種加速演化的TwBA模型，其在不同的加速率下呈現(xiàn)出冪律分布；而TwLW則展現(xiàn)了從廣延指數(shù)分布到冪律分布變化的形式。然后將加權(quán)方法拓展到鏈路預(yù)測方法，提出3個加權(quán)相似性指標。實際網(wǎng)絡(luò)數(shù)據(jù)測試表明，該方法能夠大幅度地提高基本算法的預(yù)測精度，部分甚至高于全局性指標。

復(fù)雜網(wǎng)絡(luò)；局部拓撲；演化模型；鏈路預(yù)測；信息耦合

1 引言

近年來，復(fù)雜網(wǎng)絡(luò)領(lǐng)域的研究蓬勃發(fā)展，越來越多的現(xiàn)實網(wǎng)絡(luò)已經(jīng)成為復(fù)雜網(wǎng)絡(luò)的研究對象，包括社交媒體網(wǎng)絡(luò)[1]、互聯(lián)網(wǎng)[2]、電力網(wǎng)絡(luò)[3]、蛋白質(zhì)網(wǎng)絡(luò)[4]、交通運輸網(wǎng)絡(luò)[5]等多種復(fù)雜性系統(tǒng)。網(wǎng)絡(luò)演化機制作為網(wǎng)絡(luò)科學(xué)的根本性問題，一直是統(tǒng)計領(lǐng)域的研究熱點。尤其是在小世界[6]、無標度[7]等特性的發(fā)現(xiàn)之后，極大地豐富了人們對于現(xiàn)實網(wǎng)絡(luò)的認識，也刺激了各領(lǐng)域研究復(fù)雜網(wǎng)絡(luò)演化機制的熱忱[8]。

經(jīng)典的BA模型揭示了網(wǎng)絡(luò)的無標度特性，認為網(wǎng)絡(luò)增長和偏好連接是網(wǎng)絡(luò)演化的根本動力[7]。在BA模型的基礎(chǔ)上，許多學(xué)者在連接概率和內(nèi)部連邊等上做了改進[9,10]?？紤]到現(xiàn)實網(wǎng)絡(luò)中個體選擇的局限性，文獻[11]提出了局域世界演化模型(LW)，模型通過在隨機選擇的局域世界中進行度優(yōu)先選擇，并呈現(xiàn)出指數(shù)分布和冪律分布之間的度分布形式。由于許多真實網(wǎng)絡(luò)的連接存在權(quán)值，文獻[12]提出了經(jīng)典的賦權(quán)演化模型BBV模型，該模型采用強度優(yōu)先連接，新連接添加時會為當前點強度增加一個，產(chǎn)生了標準的無標度網(wǎng)絡(luò)?；贐BV模型，許多學(xué)者進一步提出了不同的含權(quán)演化模型，但在權(quán)值的賦予上多是在無權(quán)網(wǎng)絡(luò)模型上進行簡單的增添，缺乏對局部拓撲信息的耦合，且其取值并不能反映當前連接周圍的拓撲結(jié)構(gòu)。

現(xiàn)階段，網(wǎng)絡(luò)演化模型的研究均基于宏觀統(tǒng)計(度分布等宏觀參數(shù))，并沒有在實際網(wǎng)絡(luò)中進行數(shù)據(jù)驗證。因此，相關(guān)學(xué)者認為鏈路預(yù)測可用于衡量網(wǎng)絡(luò)演化模型[16]，驗證物理演化機制在實際網(wǎng)絡(luò)中的有效性。并基于拓撲演化機制，提出了大量的鏈路預(yù)測方法，包括共同鄰居[17](Common Neighbors, CN), Salton[18]，資源分配[19](Resource Allocation, RA), LHN-II[20]和Katz[21]等相似性指標，一定程度上豐富了人們對真實網(wǎng)絡(luò)中網(wǎng)絡(luò)演化機制的認識。研究表明許多實際網(wǎng)絡(luò)的度分布介于冪律分布和指數(shù)分布之間[22]，呈現(xiàn)出近冪律的分布形式如去頭的冪律分布、廣延指數(shù)分布等[23]，且增長過程中表現(xiàn)出了加速增長的趨勢(邊的增長速度遠大于點的增加速度)[24]。具體實際網(wǎng)絡(luò)中如：政治論壇博客網(wǎng)絡(luò)[25]為近冪律分布；線蟲神經(jīng)網(wǎng)絡(luò)[6]則存在單峰[26]，呈現(xiàn)單側(cè)冪律分布；引文網(wǎng)絡(luò)[27]則為近指數(shù)分布；而路由器級互聯(lián)網(wǎng)[28]則表現(xiàn)為接近廣延指數(shù)分布的近冪律分布。度優(yōu)先選擇被認為是冪律分布產(chǎn)生的重要機制，但越來越多實證研究發(fā)現(xiàn)局部范圍內(nèi)的拓撲信息對新連接的建立也起著重要作用[29,30]。局部拓撲信息耦合程度能夠很大程度上影響網(wǎng)絡(luò)節(jié)點的偏好連接，現(xiàn)實網(wǎng)絡(luò)如人際關(guān)系網(wǎng)絡(luò)中，個體之間新連接的建立往往傾向于個體及其周圍社會關(guān)系的統(tǒng)合考量，新連接則可以理解為兩個節(jié)點周圍社會關(guān)系的偏好選擇；同樣，在引文網(wǎng)絡(luò)中，新引用的產(chǎn)生更多是基于文獻相互引用構(gòu)成的影響力(局部拓撲關(guān)系構(gòu)成的綜合吸引力)。

基于上述討論，本文提出了一種局部拓撲信息加權(quán)方法，量化節(jié)點間聯(lián)系的緊密性和拓撲信息的耦合程度，進而使節(jié)點可以耦合更多的局部拓撲信息。將該方法應(yīng)用于經(jīng)典BA模型，基于拓撲加權(quán)后的節(jié)點強度進行優(yōu)先選擇，提出了基于局部拓撲加權(quán)的TwBA和局域世界模型TwLW。度分布分析表明，不同于BA模型，TwBA呈現(xiàn)出從指數(shù)分布到冪律分布變化的形式，并隨著連邊數(shù)的增長，迅速轉(zhuǎn)變?yōu)閮缏煞植?，這一定程度上說明了現(xiàn)實網(wǎng)絡(luò)連邊加速增長后產(chǎn)生冪律分布的現(xiàn)象；基于TwBA的度分布特點，進一步提出加速網(wǎng)絡(luò)模型A-TwBA，度分布統(tǒng)計顯示模型在網(wǎng)絡(luò)加速演化后呈現(xiàn)出冪律分布，部分同時呈現(xiàn)單峰和冪律分布；而TwLW模型則呈現(xiàn)了廣延指數(shù)分布到冪律分布變化的形式。為了在實際網(wǎng)絡(luò)中進一步驗證局部拓撲加權(quán)促進網(wǎng)絡(luò)演化這一機制的有效性，將拓撲加權(quán)應(yīng)用于基本的鏈路預(yù)測方法CN, Jaccard和RA。多個實際網(wǎng)絡(luò)數(shù)據(jù)測試結(jié)果表明，局部拓撲加權(quán)能夠大幅度提高相似性指標的預(yù)測精度，部分甚至高于全局性指標。從宏觀統(tǒng)計和實際網(wǎng)絡(luò)數(shù)據(jù)兩個方面驗證了局部拓撲信息耦合促進網(wǎng)絡(luò)演化這一機制的合理性。

2 局部拓撲信息加權(quán)方法(TW)

現(xiàn)實網(wǎng)絡(luò)中，權(quán)重一般是根據(jù)統(tǒng)計結(jié)果進行賦值，比如：節(jié)點間交互的頻率、作用強度[31]，但并沒有進一步反映連接周圍的拓撲結(jié)構(gòu)關(guān)系。越來越多實際網(wǎng)絡(luò)數(shù)據(jù)表明，網(wǎng)絡(luò)局部范圍內(nèi)的積聚程度對連邊的可能性起著重要作用[32,33]。節(jié)點周圍拓撲集聚程度越高，對其他節(jié)點的吸引力越大，它們之間便更傾向于建立連接。對于網(wǎng)絡(luò)中直接連接的兩個節(jié)點和，其間接連接可以為當前邊提供隱含的拓撲信息和潛在內(nèi)部聯(lián)系，增加了節(jié)點間的相關(guān)聯(lián)系和信息耦合，一定程度上反映了節(jié)點間聯(lián)系的緊密程度。圖1示意了不同情形下的拓撲影響，可分為兩種對比情況：一種情形為兩個端點擁有相同的連邊數(shù)目，但間接連接數(shù)目不同如：圖1(a)和圖1(b)，由于圖1(b)中含有間接連接多于圖1(a)，所以認為圖1(b)中節(jié)點和間的局部拓撲緊密性更高，故連邊權(quán)重大于圖1(a)；另一種情形為間接連接數(shù)目相同，但總連邊數(shù)目不同：圖1(b)和圖1(c)，由于圖1(c)中連邊數(shù)目小于圖1(b)，雖然間接連接數(shù)目相同，局部拓撲緊密性也與其占比例相關(guān)，圖1(c)中節(jié)點和間拓撲關(guān)聯(lián)更緊密，故權(quán)重相對更大。

圖1 不同局部拓撲情形對比圖

基于上述分析，假定每條邊可以擁有或支配的資源為1。從間接連接對節(jié)點間緊密性的影響上分析，若兩節(jié)點所有連接的數(shù)目為，間接聯(lián)系數(shù)目為，間接聯(lián)系對當前連接的影響，可以量化表示為，而當前直接連邊自身在所有連接中的比重為，如圖1(c)中的量化結(jié)果分別為4/7和1/7。總之，對于網(wǎng)絡(luò)中兩個節(jié)點和，其局部拓撲信息的影響總體加權(quán)表示為

3 基于局部拓撲信息加權(quán)的網(wǎng)絡(luò)演化模型

3.1 基于局部拓撲信息加權(quán)的網(wǎng)絡(luò)演化模型

基于局部拓撲加權(quán)方法(TW)，對BA模型進行加權(quán)拓展，提出TwBA模型和局域世界模型TwLW(局部拓撲加權(quán)可以拓展到任何無權(quán)網(wǎng)絡(luò)模型，在此以經(jīng)典的BA模型為例，說明局部拓撲對拓撲演化的促進作用)。TwBA演化步驟為：

(2)賦權(quán)：根據(jù)式(1)對初始網(wǎng)絡(luò)的已有邊進行賦權(quán)；

(4)權(quán)值更新：根據(jù)式(1)對變化和新加入的邊重新賦權(quán)；

(5)返回步驟(3)，直至網(wǎng)絡(luò)達到指定大小。

TwBA模型說明了新連接的偏好連接不僅僅和其節(jié)點度有關(guān)，也與其周圍拓撲結(jié)構(gòu)相關(guān)。同理，在加入局域世界后，把TwBA模型拓展為TwLW模型，其具體演化步驟則表示為：

(2)賦權(quán)：根據(jù)式(1)對初始網(wǎng)絡(luò)的已有邊進行賦權(quán)；

(5)權(quán)值更新：根據(jù)式(1)對變化和新加入的邊重新賦權(quán)；

(6)返回步驟(3)，直至網(wǎng)絡(luò)達到指定大小。

同樣，當TwLW中局域世界為整個網(wǎng)絡(luò)時，TwLW則轉(zhuǎn)變?yōu)門wBA模型。TwLW模型中，新節(jié)點難以獲取整個網(wǎng)絡(luò)的信息[34]，其建立連接是在一定的社交圈內(nèi)根據(jù)已有節(jié)點及其社會關(guān)系進行優(yōu)先選擇。

3.2度分布分析

不同于BA模型的標準冪律分布，經(jīng)過局部拓撲加權(quán)后，TwBA呈現(xiàn)了從指數(shù)分布到冪律分布變化的度分布形式。圖2顯示了相同初始網(wǎng)絡(luò)下BA模型和TwBA模型的度分布對比。BA模型隨著連邊數(shù)的增加始終保持冪律分布，而對于TwBA模型，當值較小時，呈現(xiàn)近指數(shù)分布(一些朋友關(guān)系網(wǎng)[35]、蛋白質(zhì)[36]等實際網(wǎng)絡(luò)的度分布形式)；隨著值的增大，TwBA的度分布迅速轉(zhuǎn)變?yōu)閮缏尚问剑也鍒D互余累積度分布曲線中均展現(xiàn)出了指數(shù)截斷現(xiàn)象[22]。實證研究表明，大多數(shù)網(wǎng)絡(luò)的度分布為近冪律分布且存在加速增長的現(xiàn)象[24]，TwBA隨著的增大，迅速趨向于冪律分布，也說明了現(xiàn)實網(wǎng)絡(luò)的加速演化、平均連接的迅速增多，也是促進網(wǎng)絡(luò)形成冪律分布的一個內(nèi)部驅(qū)動。TwBA利用局部拓撲信息對BA模型進行了拓展，使其更多地符合了實際網(wǎng)絡(luò)的演化過程和度分布形式，說明了局部拓撲信息耦合對網(wǎng)絡(luò)演化的促進作用。

圖2 度分布對比 (，插圖為互余累積度分布曲線)

由于大量實際網(wǎng)絡(luò)如萬維網(wǎng)、合作網(wǎng)絡(luò)、蛋白質(zhì)和引文網(wǎng)絡(luò)在演化過程中均存在連邊數(shù)目加速增長的現(xiàn)象[24]。在TwBA的基礎(chǔ)上，令，提出一種加速演化模型A-TwBA，其中為初始連邊數(shù)目(),為加速演化速率()。在不同參數(shù)下，加速演化模型的度分布情形如圖3所示。多數(shù)情形下模型均為冪律分布，部分情形下，甚至同時出現(xiàn)了單峰[26]和冪律分布，這與一類實際網(wǎng)絡(luò)如線蟲神經(jīng)網(wǎng)絡(luò)(CE)等網(wǎng)絡(luò)的度分布較為契合[6]。當初始連邊數(shù)為0,時(圖3(a))，最大連邊數(shù)，此時連邊數(shù)目變化較小(從1到3)，模型呈現(xiàn)輕微的指數(shù)分布傾向，而隨著初始的增大(圖3(c)、圖3(d))，其度分布均展現(xiàn)為冪律分布，但無論加速演化速率多小，只要網(wǎng)絡(luò)規(guī)模足夠大，模型均能演化為冪律分布的形式。圖3中所有不同初始連邊數(shù)目下均顯示了模型在演化速率越大時，其冪律指數(shù)越大，度分布越陡峭，說明了網(wǎng)絡(luò)加速增長的速率越快，其度分布下降速度越快，無標度程度越明顯。A-TwBA一定程度上反映了網(wǎng)絡(luò)在加速演化中度分布的無標度特征。

圖3 A-TwBA模型的度分布

TwLW模型是在TwBA基礎(chǔ)上添加了局域世界。圖4顯示了不同的局域世界規(guī)模和連邊數(shù)目下的互余累積度分布情況(=10000)。圖4(a)中隨著局域世界規(guī)模的增大，LW模型的度分布由近冪律分布到廣延指數(shù)分布的變化過程。當局域世界為整個網(wǎng)絡(luò)大小時，此時為TwBA模型，則依連邊數(shù)目從指數(shù)分布變化為冪律分布。圖4(b)中顯示了時，不同連邊數(shù)目下度分布情形，此時總體呈現(xiàn)出近冪律分布(廣延指數(shù)分布)的形式，并隨著連邊數(shù)目的增加，冪律指數(shù)逐漸增大。廣延指數(shù)分布普遍存在于一些合作網(wǎng)絡(luò)系統(tǒng)中如淮陽菜肴系統(tǒng)、旅游交通線路系統(tǒng)、以及好萊塢演員網(wǎng)[23]。從上述TwBA, A-TwBA和TwLW的度分布統(tǒng)計結(jié)果中，局部拓撲加權(quán)使模型進一步符合了實際網(wǎng)絡(luò)情形，從宏觀數(shù)據(jù)統(tǒng)計上驗證了實際網(wǎng)絡(luò)中局部拓撲耦合能夠促進網(wǎng)絡(luò)演化這一演化機制。

圖4 TwLW的度分布 (，插圖為互余累積度分布曲線)

4 基于局部拓撲信息加權(quán)的鏈路預(yù)測方法及實證分析

4.1基于局部拓撲信息加權(quán)的鏈路預(yù)測方法

通過局部拓撲加權(quán)對網(wǎng)絡(luò)所有節(jié)點間的聯(lián)系加權(quán)后，基于基本無權(quán)網(wǎng)絡(luò)預(yù)測指標，分別把3個鏈路預(yù)測方法拓展為含權(quán)的預(yù)測方法[31]，包括CN, Salton和RA等相似性指標(局部拓撲加權(quán)可以拓展到多種相似性預(yù)測指標，在此以CN等指標為例，說明局部拓撲促進演化這一機制在實際網(wǎng)絡(luò)中的有效性)，其中CN指標可以拓展為TwCN，具體相似度表示為

(3)

4.2 衡量指標及網(wǎng)絡(luò)數(shù)據(jù)

評價鏈路預(yù)測算法精確程度的指標為AUC。AUC可以簡單地理解為在測試集中隨機選擇一條邊的分數(shù)值大于未連接邊的分數(shù)值高的概率[16]。若測試集中邊大于未連接邊的分數(shù)()，則加1分，若兩者相等()，則加0.5分，表示為

為了更好地體現(xiàn)在現(xiàn)實網(wǎng)絡(luò)中局域信息加權(quán)對相似性指標的優(yōu)化作用，選擇了7個不同類型的實際網(wǎng)絡(luò)數(shù)據(jù)進行測試包括：(1)Politicalblogs (PB)[25]：美國某政治論壇的博客首頁之間通過超鏈接構(gòu)成的網(wǎng)絡(luò)；(2) Hamster[35]: 在hamsterster.com網(wǎng)頁上的用戶朋友關(guān)系網(wǎng)絡(luò)；(3)Yeast[36]：蛋白質(zhì)相互作用網(wǎng)絡(luò)，節(jié)點表示蛋白質(zhì)，邊為相互作用關(guān)系；(4) Caenorhabditis Elegans (CE)[6]：線蟲神經(jīng)網(wǎng)絡(luò)，節(jié)點代表線蟲的神經(jīng)元，邊為神經(jīng)元突觸(synapse)或間隙連接(gap junction)；(5)Power[6]：美國西部電力網(wǎng)絡(luò)，節(jié)點表示變電站或換流站，連邊為高壓線；(6)Kohonen[27]：有關(guān)自組織映射主題或Kohonen T的論文引用網(wǎng)絡(luò)；(7)Router[28]：路由器層次的Internet。上述網(wǎng)絡(luò)具體的特征參數(shù)如表1所示，包含節(jié)點數(shù)目()，邊的數(shù)目()，平均度，集聚系數(shù)()[6]和匹配系數(shù)[37]。在試驗測試中，設(shè)置集合中邊數(shù)占比為0.9，則為0.1，測試結(jié)果均為100次結(jié)果的均值。

表1 網(wǎng)絡(luò)數(shù)據(jù)特征參數(shù)

4.3實證分析

為了在實際網(wǎng)絡(luò)中驗證局部拓撲信息耦合促進網(wǎng)絡(luò)演化的有效性，分別對比了局部拓撲加權(quán)和非加權(quán)的鏈路預(yù)測指標在實際網(wǎng)絡(luò)中的預(yù)測準確度，其中相似性指標包括CN, Salton和RA。

表2的數(shù)據(jù)對比可以看出，拓撲加權(quán)后的預(yù)測精度均高于未加權(quán)的預(yù)測指標，這一定程度上驗證了局部拓撲加權(quán)在實際網(wǎng)絡(luò)中的有效性。在Router等稀疏網(wǎng)絡(luò)中，AUC的增大是顯著的，尤其是TwRA可以把RA指標的AUC從0.65提高到0.96。相比全局性指標Katz()，LHN-II()，大多數(shù)情況下TwCN等含權(quán)指標的預(yù)測精度高于LHN-II，部分高于Katz，但從CN拓展到TwCN等并沒有在時間復(fù)雜度上有量級的變化(Tw的復(fù)雜度與CN同一個量級)。由于全局性算法復(fù)雜度較高，在大規(guī)模網(wǎng)絡(luò)中使用便受到一定的限制。同時，局部指標可以應(yīng)用于大規(guī)模實際網(wǎng)絡(luò)，但預(yù)測精度不足。通過局部拓撲加權(quán)后，既能使局部預(yù)測指標的預(yù)測精度接近全局性指標，又能夠使其應(yīng)用于大規(guī)模網(wǎng)絡(luò)，具有重要的實際應(yīng)用價值。實際含權(quán)網(wǎng)絡(luò)的預(yù)測中，相似性指標預(yù)測并沒有表現(xiàn)出很好的結(jié)果，權(quán)值高的邊起的作用反而難以界定，甚至出現(xiàn)了“弱連接”(weak tie)效應(yīng)[31]，而局部拓撲加權(quán)則有效促進了相似性指標的預(yù)測精度。綜上所述，在不改變當前相似性指標時間復(fù)雜度量級的基礎(chǔ)上，局部拓撲加權(quán)能夠有效提高相似性指標的預(yù)測精度，其中部分甚至高于全局性指標，驗證了實際網(wǎng)絡(luò)中局部拓撲信息耦合促進網(wǎng)絡(luò)演化這一機制的有效性。

表2 局部拓撲加權(quán)和非加權(quán)的相似性指標AUC結(jié)果對比

5 結(jié)論

許多網(wǎng)絡(luò)演化模型認為度優(yōu)先選擇是冪律分布產(chǎn)生的重要機制。然而，越來越多的研究表明，新連接的選擇更多的是基于節(jié)點及其周圍拓撲關(guān)系的優(yōu)先選擇。基于局部拓撲信息耦合對網(wǎng)絡(luò)網(wǎng)絡(luò)演化的促進作用，本文提出了一種局部拓撲加權(quán)方法，將其應(yīng)用于拓撲演化模型，分別拓展為TwBA, A-TwBA和TwLW模型，產(chǎn)生了從指數(shù)分布到冪律分布，部分出現(xiàn)單峰和廣延指數(shù)分布形式，宏觀統(tǒng)計上實證了模型的有效性；然后，將其應(yīng)用與鏈路預(yù)測，分別拓展了CN, Salton和RA相似性指標(加權(quán)方法可以應(yīng)用于任何相似性指標)。實際網(wǎng)絡(luò)數(shù)據(jù)測試表明，拓展后的相似性指標的預(yù)測效果較好，這一定程度上驗證了在實際網(wǎng)絡(luò)中局部拓撲加權(quán)確實能夠揭示實際網(wǎng)絡(luò)連邊機理。由于演化模型的研究一直基于宏觀統(tǒng)計，沒有統(tǒng)一的衡量標準，很多學(xué)者認為鏈路預(yù)測可以對演化模型進行評價，也普遍認同每一種演化模型就對應(yīng)一個預(yù)測方法。本文從局部拓撲耦合促進網(wǎng)絡(luò)演化這一機制出發(fā)，分別將局部拓撲加權(quán)應(yīng)用于經(jīng)典的網(wǎng)絡(luò)演化模型和鏈路預(yù)測，從宏觀統(tǒng)計和實際網(wǎng)絡(luò)數(shù)據(jù)兩個方面驗證了演化機制的合理性，也說明了復(fù)雜網(wǎng)絡(luò)演化模型和鏈路預(yù)測在同一演化機制上的統(tǒng)一。

[1] BIAN Jiang, XIE Mengjun, TOPALOGLU U,. Social network analysis of biomedical research collaboration networks in a CTSA institution[J]., 2014, 52(1): 130-140.doi:10.1016/j.jbi. 2014.01.015.

[2] WANG Shengjun, WANG Zhen, JIN Tao,. Emergence of disassortative mixing from pruning nodes in growing scale-free networks[J]., 2014, 4(7): 7536-7541. doi:10.1038/srep07536.

[3] ZHANG Yudong, BAO Zhejing, CAO Yijia,. Long-term effect of different topology evolutions on blackouts in power grid[J].&, 2014, 62(4): 718-726.doi:10.1016/j.ijepes.2014. 04.056.

[4] TESCHENDORFF A E, BANERJI C R S, SEVERINI S,. Increased signaling entropy in cancer requires the scale-free property of protein interaction networks[J]., 2015, 5(9), article number: 9646.doi: 10.1038/srep09646.

[5] SUN Li, LIU Like, XU Zhongzhi,. Locating inefficient links in a large-scale transportation network[J].:, 2015, 419(2): 537-545.doi:10.1016/j.physa.2014.10.066.

[6] WATTS D J and STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]., 1998, 393(6684): 440-442.doi: 10.1038/30918.

[7] BARABáSI A L and ALBERT R. Emergence of scaling in random networks[J]., 1999, 286(5439): 509-512.doi: 10.1126/science.286.5439.509.

[8] 方錦清, 汪小帆, 鄭志剛, 等. 一門嶄新的交叉科學(xué):網(wǎng)絡(luò)科學(xué)(上)[J]. 物理學(xué)進展,2007, 27(3): 239-343.

FANG Jinqing, WANG Xiaofan, ZHENG Zhigang,. New interdisciplinary science: network science (1)[J]., 2007, 27(3): 239-343.

[9] ALBERT R and BARABáSI A L. Topology of evolving networks: local events and universality[J]., 2000, 85(24): 5234-5237. doi:10.1103/PhysRevLett. 85.5234

[10] BIANCONI G and BARABáSI A L. Bose-einstein condensation in complex networks[J]., 2001, 86(24): 5632-5635. doi: 10.1103/PhysRevLett.86.5632.

[11] LI Xiang and CHEN Guanrong. A local-world evolving network model[J]., 2003, 328(1): 274-286.doi: 10.1016/S0378- 4371(03)00604-6.

[12] BARRAT A, BARTHéLEMY M, and VESPIGNANI A. Weighted evolving networks: coupling topology and weight dynamics[J].2004, 92(22): 228701-228706. doi: 10.1103/PhysRevLett.92.228701.

[13] YANG Chunxia, TANG Minxuan, TANG Haiqiang,. Local-world and cluster-growing weighted networks with controllable clustering[J]., 2014, 25(5): 1440009-1440021.doi: 10.1142/S0129183114400099.

[14] DAI Meifeng and ZHANG Danping. Weighted evolving network with aging-node-deleting and local rearrangements of weights[J]., 2014, 25(2): 1350093-1350102. doi:10.1142/S0129183 113500939.

[15] 王丹, 金小崢. 可調(diào)聚類系數(shù)加權(quán)無標度網(wǎng)絡(luò)建模及其擁塞問題研究[J]. 物理學(xué)報, 61(22): 228901-228910.

WANG Dan and JIN XiaoZheng. On weightd scale-free network model with tunable clustering and congesstion[J]., 2012, 61(22): 228901-228910.

[16] Lü Linyuan and ZHOU Tao. Link prediction in complex networks: a survey[J].:, 2011, 390(6): 1150-1170.doi:10.1016/ j.physa.2010.11.027.

[17] LORRAIN F and WHITE H C. Structural equivalence of individuals in social networks[J].1971, 1(1): 49-80.doi: 10.1080/ 0022250X.1971.9989788.

[18] SALTON G and MCGILL M J. Introduction to Modern Information Retrieval[M]. New York: McGraw-Hill, 1983: 30-31.

[19] ZHOU Tao, Lü Linyuan, and ZHANG Yicheng. Predicting missing links via local information[J].2009, 71(4): 623-630.doi:10.1140/epjb/ e2009-00335-8.

[20] LEICHT E A, HOLME P, and NEWMAN M E J. Vertex similarity in networks[J]., 2006, 73(2): 026120-0261125.doi: 10.1103/PhysRevE.73.026120.

[21] KATZ L and POWELL J H. A proposed index of the conformity of one sociometric measurement to another[J]., 1953, 18(3): 249-256. doi:10.1007/ BF02289063.

[22] 汪小帆, 李翔, 陳關(guān)榮. 復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M]. 北京：清華大學(xué)出版社, 2006: 35-85.

WANG Xiaofan, LI Xiang, and CHEN Guanrong. Complex Networks Theory and Its Applications[M]. Beijing: Tsinghua University Press, 2006: 35-85.

[23] ROBERTS J A, IYER K K, FINNIGAN S,. Scale-free bursting in human cortex following hypoxia at birth[J]., 2014, 34(19): 6557-6572.

[24] ZHANG Zhongzhi, FANG Lujun, ZHOU Shuigeng,. Effects of accelerating growth on the evolution of weighted complex networks[J].:2009, 388(2): 225-232. doi: 10.1016/j. physa.2008.10.008.

[25] ADAMIC L A and GLANCE N. The Political blogosphere and the 2004 US election: divided they blog[C]. Proceedings of the 3rd ACM International Workshop on Link Discovery,New York, NY, USA, 2005: 36-43.doi: 10.1145/1134271. 1134277.

[26] WANG Qing and GUO Jinli. Human dynamics scaling characteristics for aerial inbound logistics operation[J].:, 2010, 389(10): 2127-2133.doi:10.1016/j.physa.2010.01.009.

[27] TAN Fei, XIA Yongxiang, and ZHU Boyao. Link prediction in complex networks: a mutual information perspective[J]., 2014, 9(9): e107056-e107061. doi: 10.1371/ journal.pone.0107056.

[28] SPRING N, MAHAJAN R, and WETHERALL D. Measuring ISP topologies with rocketfuel[J]., 2002, 32(4): 133-145. doi:10.1145/964725.633039.

[29] 崔愛香, 傅彥, 尚明生, 等. 復(fù)雜網(wǎng)絡(luò)局部結(jié)構(gòu)的涌現(xiàn): 共同鄰居驅(qū)動網(wǎng)絡(luò)演化[J]. 物理學(xué)報, 2011, 60(3): 803-808.

CUI Aixiang, FU Yan, SHANG Mingsheng,. Emergence of local structures in complex network: common neighborhood drives the network evolution[J]., 2011, 60(3): 803-808.

[30] 劉樹新, 季新生, 劉彩霞, 等. 一種信息傳播促進網(wǎng)絡(luò)增長的網(wǎng)絡(luò)演化模型[J]. 物理學(xué)報, 2014, 63(15): 158902.

LIU Shuxin, JI Xinsheng, LIU Caixia,. A complex network evolution model for network growth promoted by information transmission[J].2014, 63(15): 158902.

[31] Lü Linyuan and ZHOU Tao. Link prediction in weighted networks: The role of weak ties[J]., 2010, 89(1): 18001-18006. doi:10.1209/0295-5075/89/18001.

[32] XIE Zhou, LI Xiang, and WANG Xiaofan. A new community-based evolving network model[J]., 2007, 384(2): 725-732.doi:10.1016/j.physa.2007.05.031.

[33] LI Fenhua, HE Jing, HUANG Guangyan,. A clustering-based link prediction method in social networks[J]., 2014, 29(5): 432-442.doi: 10.1016/j.procs.2014.05.039.

[34] YANF Guangyong and LIU Jianguo. A local-world evolving hypernetwork model[J]., 2014, 23(1): 018901-018909. doi:10.1088/1674-1056/23/1/018901.

[35] Lü Linyuan, PAN Liming, ZHOU Tao,. Toward link predictability of complex networks[J]., 2015, 112(8): 2325-2330.

[36] VON MERING C, KRAUSE R, SNEL B,. Comparative assessment of large-scale data sets of protein-protein interactions[J]., 2002, 417(6887): 399-403.doi: 10.1038/nature750.

[37] SENDI?A-NADAL I, LEYVA I, NAVAS A,Effects of degree correlations on the explosive synchronization of scale-free networks[J]., 2015, 91(3): 032811-032819.doi: 10.1103/PhysRevE.91.032811.

Information Coupling of Local Topology Promoting the Network Evolution

LIU Shuxin①JI Xinsheng①②LIU Caixia①TANG Hongbo①GONG Xiaorui①

①(National Digital Switching System Engineering and Technological R&D Center, Zhengzhou 450002, China)②(National Engineering Laboratory for Mobile Network Security, Beijing 100876, China)

To study the effects of information coupling of local topology on the complex network evolution, a new weighted method is proposed based on local topology information, which can measure the closeness of connection and the coupling degree of topology information between nodes. In this paper, to demonstrate the efficiency of the information coupling of local topology, an empirical research is made on characteristic statistics of evolving model and real network data testing of link prediction respectively. Firstly, the weighted method is applied to BA model; TwBA and the local world model TwLW are proposed based on the topology weighted method. Simulation experiments show that the degree distribution of TwBA can be rapidly changed from exponential distribution to power law distribution with the increasing of the connection numbers for new added nodes, which confirmes that the phenomenon of accelerating growth appears widely in the evolution of many real scale-free networks. Then, based on TwBA model, an accelerating growth model A-TwBA is proposed, and the A-TwBA model presents power law distribution for different accelerating growth rates. The degree distribution of TwLW is changed from stretched exponential distribution to power law distribution for different sizes of local world. Finally, the proposed weighted method is applied to link prediction methods (including CN, Salton and RA index), and three weighted indices are proposed. Empirical study shows that the weighted proposed method can significantly improve the prediction accuracy of these basic indices, and some of them are higher than those of the global indices.

Complex network; Local topology; Evolving model; Link prediction; Information coupling

N94; TP3; TP391

A

1009-5896(2016)09-2180-08

10.11999/JEIT151338

2015-11-26；

2016-04-07；

2016-05-25

國家自然科學(xué)基金創(chuàng)新研究群體項目(61521003)，國家高技術(shù)研究發(fā)展計劃(2014AA01A701)

The Foundation for Innovative Research Groups of the National Natural Science Foundation of China (61521003), The National High Technology Research and Development Program of China (2014AA01A701)

劉樹新 liushuxin11@126.com

劉樹新： 男，1987年生，博士，研究方向為復(fù)雜網(wǎng)絡(luò)、鏈路預(yù)測、移動網(wǎng)絡(luò)安全.

季新生： 男，1968年生，教授，博士生導(dǎo)師，研究方向為移動網(wǎng)絡(luò)安全、移動通信技術(shù)、無線網(wǎng)絡(luò)防護.

劉彩霞： 女，1974年生，副教授，碩士生導(dǎo)師，研究方向為網(wǎng)絡(luò)安全、社會網(wǎng)絡(luò)、下一代移動網(wǎng)絡(luò).

湯紅波： 男，1968年生，教授，碩士生導(dǎo)師，研究方向為移動網(wǎng)絡(luò)安全、下一代移動網(wǎng)絡(luò).

鞏小銳： 男，1991年生，博士，研究方向為新型網(wǎng)絡(luò)體系結(jié)構(gòu)、社會網(wǎng)絡(luò).