Link Prediction in Complex Networks: A Clustering Perspective

Abstract

Link prediction is an open problem in the complex network, which attracts much research interest currently. However, little attention has been paid to the relation between network structure and the performance of prediction methods. In order to fill this vital gap, we try to understand how the network structure affects the performance of link prediction methods in the view of clustering. Our experiments on both synthetic and real-world networks show that as the clustering grows, the precision of these methods could be improved remarkably, while for the sparse and weakly clustered network, they perform poorly. We explain this through the distinguishment caused by increased clustering between the score distribution of positive and negative instances. Our finding also sheds light on the problem of how to select appropriate approaches for different networks with various densities and clusterings.

7 pages, 3 figures

References in corpus (6)

• Finding community structure in networks using the eigenvectors of matrices
• Link Prediction in Complex Networks: A Survey
• Hierarchical structure and the prediction of missing links in networks
• Predicting Missing Links via Local Information
• Missing and spurious interactions and the reconstruction of complex networks
• Performance of networks of artificial neurons: The role of clustering

Cited by in corpus (4)

• Improving link prediction in complex networks by adaptively exploiting multiple structural features of networks
• The maximum capability of a topological feature in link prediction
• A nanomechanical resonator coupled linearly via its momentum to a quantum point contact
• Performance of Local Information Based Link Prediction: A Sampling Perspective