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
摘要:

针对传统相似度算法无法预测给定顶点存在的链接问题,以抽样方法为基础,提出一种对复杂网络进行链接预测的方法,找出用户感兴趣节点的相关链接.根据用户感兴趣的节点,使用随机游走的方法,构造一个子图.设定该子图的大小使相似度估计值的误差小于给定的容错阈值.该方法仅在一个小的包含全局信息的子图上进行相似度计算,可以使计算时间大大减少.实验结果表明,算法的时间复杂度与数据集大小呈线性关系,基于局部指标的常见邻居(CN)算法、Jaccard以及PA指标算法的时间复杂度与数据集大小呈平方关系,以全局拓扑路径为基础的Katz算法的时间复杂度与数据集大小呈立方关系.

Abstract:
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  
基金资助:

国家自然科学基金资助项目(61379066)

通讯作者: 陈崚,男,教授. ORCID: 0000-0002-8147-9687.      E-mail: yzulchen@163.com
作者简介: 戴彩艳(1985—),女,博士生,从事网络预测研究. ORCID: 0000-0003-3562-3905. E-mail: daicaiyan@163.com
服务  
把本文推荐给朋友
加入引用管理器
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:∥www.linkprediction.org/index.php/link/resource/data.
[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.