Bounded link prediction for very large networks
arXiv:1506.06516 · doi:10.1016/j.physa.2016.03.041
Abstract
Evaluation of link prediction methods is a hard task in very large complex networks because of the inhibitive computational cost. By setting a lower bound of the number of common neighbors (CN), we propose a new framework to efficiently and precisely evaluate the performances of CN-based similarity indices in link prediction for very large heterogeneous networks. Specifically, we propose a fast algorithm based on the parallel computing scheme to obtain all the node pairs with CN values larger than the lower bound. Furthermore, we propose a new measurement, called self-predictability, to quantify the performance of the CN-based similarity indices in link prediction, which on the other side can indicate the link predictability of a network.
arXiv comment9 figures
References in corpus (14)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- The structure and dynamics of multilayer networks
- Link Prediction in Complex Networks: A Survey
- Hierarchical structure and the prediction of missing links in networks
- Clustering and preferential attachment in growing networks
- Predicting Missing Links via Local Information
- Recommender Systems
- Vertex similarity in networks
- Quantifying Long-Term Scientific Impact
- Link Prediction Based on Local Random Walk
- Reputation and Impact in Academic Careers
- The Anatomy of a Scientific Rumor
- Message Passing for Optimization and Control of Power Grid: Model of Distribution System with Redundancy