以美国航空网络、科学家合作网络和线虫新陈代谢网络等5种实际网络为例进行了综合实验,用结果数据定量化描述了同配系数、集聚系数和网络效率等网络结构特征参数,与基于局部信息和全局信息的两类链路预测方法结果之间的关系。通过对结果的分析,得到了网络同配系数为正且聚集系数大于阈值(约0.1)时适用基于局部信息的预测方法,否则适用基于全局信息的预测方法;以及集聚系数、网络效率与局部信息预测方法的结果成正比,与全局信息预测方法成反比等结论。这些结论为通过网络特征参数进行链路预测方法的选择提供了定量化的参考依据。
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.
[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.
