Entropy-based link prediction in weighted networks

doi:10.1088/1674-1056/26/1/018902

Abstract Information entropy has been proved to be an effective tool to quantify the structural importance of complex networks. In a previous work[Xu et al. Physica A, 456 294 (2016)], we measure the contribution of a path in link prediction with information entropy. In this paper, we further quantify the contribution of a path with both path entropy and path weight, and propose a weighted prediction index based on the contributions of paths, namely weighted path entropy (WPE), to improve the prediction accuracy in weighted networks. Empirical experiments on six weighted real-world networks show that WPE achieves higher prediction accuracy than three other typical weighted indices.

Keywords: link prediction weighted networks information entropy

Received: 18 July 2016
Revised: 25 October 2016
Accepted manuscript online:

PACS:	89.75.Hc	(Networks and genealogical trees)
	89.75.Fb	(Structures and organization in complex systems)
	89.20.Hh	(World Wide Web, Internet)

Fund: Project supported by the National Natural Science Foundation of China (Grant Nos. 61201173 and 61304154), the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20133219120032), the Postdoctoral Science Foundation of China (Grant No. 2013M541673), and China Postdoctoral Science Special Foundation (Grant No. 2015T80556).

Corresponding Authors: Cunlai Pu
E-mail: pucunlai@njust.edu.cn

Cite this article:

Zhongqi Xu(许忠奇), Cunlai Pu(濮存来), Rajput Ramiz Sharafat, Lunbo Li(李伦波), Jian Yang(杨健) Entropy-based link prediction in weighted networks 2017 Chin. Phys. B 26 018902

[1]	Barabási A L 2016 Network Science (Cambridge University Press)
[2]	Newman M 2010 Networks:An Introduction (Oxford University Press)
[3]	Chen G R, Wang X F and Li X 2012 Introduction to Complex Networks:Models, Structures and Dynamics (Higher Education Press)
[4]	Mayer-Schönberger V and Cukier K 2013 Big Data:A Revolution That Will Transform How We Live, Work, and Think (Houghton Mifflin Harcourt)
[5]	Abbasi A, Sarker S and Chiang R H 2016 J. Assoc. Inf. Syst. 17 3
[6]	Lü L Y and Zhou T 2011 Physica A 390 1150
[7]	Wang P, Xu B W, Wu Y R and Zhou X Y 2015 Sci. China-Inform. Sci. 58 1
[8]	Lü L Y, Medo M, Yeung C H, Zhang Y C, Zhang Z K and Zhou T 2012 Phys. Rep. 519 1
[9]	Cheng W L and Jian H R 2013 Bioinformatics 29 355
[10]	Sherkat E, Rahgozar M and Asadpour M 2015 Physica A 419 80
[11]	Newman M E J 2001 Proc. Natl. Acad. Sci. 98 404
[12]	Mohammad A H, Vineet C, Saeed S and Mohammad Z 2006 The Proceedings of the Fourth Workshop on Link Analysis, Counterterrorism and Security, April 22nd, 2006, Bethesda, USA
[13]	Sarukkai R R 2000 Comput. Netw. 33 377
[14]	Getoor L and Diehl C P 2005 ACM SIGKDD Explor. Newslett. 7 3
[15]	Cui W, Pu C L, Xu Z Q and Yang J 2016 Physica A 457 202
[16]	Li Y J, Yin C, Yu H and Liu Z 2016 Acta Phys. Sin. 65 020501(in Chinese)
[17]	Barabási A L and Albert R 1999 Science 286 509
[18]	Newman M E J 2001 Phys. Rev. E 64 025102
[19]	Kossinets G 2006 Soc. Netw. 28 247
[20]	Liben-Nowell D and Kleinberg J 2007 J. Am. Soc. Inf. Sci. Technol. 58 1019
[21]	Adamic L A and Adar E 2003 Soc. Netw. 25 211
[22]	Zhou T, Lü L Y and Zhang Y C 2009 Eur. Phys. J. B 71 623
[23]	Lü L Y, Jin C H and Zhou T 2009 Phys. Rev. E 80 046122
[24]	Liu W P and Lü L Y 2010 Europhys. Lett. 89 58007
[25]	Katz L 1953 Psychmetrika 18 39
[26]	Leicht E A, Holme P and Newman M E J 2006 Phys. Rev. E 73 026120
[27]	Jeh G and Widom J 2002 Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, USA, p. 538
[28]	Solé R V and Valverde S 2004 Information Theory of Complex Networks:On Evolution and Architectural Constraints, in Complex Networks (Springer) pp. 189-207
[29]	Halu A, Mukherjee S and Bianconi G 2014 Phys. Rev. E 89 012806
[30]	Anand K and Bianconi G 2009 Phys. Rev. E 80 045102
[31]	Tan F, Xia Y X and Zhu B Y 2014 PLoS ONE 9 e107056
[32]	Xu Z Q, Pu C L and Yang J 2016 Physica A 456 294
[33]	Zhu B Y and Xia Y X 2016 PLoS ONE 11 e0148265
[34]	Shen Y 2014 Physica A 393 560
[35]	Murata T and Moriyasu S 2007 IEEE/WIC/ACM International Conference on Web Intelligence p. 85
[36]	Bai M, Hu K and Tang Y 2011 Chin. Phys. B 20 128902
[37]	Lü L Y and Zhou T 2010 Europhys. Lett. 89 18001
[38]	Pu C L and Cui W 2015 Physica A 419 622
[39]	Pu C, Li S, Michaelson A and Yang J 2015 Phys. Lett. 379 1633
[40]	Feigenbaum J, Papadimitriou C, Sami R and Shenker S 2005 Distrib. Comput. 18 61
[41]	Shen Y, Ren G and Liu Y 2016 Physica A 452 229
[42]	Song H Q and Guo J 2015 Chin. Phys. B 24 108901
[43]	The data is released by Knuth D E in 1993, available at http://moreno.ss.uci.edu/data.html
[44]	The data is released by Batagelj V and Mrvar A in 2006, available at http://vlado.fmf.uni-lj.si/pub/networks/data
[45]	Brian H 2006 AmSci 94 400
[46]	The Koblenz Network Collection 2015, available at http://konect.uni-koblenz.de/
[47]	The data is released by Ulanowicz R E, Bondavalli C and Egnotovich M S in 1998, available at http://vlado.fmf.uni-lj.si/pub/networks/data/bio/foodweb/foodweb.htm
[48]	Watts D J and Strogatz S H 1998 Nature 393 440

