Stochastic fluctuations and the detectability limit of network communities

Abstract

We have analyzed the detectability limits of network communities in the framework of the popular Girvan and Newman benchmark. By carefully taking into account the inevitable stochastic fluctuations that affect the construction of each and every instance of the benchmark, we come to the conclusions that the native, putative partition of the network is completely lost even before the in-degree/out-degree ratio becomes equal to the one of a structure-less Erdös-Rényi network. We develop a simple iterative scheme, analytically well described by an infinite branching-process, to provide an estimate of the true detectability limit. Using various algorithms based on modularity optimization, we show that all of them behave (semi-quantitatively) in the same way, with the same functional form of the detectability threshold as a function of the network parameters. Because the same behavior has also been found by further modularity-optimization methods and for methods based on different heuristics implementations, we conclude that indeed a correct definition of the detectability limit must take into account the stochastic fluctuations of the network construction.

5 pages, 5 figures, correction of typos, improvement of the bibliography and of the notation, general compression

References in corpus (10)

• Fast unfolding of communities in large networks
• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• Parsimonious module inference in large networks
• Spectra of random graphs with arbitrary expected degrees
• (Un)detectable cluster structure in sparse networks
• Detectability of communities in heterogeneous networks

Cited by in corpus (2)

• Large network community detection by fast label propagation
• Improving the performance of algorithms to find communities in networks