Link Prediction Based on Enclosing Triadic Subgraphs
摘要
Link prediction is a fundamental task in the research of complex networks and has numerous applications in domains such as social networks, protein interaction networks, and transportation networks. However, existing studies suffer from poor generalization capabilities, leading to significant differences in prediction performance across datasets with distinct structural features. Moreover, the whole graph often contains redundant information that is unnecessary for the prediction task, leading to the decreased computational efficiency of the algorithms. To address the above challenges, we propose a generalized link prediction algorithm based on subgraph pattern mining, called Triadic Closure for Prediction (TCP). We introduce a novel concept, Enclosing Triadic Subgraphs of the target link, which aggregates triadic neighbors of link end nodes and transforms link prediction into a problem of extracting, labeling, embedding, and predicting these subgraphs. Our experimental results demonstrate that the Enclosing Triadic Subgraphs preserve enough information for link prediction, and the proposed algorithm achieves superior prediction performance and computational efficiency.