Link prediction in complex networks via modularity-based belief propagation

作     者：赖大荣 舒欣 Christine Nardini 

作者机构：School of Computer Science and Engineering Southeast University Nanjing 211189 China Key Laboratory of Computer Network and Information Integration of Ministry of Education Southeast University Nanjing 210096 China College of Information Science and Technology Nanjing Agricultural University Nanjing 210095 China CNR-IAC 'Mauro Picone' Via dei Taurini 19 00185 Roma Italy Personalgenomics Via delle Grazie Verona Italy 

出 版 物：《Chinese Physics B》 (中国物理B（英文版）)

年 卷 期：2017年第26卷第3期

页      面：604-614页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Project supported by the National Natural Science Foundation of China(Grants No.61202262) the Natural Science Foundation of Jiangsu Province,China(Grants No.BK2012328) the Specialized Research Fund for the Doctoral Program of Higher Education of China(Grants No.20120092120034) 

主　　题：link prediction complex network belief propagation modularity 

摘      要：Link prediction aims at detecting missing, spurious or evolving links in a network, based on the topological information and/or nodes＇ attributes of the network. Under the assumption that the likelihood of the existence of a link between two nodes can be captured by nodes＇ similarity, several methods have been proposed to compute similarity directly or indirectly, with information on node degree. However, correctly predicting links is also crucial in revealing the link formation mechanisms and thus in providing more accurate modeling for networks. We here propose a novel method to predict links by incorporating stochastic-block-model link generating mechanisms with node degree. The proposed method first recov- ers the underlying block structure of a network by modularity-based belief propagation, and based on the recovered block structural information it models the link likelihood between two nodes to match the degree sequence of the network. Experiments on a set of real-world networks and synthetic networks generated by stochastic block model show that our proposed method is effective in detecting missing, spurious or evolving links of networks that can be well modeled by a stochastic block model. This approach efficiently complements the toolbox for complex network analysis, offering a novel tool to model links in stochastic block model networks that are fundamental in the modeling of real world complex networks.