Quantifying the Effect of Community Structures for Link Prediction by Constructing Null Models

Abstract

The existing studies of link prediction mostly focused on using network topology properties to improve the accuracy of link prediction. More broadly, researches on the role of community structures for link prediction have recently received increasing attention. In this study, we propose a succinct algorithm that is built on community structures to improve the performance of link prediction, and it has been verified by both of synthetic benchmarks and real-world networks. More importantly, we introduce different null models to study the role of community structures on link prediction more carefully. Firstly, it is found that clearer community structures correspond to the higher performance of link prediction algorithms that are based on community information. Secondly, the role of links within a community and that between two communities are further distinguished. The edges within one community play a vital role for link prediction of the whole network, and conversely the edges between two communities have a minimal effect on that. At last, we reveal the relationship and dependence between this special meso-scale structure (community) and micro-scale structures of different orders (i.e., degree distribution, assortativity, and transitivity) for link prediction.

Keywords

• Null model
• link prediction
• community structure
• null network
• network topology