[1]	Link prediction in complex networks via modularity-based belief propagation Darong Lai(赖大荣), Xin Shu(舒欣), Christine Nardini. Chin. Phys. B, 2017, 26(3): 038902.
[2]	Shannon information capacity of time reversal wideband multiple-input multiple-output system based on correlated statistical channels Yu Yang(杨瑜), Bing-Zhong Wang(王秉中), Shuai Ding(丁帅). Chin. Phys. B, 2016, 25(5): 050101.
[3]	Quantum information entropy for one-dimensional system undergoing quantum phase transition Xu-Dong Song(宋旭东), Shi-Hai Dong(董世海), Yu Zhang(张宇). Chin. Phys. B, 2016, 25(5): 050302.
[4]	Shannon information entropies for position-dependent mass Schrödinger problem with a hyperbolic well Sun Guo-Hua, Dušan Popov, Oscar Camacho-Nieto, Dong Shi-Hai. Chin. Phys. B, 2015, 24(10): 100303.
[5]	Quantum information entropies of the eigenstates for the Pöschl-Teller-like potential Guo-Hua Sun, M. Avila Aoki, Shi-Hai Dong. Chin. Phys. B, 2013, 22(5): 050302.
[6]	Time evolution of information entropy for a stochastic system with double singularities driven by quasimonochromatic noise Guo Yong-Feng (郭永峰), Tan Jian-Guo (谭建国). Chin. Phys. B, 2012, 21(12): 120501.
[7]	Link prediction based on a semi-local similarity index Bai Meng(白萌), Hu Ke(胡柯), and Tang Yi(唐翌) . Chin. Phys. B, 2011, 20(12): 128902.
[8]	Effect of time delay on the upper bound of the time derivative of information entropy in a stochastic dynamical system Zhang Min-Min(张敏敏), Wang Can-Jun(王参军), and Mei Dong-Cheng(梅冬成) . Chin. Phys. B, 2011, 20(11): 110501.
[9]	Preliminary research on the relationship between long-range correlations and predictability Zhang Zhi-Sen(张志森), Gong Zhi-Qiang(龚志强), Zhi Rong(支蓉), Feng Guo-Lin(封国林), and Hu Jing-Guo(胡经国). Chin. Phys. B, 2011, 20(1): 019201.
[10]	Upper bound for the time derivative of entropy for a stochastic dynamical system with double singularities driven by non-Gaussian noise Guo Pei-Rong(郭培荣), Xu Wei(徐伟), and Liu Di(刘迪). Chin. Phys. B, 2010, 19(3): 030520.
[11]	Generating weighted community networks based on local events Xu Qi-Xin(徐琪欣) and Xu Xin-Jian(许新建). Chin. Phys. B, 2009, 18(3): 933-938.
[12]	Information entropy for static spherically symmetric black holes Jiang Ji-Jian(蒋继建) and Li Chuan-An(李传安). Chin. Phys. B, 2009, 18(2): 451-456.
[13]	Detecting and describing the modular structures of weighted networks Li Ke-Ping(李克平) and Gao Zi-You(高自友). Chin. Phys. B, 2007, 16(8): 2304-2309.
[14]	Time dependence of entropy flux and entropy production for a dynamical system driven by noises with coloured cross-correlation Xie Wen-Xian(谢文贤), Xu Wei(徐伟), and Cai Li(蔡力). Chin. Phys. B, 2007, 16(1): 42-46.
[15]	Evaluating the dynamical coupling between spatiotemporally chaotic signals via an information theory approach Xiao Fang-Hong (肖方红), Guo Shao-Hua (郭少华), Hu Yuan-Tai (胡元太). Chin. Phys. B, 2006, 15(7): 1460-1463.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Entropy-based link prediction in weighted networks

Cite this article:

Online attention