局部拓撲信息耦合促進網絡演化

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

?

局部拓撲信息耦合促進網絡演化

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

①(國家數字交換系統工程技術研究中心 鄭州 450002)②(移動互聯網安全技術國家工程實驗室 北京 100876)

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

復雜網絡；局部拓撲；演化模型；鏈路預測；信息耦合

1 引言

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

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

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

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

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

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

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

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

3 基于局部拓撲信息加權的網絡演化模型

3.1 基于局部拓撲信息加權的網絡演化模型

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

(2)賦權：根據式(1)對初始網絡的已有邊進行賦權；

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

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

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

(2)賦權：根據式(1)對初始網絡的已有邊進行賦權；

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

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

同樣，當TwLW中局域世界為整個網絡時，TwLW則轉變為TwBA模型。TwLW模型中，新節點難以獲取整個網絡的信息[34]，其建立連接是在一定的社交圈內根據已有節點及其社會關系進行優先選擇。

3.2度分布分析

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

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

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

圖3 A-TwBA模型的度分布

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

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

4 基于局部拓撲信息加權的鏈路預測方法及實證分析

4.1基于局部拓撲信息加權的鏈路預測方法

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

(3)

4.2 衡量指標及網絡數據

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

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

表1 網絡數據特征參數

4.3實證分析

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

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

表2 局部拓撲加權和非加權的相似性指標AUC結果對比

5 結論

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

[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] 方錦清, 汪小帆, 鄭志剛, 等. 一門嶄新的交叉科學:網絡科學(上)[J]. 物理學進展,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] 王丹, 金小崢. 可調聚類系數加權無標度網絡建模及其擁塞問題研究[J]. 物理學報, 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] 汪小帆, 李翔, 陳關榮. 復雜網絡理論及其應用[M]. 北京：清華大學出版社, 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] 崔愛香, 傅彥, 尚明生, 等. 復雜網絡局部結構的涌現: 共同鄰居驅動網絡演化[J]. 物理學報, 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] 劉樹新, 季新生, 劉彩霞, 等. 一種信息傳播促進網絡增長的網絡演化模型[J]. 物理學報, 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

國家自然科學基金創新研究群體項目(61521003)，國家高技術研究發展計劃(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年生，博士，研究方向為復雜網絡、鏈路預測、移動網絡安全.

季新生： 男，1968年生，教授，博士生導師，研究方向為移動網絡安全、移動通信技術、無線網絡防護.

劉彩霞： 女，1974年生，副教授，碩士生導師，研究方向為網絡安全、社會網絡、下一代移動網絡.

湯紅波： 男，1968年生，教授，碩士生導師，研究方向為移動網絡安全、下一代移動網絡.

鞏小銳： 男，1991年生，博士，研究方向為新型網絡體系結構、社會網絡.