Please wait a minute...
Chin. Phys. B, 2017, Vol. 26(3): 038902    DOI: 10.1088/1674-1056/26/3/038902

Link prediction in complex networks via modularity-based belief propagation

Darong Lai(赖大荣)1,2, Xin Shu(舒欣)3, Christine Nardini4,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
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.
Keywords:  link prediction      complex network      belief propagation      modularity  
Received:  26 August 2016      Revised:  25 November 2016      Published:  05 March 2017
PACS:  89.75.Hc (Networks and genealogical trees)  
  02.50.Tt (Inference methods)  
  89.20.Ff (Computer science and technology)  
Fund: 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).
Corresponding Authors:  Darong Lai     E-mail:

Cite this article: 

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

[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
[1] Improving robustness of complex networks by a new capacity allocation strategy
Jun Liu(刘军). Chin. Phys. B, 2021, 30(1): 016401.
[2] Manufacturing enterprise collaboration network: An empirical research and evolutionary model
Ji-Wei Hu(胡辑伟), Song Gao(高松), Jun-Wei Yan(严俊伟), Ping Lou(娄平), Yong Yin(尹勇). Chin. Phys. B, 2020, 29(8): 088901.
[3] Influential nodes identification in complex networks based on global and local information
Yuan-Zhi Yang(杨远志), Min Hu(胡敏), Tai-Yu Huang(黄泰愚). Chin. Phys. B, 2020, 29(8): 088903.
[4] Network correlation between investor's herding behavior and overconfidence behavior
Mao Zhang(张昴), Yi-Ming Wang(王一鸣). Chin. Phys. B, 2020, 29(4): 048901.
[5] Identifying influential spreaders in complex networks based on entropy weight method and gravity law
Xiao-Li Yan(闫小丽), Ya-Peng Cui(崔亚鹏), Shun-Jiang Ni(倪顺江). Chin. Phys. B, 2020, 29(4): 048902.
[6] Modeling and analysis of the ocean dynamic with Gaussian complex network
Xin Sun(孙鑫), Yongbo Yu(于勇波), Yuting Yang(杨玉婷), Junyu Dong(董军宇)†, Christian B\"ohm, and Xueen Chen(陈学恩). Chin. Phys. B, 2020, 29(10): 108901.
[7] Effect of degree correlation on edge controllability of real networks
Shu-Lin Liu(刘树林) and Shao-Peng Pang(庞少鹏)†. Chin. Phys. B, 2020, 29(10): 100202.
[8] Pyramid scheme model for consumption rebate frauds
Yong Shi(石勇), Bo Li(李博), Wen Long(龙文). Chin. Phys. B, 2019, 28(7): 078901.
[9] Exploring evolutionary features of directed weighted hazard network in the subway construction
Gong-Yu Hou(侯公羽), Cong Jin(靳聪), Zhe-Dong Xu(许哲东), Ping Yu(于萍), Yi-Yi Cao(曹怡怡). Chin. Phys. B, 2019, 28(3): 038901.
[10] Theoretical analyses of stock correlations affected by subprime crisis and total assets: Network properties and corresponding physical mechanisms
Shi-Zhao Zhu(朱世钊), Yu-Qing Wang(王玉青), Bing-Hong Wang(汪秉宏). Chin. Phys. B, 2019, 28(10): 108901.
[11] Coordinated chaos control of urban expressway based on synchronization of complex networks
Ming-bao Pang(庞明宝), Yu-man Huang(黄玉满). Chin. Phys. B, 2018, 27(11): 118902.
[12] Detecting overlapping communities based on vital nodes in complex networks
Xingyuan Wang(王兴元), Yu Wang(王宇), Xiaomeng Qin(秦小蒙), Rui Li(李睿), Justine Eustace. Chin. Phys. B, 2018, 27(10): 100504.
[13] Dominant phase-advanced driving analysis of self-sustained oscillations in biological networks
Zhi-gang Zheng(郑志刚), Yu Qian(钱郁). Chin. Phys. B, 2018, 27(1): 018901.
[14] Temperature dependence of heat conduction coefficient in nanotube/nanowire networks
Kezhao Xiong(熊科诏), Zonghua Liu(刘宗华). Chin. Phys. B, 2017, 26(9): 098904.
[15] Ranking important nodes in complex networks by simulated annealing
Yu Sun(孙昱), Pei-Yang Yao(姚佩阳), Lu-Jun Wan(万路军), Jian Shen(申健), Yun Zhong(钟赟). Chin. Phys. B, 2017, 26(2): 020201.
No Suggested Reading articles found!