Entropy-based link prediction in weighted networks

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

中国物理B ›› 2017, Vol. 26 ›› Issue (1): 18902-018902.doi: 10.1088/1674-1056/26/1/018902

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

Entropy-based link prediction in weighted networks

Zhongqi Xu(许忠奇), Cunlai Pu(濮存来), Rajput Ramiz Sharafat, Lunbo Li(李伦波), Jian Yang(杨健)

1. Department of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China;
2. Department of Industrial and Systems Engineering, University of Florida, Gainesville 32611, USA

收稿日期:2016-07-18 修回日期:2016-10-25 出版日期:2017-01-05 发布日期:2017-01-05
通讯作者: Cunlai Pu E-mail:pucunlai@njust.edu.cn
基金资助:
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).

Entropy-based link prediction in weighted networks

Zhongqi Xu(许忠奇)¹, Cunlai Pu(濮存来)^1,2, Rajput Ramiz Sharafat¹, Lunbo Li(李伦波)¹, Jian Yang(杨健)¹

1. Department of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China;
2. Department of Industrial and Systems Engineering, University of Florida, Gainesville 32611, USA

Received:2016-07-18 Revised:2016-10-25 Online:2017-01-05 Published:2017-01-05
Contact: Cunlai Pu E-mail:pucunlai@njust.edu.cn
Supported by:
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).

摘要/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.

关键词: link prediction, weighted networks, information entropy

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.

Key words: link prediction, weighted networks, information entropy

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

89.75.Hc

89.75.Fb (Structures and organization in complex systems) 89.20.Hh (World Wide Web, Internet)

许忠奇, 濮存来, Rajput Ramiz Sharafat, 李伦波, 杨健. Entropy-based link prediction in weighted networks[J]. 中国物理B, 2017, 26(1): 18902-018902.

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

参考文献 48

[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

Entropy-based link prediction in weighted networks

Entropy-based link prediction in weighted networks

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 48

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	赖大荣, 舒欣. Link prediction in complex networks via modularity-based belief propagation[J]. 中国物理B, 2017, 26(3): 38902-038902.
[2]	宋旭东, 董世海, 张宇. Quantum information entropy for one-dimensional system undergoing quantum phase transition[J]. 中国物理B, 2016, 25(5): 50302-050302.
[3]	杨瑜, 王秉中, 丁帅. Shannon information capacity of time reversal wideband multiple-input multiple-output system based on correlated statistical channels[J]. 中国物理B, 2016, 25(5): 50101-050101.
[4]	Sun Guo-Hua, Dušan Popov, Oscar Camacho-Nieto, Dong Shi-Hai. Shannon information entropies for position-dependent mass Schrödinger problem with a hyperbolic well[J]. 中国物理B, 2015, 24(10): 100303-100303.
[5]	Guo-Hua Sun, M. Avila Aoki, Shi-Hai Dong. Quantum information entropies of the eigenstates for the Pöschl-Teller-like potential[J]. 中国物理B, 2013, 22(5): 50302-050302.
[6]	郭永峰, 谭建国. Time evolution of information entropy for a stochastic system with double singularities driven by quasimonochromatic noise[J]. Chin. Phys. B, 2012, 21(12): 120501-120501.
[7]	白萌, 胡柯, 唐翌. Link prediction based on a semi-local similarity index[J]. 中国物理B, 2011, 20(12): 128902-128902.
[8]	张敏敏, 王参军, 梅冬成. Effect of time delay on the upper bound of the time derivative of information entropy in a stochastic dynamical system[J]. 中国物理B, 2011, 20(11): 110501-110501.
[9]	张志森, 龚志强, 支蓉, 封国林, 胡经国. Preliminary research on the relationship between long-range correlations and predictability[J]. 中国物理B, 2011, 20(1): 19201-019201.
[10]	郭培荣, 徐伟, 刘迪. Upper bound for the time derivative of entropy for a stochastic dynamical system with double singularities driven by non-Gaussian noise[J]. 中国物理B, 2010, 19(3): 30520-030520.
[11]	徐琪欣, 许新建. Generating weighted community networks based on local events[J]. 中国物理B, 2009, 18(3): 933-938.
[12]	蒋继建, 李传安. Information entropy for static spherically symmetric black holes[J]. 中国物理B, 2009, 18(2): 451-456.
[13]	李克平, 高自友. Detecting and describing the modular structures of weighted networks[J]. 中国物理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[J]. 中国物理B, 2007, 16(1): 42-46.
[15]	肖方红, 郭少华, 胡元太. Evaluating the dynamical coupling between spatiotemporally chaotic signals via an information theory approach[J]. 中国物理B, 2006, 15(7): 1460-1463.