Synonyms
Definition
Many datasets can naturally be represented as graph where nodes represent instances and links represent relationships between those instances. A fundamental problem with these types of data is that the link information in the graph maybe of dubious quality; links may incorrectly exist between unrelated nodes and links may be missing between two related nodes. The goal of link prediction is to predict the existence of incorrect or missing links between the nodes of the graph.
Theory/Solution
Inferring the existences of edges between nodes in a graph has traditionally been referred to as link prediction (Liben-Nowell & Kleinberg, 2003; Taskar, Wong, Abbeel, & Koller, 2003). Link prediction is a challenging problem that has been studied in various guises in different domains. For example, in social network analysis, there is work on predicting friendship links ( Zheleva, Getoor, Golbeck, & Kuter, 2008), event participation...
This is a preview of subscription content, log in via an institution to check access.
Recommended Reading
Albert, R., DasGupta, B., Dondi, R., Kachalo, S., Sontag, E., Zelikovsky, A., et al. (2007). A novel method for signal transduction network inference from indirect experimental evidence. Journal of Computational Biology, 14, 407–419.
Balasubramanyan, R., Carvalho, V. R., & Cohen, W. (2009). Cutonce recipient recommendation and leak detection in action. In Workshop on enhanced messaging.
Carvalho, V. R., & Cohen, W. W. (2007). Preventing information leaks in email. In SIAM conference on data mining.
Chaiwanarom, P., & Lursinsap, C. (2008). Link completion using prediction by partial matching. In International symposium on communications and information technologies.
Clauset, A., Moore, C., & Newman, M. E. J. (2008). Hierarchical structure and the prediction of missing links in networks. Nature, 453, 98.
Deng, M., Mehta, S., Sun, F., & Chen, T. (2002). Inferring domain-domain interactions from protein-protein interactions. Genome Research, 12(10), 1540–1548.
Diehl, C., Namata, G. M., & Getoor, L. (2007). Relationship identification for social network discovery. In Proceedings of the 22nd national conference on artificial intelligence.
Farrell, S., Campbell, C., & Myagmar, S. (2005). Relescope: An experiment in accelerating relationships. In Extended abstracts on human factors in computing systems.
Getoor, L., Friedman, N., Koller, D., & Taskar, B. (2003). Learning probabilistic models of link structure. Machine Learning, 3, 679–707.
Goldenberg, A., Kubica, J., Komarek, P., Moore, A., & Schneider, J. (2003). A comparison of statistical and machine learning algorithms on the task of link completion. In Conference on knowledge discovery and data mining, Workshop on link analysis for detecting complex behavior.
Huang, Z., & Lin, D. K. J. (2008). The time-series link prediction problem with applications in communication surveillance. Informs Journal on Computing, 21, 286–303.
Huang, Z., & Zeng, D. D. (2006). A link prediction approach to anomalous email detection. In IEEE International conference on systems, man, and cybernetics, Taipei, Taiwan.
Liben-Nowell, D., & Kleinberg, J. (2003). The link prediction problem for social networks. In International conference on information and knowledge management.
Milne, D., & Witten, I. H. (2008). Learning to link with wikipedia. In Proceedings of the 17th ACM conference on information and knowledge management.
O’Madadhain, J., Hutchins, J., & Smyth, P. (2005). Prediction and ranking algorithms for event-based network data. SIGKDD Explorations Newsletter, 7(2), 23–30.
Popescul, A., & Ungar, L. H. (2003). Statistical relational learning for link prediction. In International joint conferences on artificial intelligence workshop on learning statistical models from relational data.
Rattigan, M. J., & Jensen, D. (2005). The case for anomalous link discovery. SIGKDD Explorations Newsletter, 7, 41–47.
Richardson, M., & Domingos, P. (2006). Markov logic networks. Machine Learning, 62, 107–136.
Spring, N., Wetherall, D., & Anderson, T. (2004). Reverse engineering the internet. SIGCOMM Computer Communication Review, 34(1), 3–8.
Sprinzak, E., Altuvia, Y., & Margalit, H. (2006). Characterization and prediction of protein-protein interactions within and between complexes. Proceedings of the National Academy of Sciences, 103(40), 14718–14723.
Szilagyi, A., Grimm, V., Arakaki, A. K., & Skolnick, J. (2005). Prediction of physical protein-protein interactions. Physical Biology, 2(2), S1–S16.
Taskar, B., Wong, M.-F., Abbeel, P., & Koller, D. (2003). Link prediction in relational data. In Advances in neural information processing systems.
Yu, H., Paccanaro, A., Trifonov, V., & Gerstein, M. (2006). Predicting interactions in protein networks by completing defective cliques. Bioinformatics, 22(7), 823–829.
Zheleva, E., Getoor, L., Golbeck, J., & Kuter, U. (2008). Using friendship ties and family circles for link prediction. In 2nd ACM SIGKDD workshop on social network mining and analysis.
Zhu, J. (2003). Mining web site link structure for adaptive web site navigation and search. Ph.D. thesis, University of Ulster at Jordanstown, UK.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer Science+Business Media, LLC
About this entry
Cite this entry
Namata, G., Getoor, L. (2011). Link Prediction. In: Sammut, C., Webb, G.I. (eds) Encyclopedia of Machine Learning. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-30164-8_481
Download citation
DOI: https://doi.org/10.1007/978-0-387-30164-8_481
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-30768-8
Online ISBN: 978-0-387-30164-8
eBook Packages: Computer ScienceReference Module Computer Science and Engineering