Detectability threshold in weighted modular networks

Abstract

We study the necessary condition to detect, by means of spectral modularity optimization, the ground-truth partition in networks generated according to the weighted planted-partition model with two equally sized communities. We analytically derive a general expression for the maximum level of mixing tolerated by the algorithm to retrieve community structure, showing that the value of this detectability threshold depends on the first two moments of the distributions of node degree and edge weight. We focus on the standard case of Poisson-distributed node degrees and compare the detectability thresholds of five edge-weight distributions: Dirac, Poisson, exponential, geometric, and signed Bernoulli. We show that Dirac distributed weights yield the smallest detectability threshold, while exponentially distributed weights increase the threshold by a factor $\sqrt{2}$, with other distributions exhibiting distinct behaviors that depend, either or both, on the average values of the degree and weight distributions. Our results indicate that larger variability in edge weights can make communities less detectable. In cases where edge weights carry no information about community structure, incorporating weights in community detection is detrimental.

15 pages, 5 figures

References in corpus (31)

• Modularity and community structure in networks
• Community detection in graphs
• From Louvain to Leiden: guaranteeing well-connected communities
• Analysis of weighted networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Spectral redemption: clustering sparse networks
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• The entropy of network ensembles
• Learning Latent Block Structure in Weighted Networks
• The entropy of randomized network ensembles
• Tolerating the Community Detection Resolution Limit with Edge Weighting
• Generalized Bose-Fermi statistics and structural correlations in weighted networks
• Community detection for correlation matrices
• Inferring monopartite projections of bipartite networks: an entropy-based approach
• Enhancing community detection using a network weighting strategy
• Nonparametric weighted stochastic block models
• (Un)detectable cluster structure in sparse networks
• Detectability of communities in heterogeneous networks
• Accuracy and Precision of Methods for Community Identification in Weighted Networks
• Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
• Unveiling community structures in weighted networks
• Adaptive Modularity Maximization via Edge Weighting Scheme
• A paradox in community detection
• Mean-field theory of graph neural networks in graph partitioning
• Universal Phase Transition in Community Detectability under a Stochastic Block Model
• Detecting modules in dense weighted networks with the Potts method
• Fast extraction of the backbone of projected bipartite networks to aid community detection
• Spreading and Structural Balance on Signed Networks
• Iterative embedding and reweighting of complex networks reveals community structure
• Detectability of hierarchical communities in networks