Chance-constrained programs for link prediction

In this paper, we consider the link prediction problem, where we are given a par-tial snapshot of a network at some time and the goal is to predict additional links
at a later time. The accuracy of the current prediction methods is quite low due
to the extreme class skew and the large number of potential links. In this paper,
we describe learning algorithms based on chance constrained programs and show
that they exhibit all the properties needed for a good link predictor, namely, al-
low preferential bias to positive or negative class; handle skewness in the data;
and scale to large networks. Our experimental results on three real-world co-
authorship networks show significant improvement in prediction accuracy over
baseline algorithms.