Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Stochastic fluctuations and the detectability limit of network communities
 
research article

Stochastic fluctuations and the detectability limit of network communities

Floretta, Lucio  
•
Liechti, Jonas
•
Flammini, Alessandro
Show more
2013
Physical Review E

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.

  • Details
  • Metrics
Type
research article
DOI
10.1103/PhysRevE.88.060801
Web of Science ID

WOS:000328695200002

Author(s)
Floretta, Lucio  
Liechti, Jonas
Flammini, Alessandro
De Los Rios, Paolo  
Date Issued

2013

Publisher

American Physical Society

Published in
Physical Review E
Volume

88

Issue

6

Article Number

060801(R)

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LBS  
Available on Infoscience
January 20, 2014
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/99968
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés