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

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

doi:10.11999/JEIT151338

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

doi: 10.11999/JEIT151338 cstr: 32379.14.JEIT151338

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

基金項目:

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

計量
- 文章訪問數(shù): 1474
- HTML全文瀏覽量: 231
- PDF下載量: 301
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2015-11-26
- 修回日期: 2016-04-07
- 刊出日期: 2016-09-19

Information Coupling of Local Topology Promoting the Network Evolution

1.
(National Digital Switching System Engineering and Technological R&

Funds:

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)

摘要

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

HTML全文

參考文獻(42)

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

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

ZHANG Yudong, BAO Zhejing, CAO Yijia, et al. Long-term effect of different topology evolutions on blackouts in power grid[J]. International Journal of Electrical Power Energy Systems, 2014, 62(4): 718-726. doi:10.1016/j.ijepes.2014. 04.056.

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

SUN Li, LIU Like, XU Zhongzhi, et al. Locating inefficient links in a large-scale transportation network[J]. Physica A: Statistical Mechanics and Its Applications, 2015, 419(2): 537-545. doi: 10.1016/j.physa.2014.10.066.

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

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

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

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

ALBERT R and BARABSI A L. Topology of evolving networks: local events and universality[J]. Physical Review Letters, 2000, 85(24): 5234-5237. doi: 10.1103/PhysRevLett. 85.5234

BIANCONI G and BARABSI A L. Bose-einstein condensation in complex networks[J]. Physical Review Letters, 2001, 86(24): 5632-5635. doi: 10.1103/PhysRevLett.86.5632.

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

BARRAT A, BARTHLEMY M, and VESPIGNANI A. Weighted evolving networks: coupling topology and weight dynamics[J]. Physical Review Letters, 2004, 92(22): 228701-228706. doi: 10.1103/PhysRevLett.92.228701.

YANG Chunxia, TANG Minxuan, TANG Haiqiang, et al. Local-world and cluster-growing weighted networks with controllable clustering[J]. International Journal of Modern Physics C, 2014, 25(5): 1440009-1440021. doi: 10.1142/S0129183114400099.

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

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

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

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

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

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

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

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

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

汪小帆, 李翔, 陳關榮. 復雜網(wǎng)絡理論及其應用[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.

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

ZHANG Zhongzhi, FANG Lujun, ZHOU Shuigeng, et al. Effects of accelerating growth on the evolution of weighted complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2009, 388(2): 225-232. doi: 10.1016/j. physa.2008.10.008.

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.

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

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

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

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

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

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

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

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

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

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

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

L Linyuan, PAN Liming, ZHOU Tao, et al. Toward link predictability of complex networks[J]. Proceedings of the National Academy of Sciences, 2015, 112(8): 2325-2330.

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

SENDIA-NADAL I, LEYVA I, NAVAS A, et al. Effects of degree correlations on the explosive synchronization of scale-free networks[J]. Physical Review E, 2015, 91(3): 032811-032819. doi: 10.1103/PhysRevE.91.032811.

施引文獻

資源附件(0)

訪問統(tǒng)計