Link Prediction by a Node Pair Similarity Based Method with Unknown Number of Missing Links

This paper considers the problem of link prediction in networks with unknown number of missing links in a partial observation. We first estimate the number of missing links by solving an optimization problem, in which the objective function is to maximize the clustering coefficient of a network, subject to a Kullback-Leibler divergence constraint. Then based on this estimation, we propose an optimization approach to identify the potential missing links. The proposed approach uses both the node similarities and links in the observation and calculates the existence likelihood of missing links based on node pair similarities. Experiments in synthetic networks verify the effectiveness of our method.