On the Relationship Between Network Structure Features and Link Prediction Algorithms
JIA Jun1,2, HU Xiaofeng1, HE Xiaoyuan
1. The Department of Information Operation Command Training, National Defense University, Beijing 100091, China; 2. The Department of Graduate, National Defense University, Beijing 100091, China
Abstract：This paper experimented with five virtual networks, such as the Air network of US, the Coauthorship network of Scientists, the Neural network of the nematode C, etc. and quantified the relationship between the network structure features and the link prediction algorithms by the experiment’s data. The network structure features could be measured by assortativity coefficient, clustering coefficient, etc. and the link prediction algorithms could be divided into local-information based and global-information based. After analyzed the data, we found that if the value of network’s assortativity coefficient is positive and the value of network’s clustering coefficient is greater than the threshold which is about 0.1, the local-information based would be the better choice, otherwise the global-information based would be better. And the clustering coefficient and the network efficiency is proportional to the result of link prediction algorithms based local information and is reverse proportional to the result of algorithms based global information. These conclusions provide quantitative basis for selecting the right algorithm.
贾珺, 胡晓峰, 贺筱媛. 网络结构特征与链路预测算法关系研究[J]. 复杂系统与复杂性科学, 2017, 14(1): 28-37.
JIA Jun, HU Xiaofeng, HE Xiaoyuan. On the Relationship Between Network Structure Features and Link Prediction Algorithms[J]. Complex Systems and Complexity Science, 2017, 14(1): 28-37.
[1] Al Hasan M, Zaki M J. A survey of link prediction in social networks[M].Social network data analytics, Springer US, 2011: 243-275. [2] Sarukkai R R. Link prediction and path analysis using markov chains[J].Computer Networks, 2000, 33(1): 377-386. [3] Getoor L, Diehl C P. Link mining: a survey[J].ACM Sigkdd Explorations Newsletter, 2005, 7(2): 3-12. [4] Liben-Nowell D, Kleinberg J. The link prediction problem for social networks[J].Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019-1031. [5] Dong Y, Tang J, Wu S, et al. Link prediction and recommendation across heterogeneous social networks[C]//2012 IEEE 12th International Conference on Data Mining. 2012: 181-190. [6] Cannistraci C V, Alanis-Lobato G, Ravasi T. From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J].Scientific Reports, 2013, 3(4):1613. [7] Lü L, Zhou T. Link prediction in complex networks: a survey[J].Physica A: Statistical Mechanics and Its Applications, 2011, 390(6): 1150-1170. [8] Al Hasan M, Chaoji V, Salem S, et al. Link prediction using supervised learning[J]//Proc of Sdm Workshop Link Analysis Counterrorism & Security,2005,30(9):798-805. [9] Miller K, Jordan M I, Griffiths T L. Nonparametric latent feature models for link prediction[J]//Advances in Neural Information Processing Systems. 2009: 1276-1284. [10] Fire M, Tenenboim L, Lesser O, et al. Link prediction in social networks using computationally efficient topological features[C].Privacy, Security, Risk and Trust (PASSAT) and 2011 IEEE Third Inernational Conference on Social Computing (SocialCom), 2011 IEEE Third International Conference on. IEEE, 2011: 73-80. [11] Clauset A, Moore C, Newman M E J. Hierarchical structure and the prediction of missing links in networks[J].Nature, 2008, 453(7191): 98-101. [12] Ding J, Jiao L, Wu J, et al. Prediction of missing links based on multi-resolution community division[J].Physica A: Statistical Mechanics and Its Applications, 2015, 417: 76-85. [13] Lü L, Pan L, Zhou T, et al. Toward link predictability of complex networks[J].Proceedings of the National Academy of Sciences, 2015, 112(8): 2325-2330. [14] Liu H K, Ln L Y,Zhou T. Uncovering the network evolution mechanism by link prediction[J].Sci Sin Phys Mech Astron, 201l, 41:816-823 [15] Huang Z. Link prediction based on graph topology: the predictive value of generalized clustering coefficient[J].Social Science Electronic Publishing,2010:1634014. [16] Milward H B, Provan K G. Measuring network structure[J].Public Administration, 1998, 76(2): 387-407. [17] Newman M E J. The structure and function of complex networks[J].SIAM Review, 2003, 45(2): 167-256. [18] Newman M J. The structure of scientic collaboration networks[J].Proc of the National Acad of Sciences, 2001,98(2):404-409. [19] Lazer D, Friedman A. The network structure of exploration and exploitation[J].Administrative Science Quarterly, 2007, 52(4): 667-694. [20] Reagans R, McEvily B. Network structure and knowledge transfer: the effects of cohesion and range[J].Administrative Science Quarterly, 2003, 48(2): 240-267. [21] Wagner C S, Leydesdorff L. Network structure, self-organization, and the growth of international collaboration in science[J].Research Policy, 2005, 34(10): 1608-1618. [22] Jalili M, Sichani O A, Yu X. Optimal pinning controllability of complex networks: dependence on network structure[J].Physical Review E, 2015, 91(1): 012803. [23] Ahn M W, Jung W S. Accuracy test for link prediction in terms of similarity index: the case of WS and BA models[J].Physica A: Statistical Mechanics and Its Applications, 2015. [24] Schult D A, Swart P J. Exploring network structure, dynamics, and function using NetworkX[C].Proceedings of the 7th Python in Science Conferences, 2008: 11-16. [25] Alstott J, Bullmore E, Plenz D. Powerlaw: a python package for analysis of heavy-tailed distributions[J].PLoS One, 2014, 9(1): e85777. [26] Gleiser P M, Danon L. Community structure in jazz[J].Aduances in Complex Systems, 2003, 6(4): 565-573. [27] Newman M E J. Finding community structure in networks using the eigenvectors of matrics[J].Physical Review E, 2006,74(3):036104. [28] Watts D J, Strogatz S H. Collective dynamics of small-world networks[J].Nature, 1998, 393(6684): 440-442.
