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.
刘树新,季新生,刘彩霞,汤红波,巩小锐. 局部拓扑信息耦合促进网络演化[J]. 电子与信息学报, 2016, 38(9): 2180-2187.
LIU Shuxin, JI Xinsheng, LIU Caixia, TANG Hongbo, GONG Xiaorui. Information Coupling of Local Topology Promoting the Network Evolution. JEIT, 2016, 38(9): 2180-2187.
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.
[2]
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.
[3]
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.
[4]
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.
[5]
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.
[6]
WATTS D J and STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440-442. doi: 10.1038/30918.
[7]
BARABÁSI 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.
FANG Jinqing, WANG Xiaofan, ZHENG Zhigang, et al. New interdisciplinary science: network science (1)[J]. Progress in Physics, 2007, 27(3): 239-343.
[9]
ALBERT R and BARABÁSI 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
[10]
BIANCONI G and BARABÁSI A L. Bose-einstein condensation in complex networks[J]. Physical Review Letters, 2001, 86(24): 5632-5635. doi: 10.1103/PhysRevLett.86.5632.
[11]
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.
[12]
BARRAT A, BARTHÉLEMY 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.
[13]
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.
[14]
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.
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.
[16]
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.
[17]
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.
[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]. The European Physical Journal B, 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]. Physical Review E, 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]. Psychometrika, 1953, 18(3): 249-256. doi: 10.1007/ BF02289063.
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, et al. Scale-free bursting in human cortex following hypoxia at birth[J]. The Journal of Neuroscience, 2014, 34(19): 6557-6572.
[24]
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.
[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]. Physica A: Statistical Mechanics and Its Applications, 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]. PLoS ONE, 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]. Acm Sigcomm Computer Communication Review, 2002, 32(4): 133-145. doi: 10.1145/964725.633039.
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.
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.
[31]
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.
[32]
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.
[33]
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.
[34]
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.
[35]
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.
[36]
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.
[37]
SENDIÑA-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.
