Abstract
Missing link prediction in networks is of both theoretical interest and practical significance in modern science. In this paper, we empirically investigate a simple framework of link prediction on the basis of node similarity. We compare nine well-known local similarity measures on six real networks. The results indicate that the simplest measure, namely Common Neighbours, has the best overall performance, and the Adamic-Adar index performs second best. A new similarity measure, motivated by the resource allocation process taking place on networks, is proposed and shown to have higher prediction accuracy than common neighbours. It is found that many links are assigned the same scores if only the information of the nearest neighbours is used. We therefore design another new measure exploiting information on the next nearest neighbours, which can remarkably enhance the prediction accuracy.
Similar content being viewed by others
References
R. Albert, A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002)
S.N. Dorogovtsev, J.F.F. Mendes, Adv. Phys. 51, 1079 (2002)
M.E.J. Newman, SIAM Rev. 45, 167 (2003)
S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.-U. Huang, Phys. Rep. 424, 175 (2006)
L.d.F. Costa, F.A. Rodrigues, G. Travieso, P.R.U. Boas, Adv. Phys. 56, 167 (2007)
S. Redner, Nature 453, 47 (2008)
N.D. Martinez, B.A. Hawkins, H.A. Dawah, B.P. Feifarek, Ecology 80, 1044 (1999)
E. Sprinzak, S. Sattath, H. Margalit, J. Mol. Biol. 327, 919 (2003)
A. Grabowski, N. Kruszewska, R.A. Kosiński, Phys. Rev. E 78, 066110 (2008)
H.-B. Hu, X.-F. Wang, Europhys. Lett. 86, 18003 (2009)
L. Getoor, C.P. Diehl, Link Mining: A Survey, in Proceeding of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM Press, New York, 2005)
M. Graven, D. DiPasquo, D. Freitag, A. McCallum, T. Mitchell, K. Nigam, S. Slattery, Artificial Intelligence 118, 69 (2000)
A. Popescul, L. Ungar, Statistical relational larning for link prediction, in Workshop on Learning Statistical Models from Relational Data (ACM Press, New York, 2003), pp. 81–90
B. Taskar, M.-F. Wong, P. Abbeel, D. Koller, Link prediction in relational data, in Proceeding of Neural Information Processing Systems (MIT Press, Cambridge, 2003), pp. 659–666
J. O’Madadhain, J. Hutchins, P. Smyth, Prediction and ranking algorithms for even-based network data, In Proceeding of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM Press, New York, 2005)
D.S. Goldberg, F.P. Roth, Proc. Natl. Acad. Sci. U.S.A. 100, 4372 (2003)
D. Liben-Nowell, J. Kleinberg, J. Am. Soc. Inform. Sci. Technol. 58, 1019 (2007)
A. Clauset, C. Moore, M.E.J. Newman, Nature 453, 98 (2008)
D.J. Watts, S.H. Strogatz, Nature 393, 440 (1998)
A.-L. Barabási, R. Albert, Science 286, 509 (1999)
M.E.J. Newman, Phys. Rev. Lett. 89, 208701 (2002)
M. Girvan, M.E.J. Newman, Proc. Natl. Acad. Sci. U.S.A. 99, 7821 (2002)
T. Zhou, M. Zhao, G.-R. Chen, G. Yan, B.-H. Wang, Phys. Lett. A 368, 431 (2007)
A. Arenas, A. Díaz-Guilera, C.J. Pérez-Vicente, Phys. Rev. Lett. 96, 114102 (2006)
F. Gobel, A. Jagers, Stochastic Processes and Their Applications 2, 311 (1974)
P. Chebotarev, E. Shamis, Automation and Remote Control 58, 1505 (1997)
J.A. Hanely, B.J. McNeil, Radiology 143, 29 (1982)
C. Von Merging, R. Krause, B. Snel, M. Cornell, S.G. Oliver, S. Fields, P. Bork, Nature 417, 399 (2002)
M.E.J. Newman, Phys. Rev. E 74, 036104 (2006)
R. Ackland, Mapping the US political blogosphere: Are conservative bloggers more prominent, Presentation to BlogTalk Downunder (Sydney, 2005), available at http://incsub.org/blogtalk/images/robertackland.pdf
N. Spring, R. Mahajan, D. Wetherall, T. Anderson, IEEE/ACM Trans. Networking 12, 2 (2004)
V. Batageli, A. Mrvar, Pajek Datasets, available at http://vlado.fmf.uni-lj.si/pub/networks/data/default.htm
V. Latora, M. Marchiori, Phys. Rev. Lett. 87, 198701 (2001)
S. Maslov, K. Sneppen, Science 296, 910 (2002)
J. Schmith, N. Lemke, J.C.M. Mombach, P. Benelli, C.K. Barcellos, G.B. Bedin, Physica A 349, 675 (2005)
T. Zhou, B.-H. Wang, Y.-D. Jin, D.-R. He, P.-P. Zhang, Y. He, B.-B. Su, K. Chen, Z.-Z. Zhang, J.-G. Liu, Int. J. Mod. Phys. C 18, 297 (2007)
G. Salton, M.J. McGill, Introduction to Modern Information Retrieval (MuGraw-Hill, Auckland, 1983)
P. Jaccard, Bulletin de la Societe Vaudoise des Sciences Naturelles 37, 547 (1901)
T. Sørensen, Biol. Skr. 5, 1 (1948)
E. Ravasz, A.L. Somera, D.A. Mongru, Z.N. Oltvai, A.-L. Barabási, Science 297, 1553 (2002)
E.A. Leicht, P. Holme, M.E.J. Newman, Phys. Rev. E 73, 026120 (2006)
M. Molloy, B. Reed, Random Structure Algorithms 6, 161 (1995)
Y.-B. Xie, T. Zhou, B.-H. Wang, Physica A 387, 1683 (2008)
Z. Huang, X. Li, H. Chen, Link prediction approach to collaborative filtering, In Proceedings of the 5th ACM/IEEECS joint conference on Digital libraries (ACM Press, New York, 2005)
P. Holme, B.J. Kim, C.N. Yoon, S.K. Han, Phys. Rev. E 65, 056109 (2002)
C.-Y. Yin, W.-X. Wang, G.-R. Chen, B.-H. Wang, Phys. Rev. E 74, 047102 (2006)
G.-Q. Zhang, D. Wang, G.-J. Li, Phys. Rev. E 76, 017101 (2007)
L.A. Adamic, E. Adar, Social Networks 25, 211 (2003)
S. Zhou, R.J. Mondragón, New J. Phys. 9, 173 (2007)
S. Zhou, R.J. Mondragón, IEEE Commun. Lett. 8, 180 (2004)
V. Colizza, A. Flammini, M.A. Serrano, A. Vespignani, Nat. Phys. 2, 110 (2006)
S.-H. Yook, A.-L. Barabási, H. Jeong, Proc. Natl. Acad. Sci. U.S.A. 99, 13382 (2002)
E. Ravasz, A.-L. Barabási, Phys. Rev. E 67, 026112 (2003)
H.-K. Liu, T. Zhou, Acta Physica Sinica 56, 106 (2007)
M.T. Gastner, M.E.J. Newman, Eur. Phys. J. B 49, 247 (2006)
Q. Ou, Y.-D. Jin, T. Zhou, B.-H. Wang, B.-Q. Yin, Phys. Rev. E 75, 021102 (2007)
W. Li, X. Cai, Phys. Rev. E 69, 046106 (2004)
A. Barrat, M. Barthélemy, R. Pastor-Satorras, A. Vespignani, Proc. Natl. Acad. Sci. U.S.A. 101, 3747 (2004)
T. Zhou, J. Ren, M. Medo, Y.-C. Zhang, Phys. Rev. E 76, 046115 (2007)
T. Zhou, L.-L. Jiang, R.-Q. Su, Y.-C. Zhang, Europhys. Lett. 81, 58004 (2008)
L. Lü, C.-H. Jin, T. Zhou, e-print arXiv: 0905.3558
B. Tadić, S. Thurner, G.J. Rodgers, Phys. Rev. E 69, 036102 (2004)
F. Fouss, A. Pirotte, J.-M. Renders, M. Saerens, IEEE Trans. Knowl. Data. Eng. 19, 355 (2007)
L. Katz, Psychmetrika 18, 39 (1953)
D. Sun, T. Zhou, R.-R. Liu, C.-X. Jia, J.-G. Liu, B.-H. Wang, Phys. Rev. E 80, 017101 (2009)
S. Brin, L. Page, Computer Networks and ISDN Systems 30, 107 (1998)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhou, T., Lü, L. & Zhang, YC. Predicting missing links via local information. Eur. Phys. J. B 71, 623–630 (2009). https://doi.org/10.1140/epjb/e2009-00335-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1140/epjb/e2009-00335-8