Uncovering missing links with cold ends
arXiv:1104.0395 · doi:10.1016/j.physa.2012.06.003
Abstract
To evaluate the performance of prediction of missing links, the known data are randomly divided into two parts, the training set and the probe set. We argue that this straightforward and standard method may lead to terrible bias, since in real biological and information networks, missing links are more likely to be links connecting low-degree nodes. We therefore study how to uncover missing links with low-degree nodes, namely links in the probe set are of lower degree products than a random sampling. Experimental analysis on ten local similarity indices and four disparate real networks reveals a surprising result that the Leicht-Holme-Newman index [E. A. Leicht, P. Holme, and M. E. J. Newman, Phys. Rev. E 73, 026120 (2006)] performs the best, although it was known to be one of the worst indices if the probe set is a random sampling of all links. We further propose an parameter-dependent index, which considerably improves the prediction accuracy. Finally, we show the relevance of the proposed index on three real sampling methods.
arXiv comment16 pages, 5 figures, 6 tables
References in corpus (23)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Community structure in social and biological networks
- Assortative mixing in networks
- Finding community structure in networks using the eigenvectors of matrices
- Random graphs with arbitrary degree distributions and their applications
- Evolution of networks
- Link Prediction in Complex Networks: A Survey
- Characterization of complex networks: A survey of measurements
- Predicting Missing Links via Local Information
- Efficient Immunization Strategies for Computer Networks and Populations
- Solving the apparent diversity-accuracy dilemma of recommender systems
- Vertex similarity in networks
- Missing and spurious interactions and the reconstruction of complex networks
- Effective and Efficient Similarity Index for Link Prediction of Complex Networks
- Efficient routing on complex networks
- Link Prediction Based on Local Random Walk
- Power-law Strength-Degree Correlation From a Resource-Allocation Dynamics on Weighted Networks
- Link prediction in complex networks: a local na\"ıve Bayes model
- Evaluating Network Models: A Likelihood Analysis
- Removing spurious interactions in complex networks
- Similarity-Based Classification in Partially Labeled Networks
Cited by in corpus (9)
- Link Prediction in Complex Networks: A Survey
- Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
- Progresses and Challenges in Link Prediction
- Network-based recommendation algorithms: A review
- Review on Learning and Extracting Graph Features for Link Prediction
- Improving personalized link prediction by hybrid diffusion
- Predicting the evolution of complex networks via local information
- Revisiting Neighborhood-based Link Prediction for Collaborative Filtering
- Predicting missing links via correlation between nodes