Link prediction in complex networks via modularity-based belief propagation

doi:10.1088/1674-1056/26/3/038902

中国物理B ›› 2017, Vol. 26 ›› Issue (3): 38902-038902.doi: 10.1088/1674-1056/26/3/038902

• INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY • 上一篇下一篇

Link prediction in complex networks via modularity-based belief propagation

Darong Lai(赖大荣), Xin Shu(舒欣), Christine Nardini

1 School of Computer Science and Engineering, Southeast University, Nanjing 211189, China;
2 Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 210096, China;
3 College of Information Science and Technology, Nanjing Agricultural University, Nanjing 210095, China;
4 CNR-IAC "Mauro Picone" Via dei Taurini 19, 00185 Roma, Italy;
5 Personalgenomics, Via delle Grazie, Verona, Italy

收稿日期:2016-08-26 修回日期:2016-11-25 出版日期:2017-03-05 发布日期:2017-03-05
通讯作者: Darong Lai E-mail:darong.lai@gmail.com
基金资助:
Project supported by the National Natural Science Foundation of China (Grants No. 61202262), the Natural Science Foundation of Jiangsu Province, China (Grants No. BK2012328), and the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grants No. 20120092120034).

Link prediction in complex networks via modularity-based belief propagation

Darong Lai(赖大荣)^1,2, Xin Shu(舒欣)³, Christine Nardini^4,5

1 School of Computer Science and Engineering, Southeast University, Nanjing 211189, China;
2 Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 210096, China;
3 College of Information Science and Technology, Nanjing Agricultural University, Nanjing 210095, China;
4 CNR-IAC "Mauro Picone" Via dei Taurini 19, 00185 Roma, Italy;
5 Personalgenomics, Via delle Grazie, Verona, Italy

Received:2016-08-26 Revised:2016-11-25 Online:2017-03-05 Published:2017-03-05
Contact: Darong Lai E-mail:darong.lai@gmail.com
Supported by:
Project supported by the National Natural Science Foundation of China (Grants No. 61202262), the Natural Science Foundation of Jiangsu Province, China (Grants No. BK2012328), and the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grants No. 20120092120034).

摘要/Abstract

摘要： 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 recovers 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.

关键词: link prediction, complex network, belief propagation, modularity

Abstract: 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 recovers 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.

Key words: link prediction, complex network, belief propagation, modularity

中图分类号: (Networks and genealogical trees)

89.75.Hc

02.50.Tt (Inference methods) 89.20.Ff (Computer science and technology)

赖大荣, 舒欣. Link prediction in complex networks via modularity-based belief propagation[J]. 中国物理B, 2017, 26(3): 38902-038902.

Darong Lai(赖大荣), Xin Shu(舒欣), Christine Nardini. Link prediction in complex networks via modularity-based belief propagation[J]. Chin. Phys. B, 2017, 26(3): 38902-038902.

参考文献 46

