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 of 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.