000196119 001__ 196119
000196119 005__ 20181203023417.0
000196119 0247_ $$2doi$$a10.1103/PhysRevE.88.060801
000196119 022__ $$a1539-3755
000196119 02470 $$2ISI$$a000328695200002
000196119 037__ $$aARTICLE
000196119 245__ $$aStochastic fluctuations and the detectability limit of network communities
000196119 260__ $$aCollege Pk$$bAmerican Physical Society$$c2013
000196119 269__ $$a2013
000196119 300__ $$a5
000196119 336__ $$aJournal Articles
000196119 520__ $$aWe 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.
000196119 700__ $$0243667$$aFloretta, Lucio$$g197021$$uEcole Polytech Fed Lausanne, Lab Biophys Stat, CH-1015 Lausanne, Switzerland
000196119 700__ $$aLiechti, Jonas$$uEcole Polytech Fed Lausanne, Lab Biophys Stat, CH-1015 Lausanne, Switzerland
000196119 700__ $$aFlammini, Alessandro
000196119 700__ $$0240090$$aDe Los Rios, Paolo$$g144344$$uEcole Polytech Fed Lausanne, Lab Biophys Stat, CH-1015 Lausanne, Switzerland
000196119 773__ $$j88$$k6$$tPhysical Review E
000196119 909C0 $$0252262$$pLBS$$xU10871
000196119 909CO $$ooai:infoscience.tind.io:196119$$pSB$$particle
000196119 917Z8 $$x144344
000196119 937__ $$aEPFL-ARTICLE-196119
000196119 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000196119 980__ $$aARTICLE