Please wait a minute...
戴彩艳, 陈崚, 李斌, 陈伯伦
1.南京航空航天大学 计算机科学与技术学院,江苏 南京 210000
2.扬州大学 信息工程学院,江苏 扬州 225009
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
 全文: PDF(1085 KB)   HTML


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.
出版日期: 2017-03-01
CLC:  TP 391.1  


通讯作者: 陈崚,男,教授. ORCID: 0000-0002-8147-9687.      E-mail:
作者简介: 戴彩艳(1985—),女,博士生,从事网络预测研究. ORCID: 0000-0003-3562-3905. E-mail:
E-mail Alert


戴彩艳, 陈崚, 李斌, 陈伯伦. 复杂网络中的抽样链接预测[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2017.03.017.

DAI Cai-yan, CHEN Ling, LI Bin, CHEN Bo-lun. Sampling-based link prediction in complex networks. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2017.03.017.

[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] 许琦, 顾新建. 一种基于Subject-Action-Object三元组的知识基因提取方法[J]. J4, 2013, 47(3): 385-399.
[2] 姚原岗, 林兰芬, 董金祥. 异质工程文档多维关联的语义检索方法[J]. J4, 2011, 45(2): 267-272.
[3] 仇光, 郑淼, 张晖, 朱建科, 卜佳俊, 陈纯, 杭航. 基于正则化主题建模的隐式产品属性抽取[J]. J4, 2011, 45(2): 288-294.
[4] 仇光,郑淼,卜佳俊,史源,陈纯. 基于传播的产品属性抽取[J]. J4, 2010, 44(11): 2188-2193.