Paper Info
Title
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 conclusion that the native, putative partition of the network is completely lost even before the in-degree/out-degree ratio becomes equal to that of a structureless Erdos-Renyi 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 (semiquantitatively) 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.
Year
DOI
Venue
2013
10.1103/PhysRevE.88.060801
PHYSICAL REVIEW E
DocType
Volume
Issue
Journal
88
6
ISSN
Citations 
PageRank 
1539-3755
1
0.36
References 
Authors
0
4
Name
Order
Citations
PageRank
Lucio Floretta110.36
Jonas Liechti220.73
Alessandro Flammini3170594.69
Paolo De Los Rios4133.11