Narrow scope for resolution-limit-free community detection

V. A. Traag, P. Van Dooren, and Y. Nesterov
Phys. Rev. E 84, 016114 – Published 29 July 2011

Abstract

Detecting communities in large networks has drawn much attention over the years. While modularity remains one of the more popular methods of community detection, the so-called resolution limit remains a significant drawback. To overcome this issue, it was recently suggested that instead of comparing the network to a random null model, as is done in modularity, it should be compared to a constant factor. However, it is unclear what is meant exactly by “resolution-limit-free,” that is, not suffering from the resolution limit. Furthermore, the question remains what other methods could be classified as resolution-limit-free. In this paper we suggest a rigorous definition and derive some basic properties of resolution-limit-free methods. More importantly, we are able to prove exactly which class of community detection methods are resolution-limit-free. Furthermore, we analyze which methods are not resolution-limit-free, suggesting there is only a limited scope for resolution-limit-free community detection methods. Finally, we provide such a natural formulation, and show it performs superbly.

  • Figure
  • Figure
  • Figure
  • Received 29 April 2011

DOI:https://doi.org/10.1103/PhysRevE.84.016114

©2011 American Physical Society

Authors & Affiliations

V. A. Traag* and P. Van Dooren

  • ICTEAM, Université Catholique de Louvain, Bâtiment Euler, Avenue G. Lemaître 4, B-1348 Louvain-la Neuve, Belgium

Y. Nesterov

  • CORE, Université Catholique de Louvain, Voie du Roman Pays 34, B-1348 Louvain-la Neuve, Belgium

  • *vincent.traag@uclouvain.be

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 84, Iss. 1 — July 2011

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×