Completeness of Community Structure in Networks

By defining a new measure to community structure, exclusive modularity, and based on cavity method of statistical physics, we develop a mathematically principled method to determine the completeness of community structure, which represents whether a partition that is either annotated by experts or given by a community-detection algorithm, carries complete information about community structure in the network. Our results demonstrate that the expert partition is surprisingly incomplete in some networks such as the famous political blogs network, indicating that the relation between meta-data and community structure in real-world networks needs to be re-examined. As a byproduct we find that the exclusive modularity, which introduces a null model based on the degree-corrected stochastic block model, is of independent interest. We discuss its applications as principled ways of detecting hidden structures, finding hierarchical structures without removing edges, and obtaining low-dimensional embedding of networks.