A Network Structural Approach to the Link Prediction Problem

The link prediction problem is an emerging real-life social network problem in which data mining techniques have played a critical role. It arises in many practical applications such as recommender systems, information retrieval, and marketing analysis of social networks. We propose a new mathematical programming approach for predicting a future network using estimated node degree distribution identified from historical data. The link prediction problem is formulated as an integer programming problem that maximizes the sum of link scores (probabilities) with respect to the estimated node degree distribution. The performance of the proposed framework is tested on real-life social networks, and the computational results show that the proposed approach can improve the performance of previously published link prediction methods.