COMMON NEIGHBOUR: THE BACKBONE OF GRAPH-BASED LINK PREDICTION METHODS IN COMPLEX NETWORKS

Abstract

Link prediction in complex networks has emerged as a fundamental problem with applications spanning social network analysis, biological systems, recommendation systems, and collaborative filtering. Among the numerous similarity-based approaches proposed for link prediction, the Common Neighbour (CN) index stands as the most fundamental and widely adopted heuristic, serving as the backbone upon which many sophisticated methods have been built. This paper presents a comprehensive analysis of the Common Neighbour index and its role as the foundation for graph-based link prediction methods in complex networks. We examine the theoretical underpinnings of the CN index, its mathematical formulation, and its relationship to other similarity measures including Adamic-Adar, Resource Allocation, Jaccard Coefficient, and Preferential Attachment. The paper explores various extensions and enhancements of the CN index, including weighted variants, temporal adaptations, and integration with content-based features. Experimental results on multiple real-world networks demonstrate that while simple CN achieves AUROC 0.699, its enhanced variants and hybrid approaches incorporating CN with other features achieve significantly improved performance up to 0.878 AUROC. SHAP analysis reveals that CN-derived features contribute substantially (15-28%) to link prediction performance across diverse network types. The analysis confirms that despite its simplicity, the Common Neighbour index remains the cornerstone of graph-based link prediction, with its principles embedded in most state-of-the-art approaches. This comprehensive review serves as a valuable resource for researchers and practitioners working on network analysis and link prediction tasks.