Local degree blocking model for link prediction in complex networks

Abstract

Recovering and reconstructing networks by accurately identifying missing and unreliable links is a vital task in the domain of network analysis and mining. In this article, by studying a specific local structure, namely a degree block having a node and its all immediate neighbors, we find it contains important statistical features of link formation for complex networks. We therefore propose a parameter-free local blocking (LB) predictor to quantitatively detect link formation in given networks via local link density calculations. The promising experimental results performed on six real-world networks suggest that the new index can outperform other traditional local similarity-based methods on most of tested networks. After further analyzing the scores' correlations between LB and two other methods, we find that the features of LB index are analogous to those of both PA index and short-path-based index, which empirically verify that large degree principle and short path principle simultaneously captured by the LB index are jointly driving link formation in complex networks.

References in corpus (9)

• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Hierarchical structure and the prediction of missing links in networks
• Predicting Missing Links via Local Information
• What's in a crowd? Analysis of face-to-face behavioral networks
• Missing and spurious interactions and the reconstruction of complex networks
• Preferential attachment in the growth of social networks: the case of Wikipedia
• Preferential attachment in the protein network evolution
• Complex cooperative networks from evolutionary preferential attachment