A Supervised Link Prediction Method Using Optimized Vertex Collocation Profile

Abstract

Classical link prediction methods mainly utilize vertex information and topological structure to predict missing links in networks. However, accessing vertex information in real-world networks, such as social networks, is still challenging. Moreover, link prediction methods based on topological structure are usually heuristic, and mainly consider common neighbors, vertex degrees and paths, which cannot fully represent the topology context. In recent years, network embedding models have shown efficiency for link prediction, but they lack interpretability. To address these issues, this paper proposes a novel link prediction method based on an optimized vertex collocation profile (OVCP). First, the 7-subgraph topology was proposed to represent the topology context of vertexes. Second, any 7-subgraph can be converted into a unique address by OVCP, and then we obtained the interpretable feature vectors of vertexes. Third, the classification model with OVCP features was used to predict links, and the overlapping community detection algorithm was employed to divide a network into multiple small communities, which can greatly reduce the complexity of our method. Experimental results demonstrate that the proposed method can achieve a promising performance compared with traditional link prediction methods, and has better interpretability than network-embedding-based methods.

Keywords

• link prediction
• social network
• topological structure
• optimized vertex collocation profile
• community detection