Please wait a minute...
Computer Technology, Electronic Communications Technologies     
Sampling-based link prediction in complex networks
DAI Cai-yan, CHEN Ling, LI Bin, CHEN Bo-lun
1. Nanjing University of Aeronautics and Astronautics, College of Computer Science and Technology, Nanjing 210000, China;
2. College of Information Science and Technology, Yangzhou University, Yangzhou 225009, China
Download:   PDF(1085KB) HTML
Export: BibTeX | EndNote (RIS)      

A method of predicting links in complex networks based on sampling method was proposed to find out the link corresponding to the nodes of interest to users, aiming at the problem that the traditional similarity algorithm could not predict the link of a given vertex. Firstly, a corresponding sub-graph of the nodes of interest to users was constructed by method of random walk. By setting an appropriate size of the sub-graph, the similarity error could be restricted to a given fault tolerant threshold range. Since the similarity computation of this method was only operated in a small sub graph which contained the global information,the time cost for computation was greatly reduced. As indicated, the time complexity of this algorithm is linear to the size of the data set; while the other similar algorithms based on local index, such as CN (common neighbor), Jaccard and PA (preferential attachment), are square to the size of the data set; for the global path based approach Katz, the time complexity is cubic to the size of the data set.

Published: 01 March 2017
CLC:  TP 391.1  
Cite this article:

DAI Cai-yan, CHEN Ling, LI Bin, CHEN Bo-lun. Sampling-based link prediction in complex networks. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2017, 51(3): 554-561.



[1] LU L Y, ZHOU T. Link prediction in complex networks: a survey [J]. Physica A, 2011, 390(6): 1150-1170.
[2] KAYA B, POYRAZ M. Age-series based link prediction in evolving disease networks [J]. Computers in Biology and Medicine, 2015, 63: 1-10.
[3] BAO Z F, ZENG Y, TAY Y C. sonLP: social network link prediction by principal component regression [C] ∥ Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Canada: ACM, 2013: 364-371.
[4] PAPADIMITRIOU A, SYMEONIDIS P, YANNIS M. Fast and accurate link prediction in social networking systems [J]. Journal of Systems and Software,2012,85(9): 2119-2132.
[5] FOURNET J, BARRAT A. Contact patterns among high school students [J]. PLoS One, 2014, 9(9):e107878.
[6] BUCCAFURRI F, LAX G, NOCERA A, et al. Discovering missing me edges across social networks [J]. Information Sciences, 2015, 319: 18-37.
[7] JAHANBAKHSH K, KING V, SHOJA G C. Predicting missing contacts in mobile social networks [J]. Pervasive and Mobile Computing, 2012, 8(5):698-716.
[8] SUN Y, BARBERY R, GUPTA M., AGGARWAL C C, et al. Coauthor relationship prediction in heterogeneous bibliographic networks [C] ∥Proceedings of 2011 International Conference on Advances in Social Networks Analysis and Mining. Taiwan: IEEE, 2011: 121-128.
[9] XIE F, CHEN Z, SHANG J X, et al. A link prediction approach for item recommendation with complex number [J]. Knowledge-Based Systems,2015, 81: 148-158.
[10] VIDMER A, ZENG A, MEDO M, et al. Prediction in complex systems: the case of the international trade network [J]. Physica A: Statistical Mechanics and its Applications, 2015, 436: 188-199.
[11] LI X, CHEN H C. Recommendation as link prediction in bipartite graphs: a graph kernelbased machine learning approach [J]. Decision Support Systems, 2013, 54(2): 880-890.
[12] HUANG Z, LIN D K J. The timeseries link prediction problem with applications in communication surveillance [J]. INFORMS J on Computing, 2009,21(2): 286-303.
[13] LIU H. Uncovering the network evolution mechanism by link prediction [J]. Scientia Sinica Physica, Mechanica and Astronomica, 2011, 41:816-823.
[14] LV L, JIN C H, ZHOU T. Similarity index based on local paths for link prediction of complex networks [J]. Physical Review EStatistical, Nonlinear, and Soft Matter Physics, 2009, 80(4): 046122.
[15] LIU W P, LV L. Linkprediction based on local random walk[J]. European Physics Letter, 2010, 89(5): 58007.
[16] WANG X J, ZHANG X, ZHAO C L, et al. Predicting link directions using local directed path [J]. Physica A: Statistical Mechanics and itsApplications. 2015, 419: 260-267.
[17] POPESCUL A, UNGAR L. Statistical relational learning for link prediction [C] ∥ In Proceedings of the International Workshop on Learning Statistical Models from Relational Data. Mexico: IJCAI, 2003: 172-179.
[18] HANNEKE S, FU W J, XING E P. Discrete temporal models of social Networks [J]. Electronic Journal of Statistics, 2010, 4: 585-605.
[19] HU F, WONG H S. Labeling of human moion based on CBGA and probabilistic model \[J\]. International Journal on Smart Sensing and Intelligent Systems, 2013, 6(2): 583-609.
[20] MUNARO A. The VC-dimension of graphs with respect to K-connected subgraphs [J]. Discrete Applied Mathematics, 2016, 211: 163-174.
[21] LI Y, LONG P M. Improved bounds on the sample complexity of learning [J]. Journal of Computer and System Sciences, 2001, 62(1): 516-527.
[22] Link Prediction Group. Resources [EB/OL]. [2013-05-25].http:∥
[1] XU Qi, GU Xin-jian. Subject-action-object-triples-based method  for extraction of knowledge gene[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2013, 47(3): 385-399.
[2] YAO Yuan-gang, LIN Lan-fen, DONG Jin-xiang. Approach for multi-dimensional associated heterogeneous
engineering document semantic retrieval
[3] QIU Guang, ZHENG Miao, ZHANG Hui, ZHU Jianke, BU Jia-jun, CHEN Chun, HANG Hang. Implicit product feature extraction through regularized topic modeling[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2011, 45(2): 288-294.
[4] QIU Guang, ZHENG Miao, BU Jia-jun, SHI Yuan, CHEN Chun. Propagation based product feature extraction[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2010, 44(11): 2188-2193.