局部拓扑信息耦合促进网络演化

刘树新; 季新生; 刘彩霞; 汤红波; 巩小锐

doi:10.11999/JEIT151338

局部拓扑信息耦合促进网络演化

doi: 10.11999/JEIT151338

1.
(国家数字交换系统工程技术研究中心郑州 450002) ②(移动互联网安全技术国家工程实验室北京 100876)

基金项目:

国家自然科学基金创新研究群体项目(61521003)，国家高技术研究发展计划(2014AA01A701)

计量
- 文章访问数: 1312
- HTML全文浏览量: 193
- PDF下载量: 299
- 被引次数: 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)

摘要

摘要: 为了研究局部拓扑信息耦合对网络演化的促进作用，该文提出一种局部拓扑加权方法，用于表征节点间联系的紧密性及拓扑信息的耦合程度，并从演化模型的宏观统计和实际网络数据测试两方面验证了局部拓扑信息耦合促进网络演化的有效性。首先将该加权方法应用于BA模型，提出TwBA模型及局域世界模型TwLW。仿真实验表明，TwBA的度分布随连边数目的增多，迅速从指数分布转变为幂律分布，验证了现实网络加速增长产生幂律分布的现象，并基于此提出一种加速演化的TwBA模型，其在不同的加速率下呈现出幂律分布；而TwLW则展现了从广延指数分布到幂律分布变化的形式。然后将加权方法拓展到链路预测方法，提出3个加权相似性指标。实际网络数据测试表明，该方法能够大幅度地提高基本算法的预测精度，部分甚至高于全局性指标。
- 复杂网络 /
- 局部拓扑 /
- 演化模型 /
- 链路预测 /
- 信息耦合
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.

方锦清, 汪小帆, 郑志刚, 等. 一门崭新的交叉科学:网络科学(上)[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.

王丹, 金小峥. 可调聚类系数加权无标度网络建模及其拥塞问题研究[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.

汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用[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.

崔爱香, 傅彦, 尚明生, 等. 复杂网络局部结构的涌现: 共同邻居驱动网络演化[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.

刘树新, 季新生, 刘彩霞, 等. 一种信息传播促进网络增长的网络演化模型[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)

访问统计