Weighted enclosing subgraph-based link prediction for complex network

Abstract

Abstract Link prediction is a fundamental research issue in complex network, which can reveal the potential relationships between users. Most of link prediction algorithms are heuristic and based on topology structure. Weisfeiler–Lehman Neural Machine (WLNM), regarded as a new-generation method, has shown promising performance and thus got attention in link prediction. WLNM extracts an enclosing subgraph of each target link and encodes the subgraph as an adjacency matrix. But it does not consider the relationship between other links of the enclosing subgraph and target links. Therefore, WLNM does not make full use of the topology information around the link, and the extracted enclosing subgraph can only partially represent the topological features around the target link. In this work, a novel approach is proposed, named weighted enclosing subgraph-based link prediction (WESLP). It incorporates the link weights in the enclosing subgraph to reflect their relationship with the target link, and the Katz index between nodes is used to measure the relationship between two links. The prediction models are trained by different classifiers based on these weighted enclosing subgraphs. Experiments show that our proposed method consistently performs well on different real-world datasets.

Keywords

• Weighted subgraph
• Graph coding
• Link prediction
• Complex network