The link prediction problem for social networks

ABSTRACT

Given a snapshot of a social network, can we infer which new interactions among its members are likely to occur in the near future? We formalize this question as the link prediction problem, and develop approaches to link prediction based on measures the "proximity" of nodes in a network. Experiments on large co-authorship networks suggest that information about future interactions can be extracted from network topology alone, and that fairly subtle measures for detecting node proximity can outperform more direct measures.

REFERENCES

• 1: L. Adamic, E. Adar. Friends and neighbors on the web. Soc. Networks, 25(3), 2003.
• 2: A. Barabasi, H. Jeong, Z. Néda, E. Ravasz, A. Schubert, T. Vicsek. Evolution of the social network of scientific collaboration. Physica A, 311(3--4), 2002.
• 3: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 4: S. Deerwester, S. Dumais, G. Furnas, T. Landauer, R. Harshman. Indexing by latent semantic analysis. J. Am. Soc. Inform. Sci., 41(6), 1990.
• 5: Glen Jeh , Jennifer Widom, SimRank: a measure of structural-context similarity, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775126]
• 6: E. Jin, M. Girvan, M. Newman. The structure of growing social networks. Phys. Rev. E, 64(046132), 2001.
• 7: L. Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1), March 1953.
• 8: Henry Kautz , Bart Selman , Mehul Shah, Referral Web: combining social networks and collaborative filtering, Communications of the ACM, v.40 n.3, p.63-65, March 1997 [doi>10.1145/245108.245123]
• 9: Lillian Lee, Measures of distributional similarity, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.25-32, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034693]
• 10: M. Newman. Clustering and preferential attachment in growing networks. Phys. Rev. E , 64(025102), 2001.
• 11: M. Newman. The structure and function of complex networks. SIAM Review 45:167-256, 2003.
• 12: Christopher R. Palmer , Phillip B. Gibbons , Christos Faloutsos, ANF: a fast and scalable tool for data mining in massive graphs, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775059]
• 13: A. Popescul, L. Ungar. Statistical Relational Learning for Link Prediction. Workshop on Learning Statistical Models from Relational Data, IJCAI 2003.
• 14: Prabhakar Raghavan, Social Networks: From the Web to the Enterprise, IEEE Internet Computing, v.6 n.1, p.91-94, January 2002 [doi>10.1109/4236.989007]
• 15: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Sociology

General Terms:
Algorithms

Keywords:
link analysis, link prediction, social networks