Link Prediction on Directed Networks Based on AUC Optimization

Abstract

Complex networks have become high-dimensional, sparse, and redundant due to the rapid expansion of the Internet. Effective link prediction techniques are needed to obtain the most relevant and important information for Internet users. A new link prediction algorithm based on the area under the receiver operating characteristic curve (AUC) as the evaluation metric is proposed in this paper. In the proposed method, the AUC is treated as the objective function and the link prediction problem is transformed into an optimization problem. A group of topological features is defined for each ordered pair of nodes. By using those features as the attributes of the node pairs, link prediction can be treated as a binary classification, where the class label of each node pair is determined by the existence of a directed link between the node pair. Then, the binary classification problem can be solved by the AUC optimization. According to the empirical results, high-quality predictions can be achieved by our algorithm.