Link prediction based on a semi-local similarity index

doi:10.1088/1674-1056/20/12/128902

Abstract Missing link prediction provides significant instruction for both analysis of network structure and mining of unknown links in incomplete networks. Recently, many algorithms have been proposed based on various node-similarity measures. Among these measures, the common neighbour index, the resource allocation index, and the local path index, stemming from different source, have been proved to have relatively high accuracy and low computational effort. In this paper, we propose a similarity index by combining the resource allocation index and the local path index. Simulation results on six unweighted networks show that the accuracy of the proposed index is higher than that of the local path one. Based on the same idea of the present index, we develop its corresponding weighted version and test it on several weighted networks. It is found that, except for the USAir network, the weighted variant also performs better than both the weighted resource allocation index and the weighted local path index. Due to the improved accuracy and the still low computational complexity, the indices may be useful for link prediction.

Keywords: link prediction resource allocation local path

Received: 21 April 2011
Revised: 20 July 2011
Accepted manuscript online:

PACS:	89.75.Fb	(Structures and organization in complex systems)
	89.75.Hc	(Networks and genealogical trees)
	89.20.Ff	(Computer science and technology)

Fund: Project supported by the National Natural Science Foundation of China (Grant No. 30570432), the Young Research Foundation of Education Department of Hunan Province of China (Grant No. 11B128), and partly by the Doctor Startup Project of Xiangtan University (Grant No. 10QDZ20).

Cite this article:

Bai Meng(白萌), Hu Ke(胡柯), and Tang Yi(唐翌) Link prediction based on a semi-local similarity index 2011 Chin. Phys. B 20 128902

[1]	Krebs V E 2001 textit Connections 24 43
[2]	Kautz H, Selman B and Shah M 1997 textit Commun. ACM 40 63
[3]	Chakrabarti S, Dom B E, Gibson D, Kleinerg J, Kumar R, Raghavan P, Rajagopalan S and Tomkins A 1999 textit IEEE Computer 32 60
[4]	Lü L and Zhou T 2011 textit Physica A 390 1150
[5]	Zhou T, Ren J, Medo M and Zhang Y C 2007 textit Phys. Rev. E 76 046115
[6]	Zhou T, Jiang L L, Su R Q and Zhang Y C 2008 textit Eur. Phys. J. B 81 58004
[7]	Zhang Y C, Medo M, Ren J, Zhou T, Li T and Yang F 2007 textit Eur. Phys. J. B 80 68003
[8]	Zhang Y C, Blattner M and Yu Y K 2007 Phys. Rev. Lett. 99 154301
[9]	Zhang Q M, Shang M S and Lü L 2010 Int. J. Mod. Phys. C 21 813
[10]	Leicht E A, Holme P and Newman M E J 2006 Phys. Rev. E 73 026120
[11]	Liben-Nowell D and Kleinberg J 2007 J. Am. Soc. Inf. Sci. Tec. 58 1019
[12]	Katz L 1953 Psychometrika 18 39
[13]	Göbel F and Jagers A 1974 Stoch. Processes Appl. 2 311
[14]	Fouss F, Pirotte A, Renders J M and Saerens M 2007 IEEE Trans. Knowl. Data Eng. 19 355
[15]	Brin S and Page L 1998 Comput. Netw. ISDN Syst. 30 107
[16]	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
[17]	Blondel V D, Gajardo A, Heymans M, Senellart P and Dooren P V 2004 SIAM Rev. 46 647
[18]	Lorrain F and White H C 1971 J. Math. Soc. 1 49
[19]	Salton G and McGill M J 1983 Introduction to Modern Information Retrieval (Auckland: MuGraw-Hill) pp. 201-215
[20]	Jaccard P 1901 Bulletin de la Societe Vaudoise des Sciences Naturelle 37 547
[21]	Supphirensen T 1948 Biol. Skr. 5 1
[22]	Ravasz E, Somera A L, Mongru D A, Oltvai Z N and Barab'asi 2002 Science 297 1553
[23]	Zhou T, Lü L and Zhang Y C 2009 Eur. Phys. J. B 71 623
[24]	Barab'asi A L and Albert R 1999 Science 286 509
[25]	Adamic L A and Adar E 2003 Social Networks 25 211 bibitem26 Ou Q, Jin Y D, Zhou T, Wang B H and Yin B Q 2007 Phys. Rev. E 75 021102 bibitem27 Sun D, Zhou T, Liu J G, Liu R R, Jia C X and Wang B H 2009 textit Phys. Rev. E 80 017101
[28]	Lü L, Jin C H and Zhou T 2009 textit Phys. Rev. E 80 046122
[29]	Liu W P and Lü L 2010 Europhys. Lett. 89 58007
[30]	Barrat A, Barthélemy, Pastor-Satorras R and Vespignani A 2004 Proc. Natl. Acad. Sci. 101 3747
[31]	Murata T and Moriyasu S 2007 ACM International Conference on Web Intelligence, Fremont, November 2-5, 2007 p. 85
[32]	Lü L and Zhou T 2010 Europhys. Lett. bf 89 18001
[33]	The data was released by Batagelj V and Mrvar A in 2006, available at http://vlado.fmf.uni-lj.si/pub/networks/data
[34]	Leskovec J, Kleinberg J and Faloutsos C 2005 Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, August 21-24, 2005 p. 177
[35]	Adamic L A and Glance N 2005 Proceedings of the 3rd International Workshop on Link Discovery, Chicago, August 21-24, 2005 p. 36
[36]	This snapshot was created by Newman M E J from data for July 22, 2006 and is not previously published
[37]	Watts D J and Strogatz S H 1998 Nature bf 393 440
[38]	Latora V and Marchiori M 2001 Phys. Rev. Lett. 87 198701
[39]	Newman M E J 2002 Phys. Rev. Lett. 89 208701
[40]	Hanely J A and Mcneil B J 1982 Radiology bf 143 29
[41]	Tian L, Di Z and Yao H 2011 Acta Phys. Sin. 60 028901 (in Chinese)

[1]	Modeling for heterogeneous multi-stage information propagation networks and maximizing information Ren-Jie Mei(梅人杰), Li Ding(丁李), Xu-Ming An(安栩明), Ping Hu(胡萍). Chin. Phys. B, 2019, 28(2): 028701.
[2]	Link prediction in complex networks via modularity-based belief propagation Darong Lai(赖大荣), Xin Shu(舒欣), Christine Nardini. Chin. Phys. B, 2017, 26(3): 038902.
[3]	Entropy-based link prediction in weighted networks Zhongqi Xu(许忠奇), Cunlai Pu(濮存来), Rajput Ramiz Sharafat, Lunbo Li(李伦波), Jian Yang(杨健). Chin. Phys. B, 2017, 26(1): 018902.
[4]	Traffic resource allocation for complex networks Ling Xiang (凌翔), Hu Mao-Bin (胡茂彬), Long Jian-Cheng (龙建成), Ding Jian-Xun (丁建勋), Shi Qin (石琴). Chin. Phys. B, 2013, 22(1): 018904.
[5]	Multi-user cognitive radio network resource allocation based on the adaptive niche immune genetic algorithm Zu Yun-Xiao(俎云霄) and Zhou Jie(周杰) . Chin. Phys. B, 2012, 21(1): 019501.
[6]	Cognitive radio resource allocation based on coupled chaotic genetic algorithm Zu Yun-Xiao(俎云霄),Zhou Jie(周杰), and Zeng Chang-Chang(曾昶畅). Chin. Phys. B, 2010, 19(11): 119501.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Link prediction based on a semi-local similarity index

Cite this article:

Online attention