[1]	Newman M E J 2010 Networks: An Introduction, 1st edn. (Oxford: Oxford University Press) p. 1
[2]	Ren T, Wang Y F, Liu M M and Xu Y J 2016 Chin. Phys. B 25 020101
[3]	Boccaletti S, Latora V, Moreno Y, Chavez M and Hwang D U 2006 Phys. Rep. 424 175
[4]	Ruan Y R, Lao S Y, Xiao Y D, Wang J D and Bai L 2016 Chin. Phys. Lett. 33 028901
[5]	Duan J M, Shang M S, Cai S M and Zhang Y X 2015 Acta Phys. Sin. 64 200501 (in Chinese)
[6]	Xu X L, Liu C P and He D R 2016 Chin. Phys. Lett. 33 048901
[7]	Yu H, Braun P, Yildirim M A et al. 2008 Science 322 104
[8]	Stumpf M P H, Thorne T, de Silva E, Stewart R, An H J, Lappe M and Wiuf C 2008 Proc. Natl. Acad. Sci. USA 105 6959
[9]	Amaral L A N 2008 Proc. Natl. Acad. Sci. USA 105 6795
[10]	Butts C 2003 Soc. Netw. 25 103
[11]	Kossinets G 2006 Soc. Netw. 28 247
[12]	Schifanella R, Barrat A, Cattuto C, Markines B and Menczer F 2010 Proceedings of the Third ACM International Conference on Web Search and Data Mining, February 3-6, 2010, New York, USA, p. 271
[13]	Fouss F, Pirotte A, Renders J M and Saerens M 2007 IEEE T. Knowl. Data En. 19 355
[14]	Lü L and Zhou T 2011 Physica A 390 1150
[15]	Newman M E J 2001 Phys. Rev. E 64 025102
[16]	Adamic L A and Adar E 2003 Soc. Netw. 25 211
[17]	Zhou T, Lü L and Zhang Y C 2009 Eur. Phys. J. B 71 623
[18]	Clauset A, Moore C and Newman M E J 2008 Nature 453 98
[19]	Guimera R and Sales-Pardo M 2009 Proc. Natl. Acad. Sci. USA 106 22073
[20]	Pan L, Zhou T, Lü L and Hu C K 2016 Sci. Rep. 6 22955
[21]	Taskar B, Wong M F, Abbeel P and Koller D 2004 Proceedings of Neural Information Processing Systems, December 8-13, 2003, Vancouver and Whistler, British Columbia, Canada, p. 659
[22]	Yu K, Chu W, Yu S, Tresp V and Xu Z 2007 Proceedings of Neural Information Processing Systems, December 4-7, 2006, Vancouver, British Columbia, Canada, p. 1657
[23]	Li Y J, Yin C, Yu H and Liu Z 2016 Acta Phys. Sin. 65 200501 (in Chinese)
[24]	Katz L 1953 Psychmetrika 18 39
[25]	Salton G and McGill M J 1983 Introduction to Modern Information Retrieval (Auckland: McGraw-Hill) p. 1
[26]	Xie Y B, Zhou T and Wang B H 2008 Physica A 387 1683
[27]	Lü L, Jin C and Zhou T 2009 Phys. Rev. E 83 046122
[28]	Wang W Q, Zhang Q M and Zhou T 2012 Europhys. Lett. 98 28004
[29]	Zhang Q M, Xu X K, Zhu Y X and Zhou T 2015 Sci. Rep. 5 10350
[30]	Zhang Q M, Lü L, Wang W Q and Zhou T 2013 PloS One 8 e55437
[31]	Lü L, Pan L, Zhou T and Zhang Y C 2015 Proc. Natl. Acad. Sci. USA 112 2345
[32]	Girvan M and Newman M E J 2002 Proc. Natl Acad. Sci. USA 99 7821
[33]	Shen Y, Ren G, Liu Y and Xu J L 2016 Chin. Phys. B 25 068901
[34]	Nowicki K and Snijders T A B 2001 J. Am. Stat. Assoc. 96 1077
[35]	Karrer B and Newman M E J 2011 Phys. Rev. E 83 016107
[36]	Zhang P and Moore C 2014 Proc. Natl. Acad. Sci. USA 111 18144
[37]	Hanely J A and McNeil B J 1982 Radiology 143 29
[38]	Karrer B and Newman M E J 2011 Phys. Rev. E 83 016107
[39]	Lai D, Shu X and Nardini C 2016 J. Stat. Mech. P053301
[40]	Zachary W W 1977 J. Anthropol. Res. 33 452
[41]	Adamic L A and Glance N 2005 Proceedings of the 3rd International Workshop on Link Discovery, August 21-24, 2005, Chicago, USA, p. 36
[42]	Lusseau D, Schneider K, Boisseau O J, Haase P, Slooten E and Dawson S M 2003 Behav. Ecol. Sociobiol. 54 396
[43]	Ulanowicz R E, Bondavalli C and Egnotovich M S 1998 Technical Report Ref. No. [UMCES] CBL 98-123
[44]	Sun S, Ling L, Zhang N, Li G and Chen R 2003 Nucleic Acids Res. 31 2443
[45]	Danon L, Diaz-Guilera A, Duch J and Arenas A 2005 J. Stat. Mech. P09008
[46]	Fortunato S 2010 Phys. Rep. 486 75

Link prediction in complex networks via modularity-based belief propagation

