• Institution: Staats- und Universitaetsbibliothek Bremen
  • Research in the physical sciences including applied physical sciences; astronomy; earth, atmospheric, and planetary sciences; and physics.
  • Science Sessions: The PNAS Podcast Program

Extracting the hierarchical organization of complex systems

  1. Marta Sales-Pardo,
  2. Roger Guimerà,
  3. André A. Moreira, and
  4. Luís A. Nunes Amaral *

Author Affiliations

  1. Department of Chemical and Biological Engineering and Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL 60208

  1. Edited by H. Eugene Stanley, Boston University, Boston, MA, and approved July 22, 2007 (received for review April 23, 2007)

    1. Abstract
    2. Full Text
    3. Authors & Info
    4. Figures
    6. SI
    7. Metrics
    8. PDF
    9. PDF + SI

    Abstract

    Extracting understanding from the growing “sea” of biological and socioeconomic data is one of the most pressing scientific challenges facing us. Here, we introduce and validate an unsupervised method for extracting the hierarchical organization of complex biological, social, and technological networks. We define an ensemble of hierarchically nested random graphs, which we use to validate the method. We then apply our method to real-world networks, including the air-transportation network, an electronic circuit, an e-mail exchange network, and metabolic networks. Our analysis of model and real networks demonstrates that our method extracts an accurate multiscale representation of a complex system.

    Footnotes

    • *To whom correspondence should be addressed. E-mail: amaral@northwestern.edu

    • Author contributions: M.S.-P. and L.A.N.A. designed research; M.S.-P. performed research; M.S.-P., R.G., and A.A.M. analyzed data; and M.S.-P., R.G., and L.A.N.A. wrote the paper.

    • The authors declare no conflict of interest.

    • This article is a PNAS Direct Submission.

    • This article contains supporting information online at www.pnas.org/cgi/content/full/0703740104/DC1.

    • ↵ † We do not consider other hierarchical schemes that classify nodes according to, for instance, their importance (7). Another issue that we do not address here is that of “overlapping” modules. Note also that some authors refer to the existence of “soft” boundaries between communities (8, 9). However, there has been so far no rigorous connection between the soft boundaries and the overlap between communities. Moreover, at present, there is no theoretical model that includes overlapping modules, that is, modules that share nodes, as opposed to communities that share edges.

    • ↵ ‡ Results for real networks at a 5% significance level are identical; however, the more stringent threshold is more efficient at detecting the last level in the hierarchy for model networks. Only for a 1–3% of the cases—depending on the cohesiveness of the levels—does the algorithm find one more level than expected.

    • ↵ § We have also applied Akaike's information criterion (34), obtaining the same results for nearly all cases.

    • ↵ The ability of the present method to detect the top level is significant. A previous study coauthored by two of us identified 19 modules in the worldwide air-transportation network (37) by using the most accurate modularity maximization algorithm in the literature (38).

    • ↵ ‖ In the SI Text , we also show the organization obtained for the UCSD reconstruction of the metabolic network for Helicobacter pylori (39).

    HighWire Press-hosted articles citing this article