• PNAS Subscriptions
  • Sign-up for PNAS eTOC Alerts

Resolution limit in community detection

  1. Santo Fortunato † , ‡ , § and
  2. Marc Barthélemy † , , ‖
  1. †School of Informatics and Center for Biocomplexity, Indiana University, Bloomington, IN 47406;
  2. ‡Fakultät für Physik, Universität Bielefeld, D-33501 Bielefeld, Germany;
  3. §Complex Networks Lagrange Laboratory (CNLL), ISI Foundation, 10133 Torino, Italy; and
  4. Commissariat à l'Energie Atomique–Département de Physique Théorique et Appliquée, 91680 Bruyeres-Le-Chatel, France

  1. Edited by David O. Siegmund, Stanford University, Stanford, CA, and approved November 6, 2006 (received for review July 17, 2006)

  1. Fig. 1.
    View larger version:
    Fig. 1.

    Design of a connected network with maximal modularity. The modules (circles) must be connected to each other by the minimal number of links.

  2. Fig. 2.
    View larger version:
    Fig. 2.

    Scheme of a network partition into three or more modules. The circles on the left represent two modules Graphic 1 and Graphic 2, the oval on the right represents the rest of the network Graphic 0, whose structure is arbitrary.

  3. Fig. 3.
    View larger version:
    Fig. 3.

    Schematic examples. (A) A network made out of identical cliques (which are here complete graphs with m nodes) connected by single links. If the number of cliques is larger than about Formula, modularity optimization would lead to a partition where the cliques are combined into groups of two or more (represented by dotted lines). (B) A network with four pairwise identical cliques (complete graphs with m and p < m nodes, respectively); if m is large enough with respect to p (e.g., m = 20, p = 5), modularity optimization merges the two smallest modules into one (shown with a dotted line).

Footnotes

  • ‖To whom correspondence should be addressed. E-mail: marc.barthelemy{at}cea.fr

Online Impact