| 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 |
|
|
|
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.
|
|
Published: 01 March 2017
|
|
|
|
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.
|
复杂网络中的抽样链接预测
针对传统相似度算法无法预测给定顶点存在的链接问题,以抽样方法为基础,提出一种对复杂网络进行链接预测的方法,找出用户感兴趣节点的相关链接.根据用户感兴趣的节点,使用随机游走的方法,构造一个子图.设定该子图的大小使相似度估计值的误差小于给定的容错阈值.该方法仅在一个小的包含全局信息的子图上进行相似度计算,可以使计算时间大大减少.实验结果表明,算法的时间复杂度与数据集大小呈线性关系,基于局部指标的常见邻居（CN）算法、Jaccard以及PA指标算法的时间复杂度与数据集大小呈平方关系,以全局拓扑路径为基础的Katz算法的时间复杂度与数据集大小呈立方关系.
|
|
| ［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. Coauthor 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 kernelbased machine learning approach ［J］. Decision Support Systems, 2013, 54(2): 880-890.
［12］ HUANG Z, LIN D K J. The timeseries 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 EStatistical, 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. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
