Abstract
Link prediction refers to predicting the likelihood of the existence of an unknown link or a future link based on the observed information. It plays an important role in complex network analysis. Classical similarity indices based on common neighbor nodes consider that each common neighbor has the same effect to the link likelihood. However, in real networks, the contribution of common neighbor nodes belonging to different communities may be different. This paper proposes a new link prediction algorithm with an adjustable parameter based on community information (CI). Applying the proposed algorithm to nine similarity indices, a family of CI-based indices, referred to as CI forms, is proposed. We empirically investigate the impact of the CI on the accuracy of link prediction with nine classical indices. The experiments on ten real-world networks show that, compared with tradition local indices, the proposed CI forms have better overall prediction performance. Furthermore, a parallelization algorithm is developed to apply the proposed CI-based link prediction algorithm to large-scale complex networks using Spark GraphX. The experiment results show that the proposed parallel algorithm significantly improves the computing efficiency of link prediction.
Introduction
Link prediction is a cornerstone of network science, used for applications ranging from friend recommendations on social media to identifying protein interactions in biological systems. Most "local" prediction methods, such as counting common neighbors, treat every neighbor as equally important. However, real-world networks are rarely uniform; they are composed of clusters or "communities." This paper addresses the limitation of traditional methods by leveraging community structure to improve prediction accuracy and utilizing parallel computing to ensure scalability.
Community-Based Similarity Indices
The researchers proposed a novel approach that introduces an adjustable parameter, $\alpha$, to weigh the contribution of common neighbors based on their community membership.
In this model, if a common neighbor belongs to the same community as the two target nodes, it is classified as an "intra-community" neighbor. If it lies outside, it is an "inter-community" neighbor. The similarity score is calculated as:
$S_{x,y} = \alpha \cdot |Internal| + (1 - \alpha) \cdot |External|$
By prioritizing internal community information (typically with $\alpha$ between 0.6 and 0.9), the model achieves superior Area Under the Curve (AUC) and Precision scores compared to standard indices like Jaccard or Adamic-Adar.
Parallelization with Spark GraphX
To handle the computational demands of "big data" networks, the authors implemented a parallelized framework using Spark GraphX. This system utilizes a parallel version of the Louvain (BGLL) algorithm for community detection and a distributed message-passing approach for similarity calculations.
Using a "superstep" approach, the heavy matrix-like operations are distributed across a cluster. This allows the algorithm to process massive datasets, such as the Cit-Patents network (3.7 million nodes), which would be impossible to handle on a single machine using traditional methods.
Key Results and Insights
- Accuracy Boost: The CI-based versions of classical indices outperformed their standard counterparts across nearly all tested datasets. For example, on the Karate Club dataset, the CI-based Resource Allocation (RA-CI) index achieved an AUC of 0.9578.
- Efficiency: On large-scale networks, the parallel algorithm significantly improved computing efficiency. Using 32 processors, execution time was reduced by more than 50% compared to a single processor, completing tasks in minutes that previously took hours.
- The "Sweet Spot": While intra-community neighbors are stronger predictors, completely ignoring inter-community neighbors (setting $\alpha = 1$) often reduced performance, suggesting that "weak ties" between communities still provide essential context.
Conclusion
By integrating community information and parallel computing, this research provides a scalable and highly accurate method for link prediction in complex networks. Future work will focus on incorporating overlapping community detection and applying these methods to dynamic, evolving networks.
Summary updated