Graph Edge Prediction Algorithm

A Graph Edge Prediction Algorithm is a multi-class classification algorithm that can be implemented into a graph edge prediction system (to solve a graph edge prediction task).

• AKA: Link Prediction Algorithm.
• Context:
  • It can range from being a Heuristic Link Prediction Algorithm to being a Data-Driven Link Prediction Algorithm (such as a supervised link prediction algorithm).
• Example(s):
  • Social Network Link Prediction Algorithm.
  • Text Graph Link Prediction Algorithm.
  • a Taxonomy Mapping Algorithm.
  • ...
• Counter-Example(s):
  • Node Classification Algorithm.
• See: Markov Logic Network, Statistical Relational Learning.

References

2011

• (Lü & Zhou, 2011) ⇒ Linyuan Lü, and Tao Zhou. (2011). "Link Prediction in Complex Networks: A Survey." In: Physica A: Statistical Mechanics and its Applications, 390(6).
  • QUOTE: The algorithms can be used to extract missing information, identify spurious interactions, evaluate network evolving mechanisms, and so on. This article summaries recent progress about link prediction algorithms, emphasizing on the contributions from physical perspectives and approaches, such as the random-walk-based methods and the maximum likelihood methods. ... Finally, we introduce some applications and outline future challenges of link prediction algorithms.

2009

• (Miller et al., 2009) ⇒ Kurt T. Miller, Thomas L. Griffiths, and Michael I. Jordan. (2009). "Nonparametric Latent Feature Models for Link Prediction.." In: Advances in Neural Information Processing Systems 22 (NIPS 2009).

2006

• (Al Hasan et al., 2006) ⇒ Mohammad Al Hasan, Vineet Chaoji, Saeed Salem, and Mohammed Zaki. (2006). "Link Prediction Using Supervised Learning." In: SDM’06: Workshop on Link Analysis, Counter-terrorism and Security.
  • Link prediction in a social network is an important problem and it is very helpful in analyzing and understanding social groups.

2003

• (Liben-Nowell & Kleinberg. 2003) ⇒ David Liben-Nowell, and Jon Kleinberg. (2003). "The Link Prediction Problem for Social Networks." In: Proceedings of the twelfth International Conference on Information and knowledge management (CIKM 2003). doi:10.1145/956863.956972
• (Adamic & Adar, 2003) ⇒ Lada A. Adamic, and Eytan Adar. (2003). "Friends and Neighbors on the Web." In: Social Networks, 25(3). doi:10.1016/S0378-8733(03)00009-1
  • QUOTE: ... If we are trying to evaluate the likelihood that user A is linked to user B, we sum the number of items the two users have in common.
• (Taskar et al., 2003) ⇒ Ben Taskar, Ming-Fai Wong, Pieter Abbeel and Daphne Koller. (2003). "Link Prediction in Relational Data." In: Neural Information Processing Systems Conference (NIPS 2003)
  • QUOTE: We apply the relational Markov network framework of Taskar et al. to define a joint probabilistic model over the entire link graph — entity attributes and links.

• Concept