Maps of Random Walks on Complex Networks Reveal Community Structure

Authors

Martin Rosvall, Carl T. Bergstrom

Year

2007

Journal Paper

Algorithm

Infomap

Source

Proceedings of the National Academy of Sciences of the United States of America

Identifiers

arXiv 0707.0609 DOI 10.1073/pnas.0706851105

Abstract¶

To comprehend the multipartite organization of large-scale biological and social systems, we introduce a new information theoretic approach that reveals community structure in weighted and directed networks. The method decomposes a network into modules by optimally compressing a description of information flows on the network. The result is a map that both simplifies and highlights the regularities in the structure and their relationships. We illustrate the method by making a map of scientific communication as captured in the citation patterns of more than 6000 journals. We discover a multicentric organization with fields that vary dramatically in size and degree of integration into the network of science. Along the backbone of the network - including physics, chemistry, molecular biology, and medicine - information flows bidirectionally, but the map reveals a directional pattern of citation from the applied fields to the basic sciences.

Summary¶

Introduces the map equation and Infomap, framing community detection as compression of random-walk flows on a network. This shifted part of the field from purely density- or modularity-based partitions toward flow-based communities, especially useful for directed and weighted networks.