Detectability threshold in weighted modular networks

Filippo Radicchi, Filipi N. Silva, Alessandro Flammini, Santo Fortunato, Sadamori Kojaku · 2025

Read Detectability threshold in weighted modular networks by Filippo Radicchi, Filipi N. Silva, Alessandro Flammini, Santo Fortunato, Sadamori Kojaku (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-00214.txt.

Introduction

Finding hidden groups inside a network gets harder when links carry weights, such as strengths or counts. Filippo Radicchi and four co-authors ask when a standard spectral method can still recover the true split. They use a planted-partition model, a test network built with two equal groups, and derive a formula for the most mixing the method can tolerate.

The threshold turns on how node degree and link weight vary. Weights that spread out more make groups harder to spot. When weights carry no clue about group membership, adding them hurts rather than helps. Five weight patterns are compared, from fixed weights to weights drawn from spread-out distributions.

Catalog record

CREATORFilippo Radicchi, Filipi N. Silva, Alessandro Flammini, Santo Fortunato, Sadamori Kojaku
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-00214

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Detectability threshold in weighted modular networks Filippo Radicchi, Filipi N. Silva, Alessandro Flammini, Santo Fortunato, Sadamori Kojaku 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 of 2 \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 edge weights in community detection is detrimental. Introduction Many real networks display a mesoscopic organization in modules or clusters often referred to as communities Fortunato 2010 . A community is roughly defined as a subgroup of nodes with a density of within-community connections larger than the density of cross-community links. The relative number of cross-cluster edges determines the level of mixing of the network. If mixing is small enough, clusters are sufficiently well separated one from the other to allow for some level of detection. As mixing increases, communities become eventually undetectable, i.e., their detection can not be performed better than random guessing. The maximum level of mixing for the clusters to be detectable is the so-called detectability threshold Reichardt and Leone 2008 ; Decelle et al. 2011 . The existence of two regimes of detectability of network modular structure has been proven for several types of community detection algorithms, including spectral clustering methods Nadakuditi and Newman 2012 ; Radicchi 2013 ; Krzakala et al. 2013 ; Chen and Hero III 2015 , modularity-maximization-based methods Radicchi 2014 , as well as methods based on neural networks Kojaku et al. 2024 ; Kawamoto et al. 2018 ; Chen et al. 2019 . These findings are backed up by formal information-theoretic derivations of the detectability threshold Abbe and Sandon 2015 ; Abbe and Sandon 2016 ; Abbe 2018 . The standard setting where the problem has been investigated is the planted-partition model (PPM) Condon and Karp 2001 with two communities of equal size, where within- and cross-cluster degrees of individual nodes are random variates extracted from Poisson distributions with average values respectively equal to \langle k_{\text{in}}\rangle and \langle k_{\text{out}}\rangle . One would naively expect communities to be detectable as long as \langle k_{\text{in}}\rangle-\langle k_{\text{out}}\rangle>0 ; instead, better-than-random detection is possible only if \langle k_{\text{in}}\rangle-\langle k_{\text{out}}\rangle>\sqrt{\langle k_{\text{in}}\rangle+\langle k_{\text{out}}\rangle} Decelle et al. 2011 . The problem of community detectability has been studied also under other settings, for example PPMs with different types of degree distributions Radicchi 2013 , heterogeneous community sizes Decelle et al. 2011 ; Abbe and Sandon 2016 , non-null levels of correlation among the within- and cross-cluster degrees Radicchi 2014 and hierarchical community structure Peel and Schaub 2024 , just to mention a few of them. The general message from all these investigations is that the value of the detectability threshold may dramatically change from network to network, however, there is no algorithm that can perform better than random guessing when the level of mixing is greater than the network-specific threshold value. The goal of the present paper is to generalize the problem of community detectability to networks with weighted edges. The fact that this specific problem has not been considered so far is somehow surprising given that community detection in weighted graphs has been the focus on a large body of papers, e.g., Refs. Newman 2004 ; Alves 2007 ; Lancichinetti and Fortunato 2009 ; Heimo et al. 2008 ; Fan et al. 2007 ; Peixoto 2018 ; MacMahon and Garlaschelli 2015 ; Tian and Lambiotte 2024 . Intuitively, one would expect that incorporating edge weights into community detection should enhance performance by providing richer information beyond mere topological structure Kovács et al. 2024 ; Lu et al. 2018 ; Berry et al. 2011 ; De Meo et al. 2013 . Our analysis reveals that performance enhancement arises only when edge weights are positively correlated with community structure. If edge weights are generated independently from community structure instead, weights act as noise that impedes the proper detection of the communities. In this case, ignoring edge weights widens the detectable regime. These findings suggest that the utility of edge weights in community detection depends critically on whether they reinforce the community structure or not. We derive a general detectability limit that depends on the first two moments of the node degree and the edge weight distributions, providing a unified framework for understanding community detection in weighted networks. We then focus on two specific cases: communities manifested solely through the topology with homogeneous weights, and communities manifested through edge weights with homogeneous topology. These two cases represent complementary scenarios for how community structure can emerge in weighted networks. For both specific cases, we consider a variant of the PPM model where within- and cross-cluster degrees obey Poisson distributions with average values \langle k_{\text{in}}\rangle and \langle k_{\text{out}}\rangle , respectively, and edges are weighted by random variates with average values \langle w_{\text{in}}\rangle and \langle w_{\text{out}}\rangle , respectively. We derive closed-form expressions for the detectability thresholds across five weight distributions: Dirac, Poisson, geometric, signed Bernoulli, and exponential. Our key findings reveal a hierarchy of detectability thresholds. The Dirac distribution yields the smallest detectability threshold, matching the unweighted PPM limit and serving as the optimal baseline. Exponential weights consistently increase the threshold by a factor of \sqrt{2} compared to Dirac weights. Poisson and signed-Bernoulli distributions exhibit variable behavior: they produce the largest thresholds for small total weights but approach the Dirac limit as the total weights increase. Geometric weights show intermediate behavior, with thresholds that increase and approach the exponential distribution performance as the total weights increase. These results apply to both community manifestation scenarios—through topology with homogeneous weights and through edge weights with homogeneous topology—and are derived using spectral optimization of the modularity function. We validate our theoretical predictions by extending the analysis to multi-community networks using the Leiden algorithm, which confirms the same hierarchy of weight distributions across different numbers of communities (Appendix D ). We believe these findings extend to arbitrary community detection methods in weighted networks. Methods Weighted planted-partition model We consider networks generated according to a planted-partition model (PPM) with two blocks containing N nodes each Condon and Karp 2001 . We refer to these blocks as ground-truth communities or clusters. Without loss of generality, we label with i=1,\ldots,N the nodes in the first community, and with i=N+1,\ldots,2N the nodes in the second community. Weighted connections among pairs of nodes are generated with a two-step procedure Aicher et al. 2014 ; Peixoto 2018 : 1. We consider each pair of distinct nodes

Read the complete text