Community detection based on significance optimization in complex networks

Abstract

Community structure is an important structural property that extensively exists in various complex networks. In the past decade, much attention has been paid to the design of community-detection methods, but analyzing the behaviors of the methods is also of interest in the theoretical research and real applications. Here, we focus on an important measure for community structure, significance [Sci. Rep. 3 (2013) 2930]. Specifically, we study the effect of various network parameters on this measure in detail, analyze the critical behaviors of it in partition transition, and analytically give the formula of the critical points and the phase diagrams. The results shows that the critical number of communities in partition transition increases dramatically with the difference between inter- and intra-community link densities, and thus significance optimization displays higher resolution in community detection than many other methods, but it is also easily to lead to the excessive splitting of communities. By Louvain algorithm for significance optimization, we confirmed the theoretical results on artificial and real-world networks, and give a series of comparisons with some classical methods.

References in corpus (42)

• 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
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Self-similar community structure in organisations
• Finding statistically significant communities in networks
• Community Structure in Jazz
• The performance of modularity maximization in practical contexts
• Synchronization reveals topological scales in complex networks
• Analysis of the structure of complex networks at different resolution levels
• Phase transition in the detection of modules in sparse networks
• Detecting Network Communities: a new systematic and efficient algorithm
• Narrow scope for resolution-limit-free community detection
• Detecting network communities by propagating labels under constraints
• Modularity-Maximizing Network Communities via Mathematical Programming
• Graph spectra and the detectability of community structure in networks
• Optimal network modularity for information diffusion
• Local resolution-limit-free Potts model for community detection
• Evaluating Local Community Methods in Networks
• Community Structure of the Physical Review Citation Network
• Significant Scales in Community Structure
• Improved community structure detection using a modified fine tuning strategy
• Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels
• Scaling of degree correlations and the influence on diffusion in scale-free networks
• (Un)detectable cluster structure in sparse networks
• Markov random walk under constraint for discovering overlapping communities in complex networks
• Deterministic Modularity Optimization
• Community structure benefits the fixation of cooperation under strong selection
• Finding network communities using modularity density
• Multi-resolution community detection based on generalized self-loop rescaling strategy
• Leveraging disjoint communities for detecting overlapping community structure
• Enhancing community detection by local structural information
• Analysis and perturbation of degree correlation in complex networks
• Enhance the Efficiency of Heuristic Algorithm for Maximizing Modularity Q