Comparative Evaluation of Local and Quasi-Local Topological Methods for Link Prediction in Complex Networks

• Avelar Rodrigues de Sousa USP
• Maykon Willyam de Sousa Ferreira USP

DOI: https://doi.org/10.5753/kdmile.2026.31968

Resumo

Link prediction is a relevant task in complex networks, as it aims to estimate missing or future connections from the observed topology. This research presents an empirical comparison of 19 topological link prediction methods in eight real-world networks from different domains: social, scientific collaboration, communication, and electrical infrastructure. The evaluated methods include local similarity indices, degree-based approaches, enhanced local methods, a local Bayesian method, and quasi-local methods based on short paths and walks. The experimental protocol used five-fold cross-validation, preserving the connectivity of the training graphs and applying balanced negative sampling. The methods were mainly compared using Average Precision (AP), complemented by the area under the receiver operating characteristic curve (ROC-AUC), Precision, Recall, F1-score, and Normalized Discounted Cumulative Gain (NDCG). The results show that performance varies substantially across networks, with higher scores in networks with stronger local closure, such as ego-Facebook and scientific collaboration networks, and lower scores in the power-grid network. Among the evaluated methods, Superposed Random Walk with three steps (SRW-l3) achieved the best overall mean AP, followed by Local Path Index with β = 0.001 (LPI-beta-0.001) and Resource Allocation (RA) Based on Common Neighbor Interactions (RA-CNI). A statistical analysis (Friedman test followed by Wilcoxon signed-rank tests with Holm correction) indicated that SRW-l3 significantly outperformed PFP-l3 and RA-CNI, but its advantage over LPI-beta-0.001 was not statistically significant. Overall, the findings indicate that short paths and walks provide useful structural information for link prediction, while network properties such as average degree and clustering help explain task difficulty in an exploratory manner.

Palavras-chave: complex networks, graph mining, link prediction, topological similarity

Referências

Adamic, L. and Adar, E. Friends and neighbors on the web. Social Networks 25 (3): 211–230, 2003.

Aziz, F., Gul, H., Uddin, I., and Gkoutos, G. Path-based extensions of local link prediction methods for complex networks. Scientific Reports 10 (1): 19848, 2020.

Cannistraci, C., Alanis-Lobato, G., and Ravasi, T. From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks. Scientific Reports vol. 3, pp. 1613, 2013.

Feng, X., Zhao, J., and Xu, K. Link prediction in complex networks: A clustering perspective. The European Physical Journal B 85 (1): 3, 2012.

Ferreira, M. W., de Sousa, G., and Leal, J. Detecção de comunidades entre os membros da câmara dos deputados do brasil durante o período de 2019 a 2023: Uma abordagem utilizando redes complexas. In Anais do XLI Simpósio Brasileiro de Bancos de Dados. SBC, Porto Alegre, RS, Brasil, pp. 701–713, 2026.

Kapoor, P., Kaushal, S., Kumar, H., and Kanwar, K. A survey on feature extraction and learning techniques for link prediction in homogeneous and heterogeneous complex networks. Artificial Intelligence Review vol. 57, pp. 348, 2024.

Liben-Nowell, D. and Kleinberg, J. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology 58 (7): 1019–1031, 2007.

Liu, Z., Zhang, Q.-M., Lü, L., and Zhou, T. Link prediction in complex networks: A local naive bayes model. EPL 96 (4): 48007, 2011.

Lü, L., Jin, C.-H., and Zhou, T. Similarity index based on local paths for link prediction of complex networks. Physical Review E 80 (4): 046122, 2009.

Lü, L. and Zhou, T. Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and its Applications 390 (6): 1150–1170, 2011.

Martínez, V., Berzal, F., and Cubero, J.-C. A survey of link prediction in complex networks. ACM Computing Surveys 49 (4), 2016.

Newman, M. The structure and function of complex networks. SIAM Review 45 (2): 167–256, 2003.

Zhou, T., Lü, L., and Zhang, Y.-C. Predicting missing links via local information. The European Physical Journal B 71 (4): 623–630, 2009.