Maps of random walks on complex networks reveal community structure

Martin Rosvall and Carl T. Bergstrom

To comprehend the multipartite organization of large-scale biological and social systems, we introduce a new information-theoretic approach to reveal 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 to each other. 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 — which includes 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.

PNAS 105, 1118 (2008)
arXiv:0707.0609

Code for the community-detection algorithm Infomap, Infomap online, and interactive applications for generating network maps, exploring networks, visualizing changes in networks and explaining the machinery of  the map equation for standard, multilevel, and higher-order networks are available on mapequation.org