Information Coupling of Local Topology Promoting the Network Evolution

LIU Shuxin; JI Xinsheng; LIU Caixia; TANG Hongbo; GONG Xiaorui

doi:10.11999/JEIT151338

Volume 38 Issue 9

Sep. 2016

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2016 > 38(9): 2180-2187

LIU Shuxin, JI Xinsheng, LIU Caixia, TANG Hongbo, GONG Xiaorui. Information Coupling of Local Topology Promoting the Network Evolution[J]. Journal of Electronics & Information Technology, 2016, 38(9): 2180-2187. doi: 10.11999/JEIT151338

Citation:

LIU Shuxin, JI Xinsheng, LIU Caixia, TANG Hongbo, GONG Xiaorui. Information Coupling of Local Topology Promoting the Network Evolution[J]. Journal of Electronics & Information Technology, 2016, 38(9): 2180-2187. doi: 10.11999/JEIT151338

Citation:

PDF( 293 KB)

Information Coupling of Local Topology Promoting the Network Evolution

doi: 10.11999/JEIT151338

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

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)

Received Date: 2015-11-26
Rev Recd Date: 2016-04-07
Publish Date: 2016-09-19

Abstract

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

FullText(HTML)

References(42)

References

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.

Relative Articles

Supplements(0)

Cited By

Proportional views