Skip to main content
SpringerLink
Log in

Predicting missing links via local information

  • Topical issue on The Physics Approach to Risk: Agent-Based Models and Networks
  • Published:
The European Physical Journal B Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R. Albert, A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002)

    Article  ADS  Google Scholar 

  2. S.N. Dorogovtsev, J.F.F. Mendes, Adv. Phys. 51, 1079 (2002)

    Article  ADS  Google Scholar 

  3. M.E.J. Newman, SIAM Rev. 45, 167 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  4. S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.-U. Huang, Phys. Rep. 424, 175 (2006)

    Article  MathSciNet  ADS  Google Scholar 

  5. L.d.F. Costa, F.A. Rodrigues, G. Travieso, P.R.U. Boas, Adv. Phys. 56, 167 (2007)

    Article  ADS  Google Scholar 

  6. S. Redner, Nature 453, 47 (2008)

    Article  ADS  Google Scholar 

  7. N.D. Martinez, B.A. Hawkins, H.A. Dawah, B.P. Feifarek, Ecology 80, 1044 (1999)

    Google Scholar 

  8. E. Sprinzak, S. Sattath, H. Margalit, J. Mol. Biol. 327, 919 (2003)

    Article  Google Scholar 

  9. A. Grabowski, N. Kruszewska, R.A. Kosiński, Phys. Rev. E 78, 066110 (2008)

    Article  ADS  Google Scholar 

  10. H.-B. Hu, X.-F. Wang, Europhys. Lett. 86, 18003 (2009)

    Article  ADS  Google Scholar 

  11. 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)

    Google Scholar 

  12. M. Graven, D. DiPasquo, D. Freitag, A. McCallum, T. Mitchell, K. Nigam, S. Slattery, Artificial Intelligence 118, 69 (2000)

    Article  Google Scholar 

  13. 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

    Google Scholar 

  14. 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

    Google Scholar 

  15. 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)

    Google Scholar 

  16. D.S. Goldberg, F.P. Roth, Proc. Natl. Acad. Sci. U.S.A. 100, 4372 (2003)

    Article  MATH  MathSciNet  ADS  Google Scholar 

  17. D. Liben-Nowell, J. Kleinberg, J. Am. Soc. Inform. Sci. Technol. 58, 1019 (2007)

    Article  Google Scholar 

  18. A. Clauset, C. Moore, M.E.J. Newman, Nature 453, 98 (2008)

    Article  ADS  Google Scholar 

  19. D.J. Watts, S.H. Strogatz, Nature 393, 440 (1998)

    Article  ADS  Google Scholar 

  20. A.-L. Barabási, R. Albert, Science 286, 509 (1999)

    Article  MathSciNet  Google Scholar 

  21. M.E.J. Newman, Phys. Rev. Lett. 89, 208701 (2002)

    Article  ADS  Google Scholar 

  22. M. Girvan, M.E.J. Newman, Proc. Natl. Acad. Sci. U.S.A. 99, 7821 (2002)

    Article  MATH  MathSciNet  ADS  Google Scholar 

  23. T. Zhou, M. Zhao, G.-R. Chen, G. Yan, B.-H. Wang, Phys. Lett. A 368, 431 (2007)

    Article  ADS  Google Scholar 

  24. A. Arenas, A. Díaz-Guilera, C.J. Pérez-Vicente, Phys. Rev. Lett. 96, 114102 (2006)

    Article  ADS  Google Scholar 

  25. F. Gobel, A. Jagers, Stochastic Processes and Their Applications 2, 311 (1974)

    Article  MathSciNet  Google Scholar 

  26. P. Chebotarev, E. Shamis, Automation and Remote Control 58, 1505 (1997)

    MATH  MathSciNet  Google Scholar 

  27. J.A. Hanely, B.J. McNeil, Radiology 143, 29 (1982)

    Google Scholar 

  28. C. Von Merging, R. Krause, B. Snel, M. Cornell, S.G. Oliver, S. Fields, P. Bork, Nature 417, 399 (2002)

    Article  ADS  Google Scholar 

  29. M.E.J. Newman, Phys. Rev. E 74, 036104 (2006)

    Article  MathSciNet  ADS  Google Scholar 

  30. 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

  31. N. Spring, R. Mahajan, D. Wetherall, T. Anderson, IEEE/ACM Trans. Networking 12, 2 (2004)

    Article  Google Scholar 

  32. V. Batageli, A. Mrvar, Pajek Datasets, available at http://vlado.fmf.uni-lj.si/pub/networks/data/default.htm

  33. V. Latora, M. Marchiori, Phys. Rev. Lett. 87, 198701 (2001)

    Article  ADS  Google Scholar 

  34. S. Maslov, K. Sneppen, Science 296, 910 (2002)

    Article  ADS  Google Scholar 

  35. J. Schmith, N. Lemke, J.C.M. Mombach, P. Benelli, C.K. Barcellos, G.B. Bedin, Physica A 349, 675 (2005)

    Article  ADS  Google Scholar 

  36. 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)

    Article  MATH  ADS  Google Scholar 

  37. G. Salton, M.J. McGill, Introduction to Modern Information Retrieval (MuGraw-Hill, Auckland, 1983)

    MATH  Google Scholar 

  38. P. Jaccard, Bulletin de la Societe Vaudoise des Sciences Naturelles 37, 547 (1901)

    Google Scholar 

  39. T. Sørensen, Biol. Skr. 5, 1 (1948)

    Google Scholar 

  40. E. Ravasz, A.L. Somera, D.A. Mongru, Z.N. Oltvai, A.-L. Barabási, Science 297, 1553 (2002)

    Article  ADS  Google Scholar 

  41. E.A. Leicht, P. Holme, M.E.J. Newman, Phys. Rev. E 73, 026120 (2006)

    Article  ADS  Google Scholar 

  42. M. Molloy, B. Reed, Random Structure Algorithms 6, 161 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  43. Y.-B. Xie, T. Zhou, B.-H. Wang, Physica A 387, 1683 (2008)

    Article  ADS  Google Scholar 

  44. 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)

    Google Scholar 

  45. P. Holme, B.J. Kim, C.N. Yoon, S.K. Han, Phys. Rev. E 65, 056109 (2002)

    Article  ADS  Google Scholar 

  46. C.-Y. Yin, W.-X. Wang, G.-R. Chen, B.-H. Wang, Phys. Rev. E 74, 047102 (2006)

    Article  ADS  Google Scholar 

  47. G.-Q. Zhang, D. Wang, G.-J. Li, Phys. Rev. E 76, 017101 (2007)

    Article  ADS  Google Scholar 

  48. L.A. Adamic, E. Adar, Social Networks 25, 211 (2003)

    Article  Google Scholar 

  49. S. Zhou, R.J. Mondragón, New J. Phys. 9, 173 (2007)

    Article  ADS  Google Scholar 

  50. S. Zhou, R.J. Mondragón, IEEE Commun. Lett. 8, 180 (2004)

    Article  Google Scholar 

  51. V. Colizza, A. Flammini, M.A. Serrano, A. Vespignani, Nat. Phys. 2, 110 (2006)

    Article  Google Scholar 

  52. S.-H. Yook, A.-L. Barabási, H. Jeong, Proc. Natl. Acad. Sci. U.S.A. 99, 13382 (2002)

    Article  ADS  Google Scholar 

  53. E. Ravasz, A.-L. Barabási, Phys. Rev. E 67, 026112 (2003)

    Article  ADS  Google Scholar 

  54. H.-K. Liu, T. Zhou, Acta Physica Sinica 56, 106 (2007)

    Google Scholar 

  55. M.T. Gastner, M.E.J. Newman, Eur. Phys. J. B 49, 247 (2006)

    Article  ADS  Google Scholar 

  56. Q. Ou, Y.-D. Jin, T. Zhou, B.-H. Wang, B.-Q. Yin, Phys. Rev. E 75, 021102 (2007)

    Article  ADS  Google Scholar 

  57. W. Li, X. Cai, Phys. Rev. E 69, 046106 (2004)

    Article  ADS  Google Scholar 

  58. A. Barrat, M. Barthélemy, R. Pastor-Satorras, A. Vespignani, Proc. Natl. Acad. Sci. U.S.A. 101, 3747 (2004)

    Article  ADS  Google Scholar 

  59. T. Zhou, J. Ren, M. Medo, Y.-C. Zhang, Phys. Rev. E 76, 046115 (2007)

    Article  ADS  Google Scholar 

  60. T. Zhou, L.-L. Jiang, R.-Q. Su, Y.-C. Zhang, Europhys. Lett. 81, 58004 (2008)

    Article  ADS  Google Scholar 

  61. L. Lü, C.-H. Jin, T. Zhou, e-print arXiv: 0905.3558

  62. B. Tadić, S. Thurner, G.J. Rodgers, Phys. Rev. E 69, 036102 (2004)

    Article  ADS  Google Scholar 

  63. F. Fouss, A. Pirotte, J.-M. Renders, M. Saerens, IEEE Trans. Knowl. Data. Eng. 19, 355 (2007)

    Article  Google Scholar 

  64. L. Katz, Psychmetrika 18, 39 (1953)

    Article  MATH  Google Scholar 

  65. D. Sun, T. Zhou, R.-R. Liu, C.-X. Jia, J.-G. Liu, B.-H. Wang, Phys. Rev. E 80, 017101 (2009)

    Article  ADS  Google Scholar 

  66. S. Brin, L. Page, Computer Networks and ISDN Systems 30, 107 (1998)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Research Center for Complex System Science, University of Shanghai for Science and Technology, 200093, Shanghai, P.R. China

    Tao Zhou, Linyuan Lü & Yi-Cheng Zhang

  2. Department of Physics, University of Fribourg, Chemin du Musée 3, 1700, Fribourg, Switzerland

    Tao Zhou, Linyuan Lü & Yi-Cheng Zhang

  3. Department of Modern Physics, University of Science and Technology of China, 230026, Hefei Anhui, P.R. China

    Tao Zhou & Yi-Cheng Zhang

Authors
  1. Tao Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Linyuan Lü
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yi-Cheng Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tao Zhou.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1140/epjb/e2009-00335-8

PACS

Search

Navigation