A Comparative Study of Similarity and Embedding-Based Link Prediction for Backbone Extraction in Complex Networks
摘要
This study compares two link prediction-based backbone extraction frameworks: (1) a similarity-based method using the Local Path Index (LP) and (2) an embedding-based method using a Graph Autoencoder (GAE). Both methods assign scores to edges, extracting two types of backbones: resilient backbones (high-score edges) and adaptive backbones (low-score edges). A qualitative analysis on the Les Misérables network shows that resilient backbones emphasize dominant structures (e.g., major character relationships), while adaptive backbones retain weaker or less frequent connections. LP better preserves strong, localized connectivity, whereas GAE more effectively maintains global structures and weak ties. A quantitative evaluation across three datasets further demonstrates this distinction. For resilient backbones, LP better preserves reachability, transitivity, and weight distribution, reinforcing strong local connectivity and clustering. GAE, in contrast, more effectively retains node fraction and degree distribution, preserving the overall structural balance. For adaptive backbones, LP maintains node fraction, transitivity, and weight distribution, while GAE better preserves reachability and degree distribution, reducing fragmentation and integrating weakly connected nodes. These findings underscore the trade-off in each framework. The two methods provide complementary perspectives, making their selection dependent on the desired structural properties.