umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
Umeå University, Faculty of Science and Technology, Department of Physics.
Department of Biology, University of Washington.
2011 (English)In: PLoS ONE, ISSN 1932-6203, Vol. 6, no 4, e18209- p.Article in journal (Refereed) Published
Abstract [en]

To comprehend the hierarchical organization of large integrated systems, we introduce the hierarchical map equation, which reveals multilevel structures in networks. In this information-theoretic approach, we exploit the duality between compression and pattern detection; by compressing a description of a random walker as a proxy for real flow on a network, we find regularities in the network that induce this system-wide flow. Finding the shortest multilevel description of the random walker therefore gives us the best hierarchical clustering of the network — the optimal number of levels and modular partition at each level — with respect to the dynamics on the network. With a novel search algorithm, we extract and illustrate the rich multilevel organization of several large social and biological networks. For example, from the global air traffic network we uncover countries and continents, and from the pattern of scientific communication we reveal more than 100 scientific fields organized in four major disciplines: life sciences, physical sciences, ecology and earth sciences, and social sciences. In general, we find shallow hierarchical structures in globally interconnected systems, such as neural networks, and rich multilevel organizations in systems with highly separated regions, such as road networks.

Place, publisher, year, edition, pages
2011. Vol. 6, no 4, e18209- p.
National Category
Other Physics Topics
Identifiers
URN: urn:nbn:se:umu:diva-43073DOI: 10.1371/journal.pone.0018209OAI: oai:DiVA.org:umu-43073DiVA: diva2:411199
Funder
Swedish Research Council, 2009-5344
Available from: 2011-04-16 Created: 2011-04-16 Last updated: 2011-04-19Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Rosvall, Martin

Search in DiVA

By author/editor
Rosvall, Martin
By organisation
Department of Physics
Other Physics Topics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 73 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf