Infomap

Infomap is a software package and information-theoretic approach for detecting community structure in complex networks. It is based on the map equation, which expresses the theoretical description length required to describe the movements of a random walker on a network. By minimizing this description length, Infomap partitions the network into modules that best capture flow on the network.

The algorithmic idea centers on describing a random walk efficiently. The map equation encodes the trajectory using a two-level code: short codes for movements within modules and longer codes for transitions between modules. Infomap uses heuristic optimization to find partitions that minimize the map equation, and it can produce hierarchical partitions with modules contained within modules.

Features and inputs: Infomap accommodates directed and weighted graphs, supports large networks, and can perform hierarchical community detection. It outputs include module assignments, community hierarchies, and inter-module flow (visitation flux). The software is implemented as open-source code with implementations in C++ and interfaces in other languages, and it runs on multiple platforms.

Applications and evaluation: Infomap is widely used in network science across biology, neuroscience, social and information networks, transportation systems, ecology, and related fields. It emphasizes flow-based structure, often identifying meaningful communities based on dynamic processes on the network. It is frequently used as an alternative or complement to modularity-based methods for detecting communities.

History: Infomap was developed by Martin Rosvall and colleagues, with the map equation introduced in the late 2000s. Since then, the software has been maintained and expanded by its developers and the user community, remaining a prominent tool for flow-based community detection.