Learning Algorithms for Link Prediction Based on Chance Constraints
Abstract
In this paper, we consider the link prediction problem, where we are given a partial snapshot of a network at some time and the goal is to predict the additional links formed at a later time. The accuracy of current prediction methods is quite low due to the extreme class skew and the large number of potential links. Here, we describe learning algorithms based on chance constrained programs and show that they exhibit all the properties needed for a good link predictor, namely, they allow preferential bias to positive or negative class; handle skewness in the data; and scale to large networks. Our experimental results on three real-world domains—co-authorship networks, biological networks and citation networks—show significant performance improvement over baseline algorithms. We conclude by briefly describing some promising future directions based on this work.
Cite
Text
Doppa et al. "Learning Algorithms for Link Prediction Based on Chance Constraints." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2010. doi:10.1007/978-3-642-15880-3_28Markdown
[Doppa et al. "Learning Algorithms for Link Prediction Based on Chance Constraints." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2010.](https://mlanthology.org/ecmlpkdd/2010/doppa2010ecmlpkdd-learning/) doi:10.1007/978-3-642-15880-3_28BibTeX
@inproceedings{doppa2010ecmlpkdd-learning,
title = {{Learning Algorithms for Link Prediction Based on Chance Constraints}},
author = {Doppa, Janardhan Rao and Yu, Jun and Tadepalli, Prasad and Getoor, Lise},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2010},
pages = {344-360},
doi = {10.1007/978-3-642-15880-3_28},
url = {https://mlanthology.org/ecmlpkdd/2010/doppa2010ecmlpkdd-learning/}
}