Link prediction in complex networks via modularity-based belief propagation

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 46

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Jie Zhou(周洁), Cheng Yuan(袁诚), Zu-Yu Qian(钱祖燏), Bing-Hong Wang(汪秉宏), and Sen Nie(聂森). Analysis of cut vertex in the control of complex networks[J]. 中国物理B, 2023, 32(2): 28902-028902.
[2]	Pengli Lu(卢鹏丽) and Wei Chen(陈玮). Vertex centrality of complex networks based on joint nonnegative matrix factorization and graph embedding[J]. 中国物理B, 2023, 32(1): 18903-018903.
[3]	Chaoyi Shi(史朝义), Qi Zhang(张琦), and Tianguang Chu(楚天广). Effect of observation time on source identification of diffusion in complex networks[J]. 中国物理B, 2022, 31(7): 70203-070203.
[4]	Jing-Cheng Zhu(朱敬成) and Lun-Wen Wang(王伦文). An extended improved global structure model for influential node identification in complex networks[J]. 中国物理B, 2022, 31(6): 68904-068904.
[5]	Ai-Xia Feng(冯爱霞), Qi-Guang Wang(王启光), Shi-Xuan Zhang(张世轩), Takeshi Enomoto(榎本刚), Zhi-Qiang Gong(龚志强), Ying-Ying Hu(胡莹莹), and Guo-Lin Feng(封国林). Characteristics of vapor based on complex networks in China[J]. 中国物理B, 2022, 31(4): 49201-049201.
[6]	Yahan Deng(邓雅瀚), Zhongkai Mo(莫中凯), and Hongqian Lu(陆宏谦). Robust H_∞ state estimation for a class of complex networks with dynamic event-triggered scheme against hybrid attacks[J]. 中国物理B, 2022, 31(2): 20503-020503.
[7]	Atiyeh Bayani, Sajad Jafari, and Hamed Azarnoush. Explosive synchronization: From synthetic to real-world networks[J]. 中国物理B, 2022, 31(2): 20504-020504.
[8]	Hongwei Zhang(张红伟), Ran Cheng(程然), and Dawei Ding(丁大为). Finite-time synchronization of uncertain fractional-order multi-weighted complex networks with external disturbances via adaptive quantized control[J]. 中国物理B, 2022, 31(10): 100504-100504.
[9]	Dong-Jie Qian(钱冬杰). Explosive synchronization in a mobile network in the presence of a positive feedback mechanism[J]. 中国物理B, 2022, 31(1): 10503-010503.
[10]	Dan-Dan Yan(颜丹丹), Xing-Kui Fan(范兴奎), Zhen-Yu Chen(陈祯羽), and Hong-Yang Ma(马鸿洋). Low-loss belief propagation decoder with Tanner graph in quantum error-correction codes[J]. 中国物理B, 2022, 31(1): 10304-010304.
[11]	Gui-Qiong Xu(徐桂琼), Lei Meng(孟蕾), Deng-Qin Tu(涂登琴), and Ping-Le Yang(杨平乐). LCH: A local clustering H-index centrality measure for identifying and ranking influential nodes in complex networks[J]. 中国物理B, 2021, 30(8): 88901-088901.
[12]	Tong-Feng Weng(翁同峰), Xin-Xin Cao(曹欣欣), and Hui-Jie Yang(杨会杰). Complex network perspective on modelling chaotic systems via machine learning[J]. 中国物理B, 2021, 30(6): 60506-060506.
[13]	Zi-Wei Yuan(袁紫薇), Chang-Chun Lv(吕长春), Shu-Bin Si(司书宾), and Dong-Li Duan(段东立). Dynamical robustness of networks based on betweenness against multi-node attack[J]. 中国物理B, 2021, 30(5): 50501-050501.
[14]	胡辑伟, 高松, 严俊伟, 娄平, 尹勇. Manufacturing enterprise collaboration network: An empirical research and evolutionary model[J]. 中国物理B, 2020, 29(8): 88901-088901.
[15]	杨远志, 胡敏, 黄泰愚. Influential nodes identification in complex networks based on global and local information[J]. 中国物理B, 2020, 29(8): 88903-088903.