Detecting Statistically Significant Communities

Abstract

Community detection is a key data analysis problem across different fields. During the past decades, numerous algorithms have been proposed to address this issue. However, most work on community detection does not address the issue of statistical significance. Although some research efforts have been made towards mining statistically significant communities, deriving an analytical solution of p-value for one community under the configuration model is still a challenging mission that remains unsolved. The configuration model is a widely used random graph model in community detection, in which the degree of each node is preserved in the generated random networks. To partially fulfill this void, we present a tight upper bound on the p-value of a single community under the configuration model, which can be used for quantifying the statistical significance of each community analytically. Meanwhile, we present a local search method to detect statistically significant communities in an iterative manner. Experimental results demonstrate that our method is comparable with the competing methods on detecting statistically significant communities.

References in corpus (27)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Cooperative Game Theory Approaches for Network Partitioning
• Benchmark graphs for testing community detection algorithms
• Defining and identifying communities in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Extracting the hierarchical organization of complex systems
• Robustness of community structure in networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Community extraction for social networks
• Significant Scales in Community Structure
• Statistical significance of communities in networks
• When are networks truly modular?
• Deciphering Network Community Structure by Surprise
• Z-score-based modularity for community detection in networks
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Testing for Global Network Structure Using Small Subgraph Statistics
• A testing based extraction algorithm for identifying significant communities in networks
• Measuring Significance of Community Structure in Complex Networks
• Thermodynamics of Community Structure
• Combinatorial approach to Modularity
• Statistical test for detecting community structure in real-valued edge-weighted graphs