Infomap Clustering and the Map Equation

Communities as Regions of Trapped Flow

A graph community can be viewed not only as a set of densely connected vertices, but also as a region where a random walker tends to spend time before leaving. Infomap turns that view into a clustering objective: a good partition makes the walk’s path economical to describe. The method is therefore sensitive to the movement induced by graph edges, rather than directly to gene expression values or a prescribed number of clusters.

For a cell-neighborhood graph, the vertices represent cells and edge weights represent neighborhood connections. A random walker moves along these edges, with stronger edges receiving more transition probability. If it remains in one region for many steps, a coding scheme can reuse a short codebook for that region’s cells. When it crosses between regions, it must also encode which region’s codebook to use. The map equation balances these costs.

Definition: Consider a connected, undirected weighted graph with edge weights $w_{ij}=w_{ji}\geq 0$, no self-loops, vertex strengths $s_i=\sum_j w_{ij}>0$, and total edge weight $w=\sum_{i<j}w_{ij}$. A strength-weighted random walk moves from vertex $i$ to vertex $j$ with probability $P_{ij}=w_{ij}/s_i$. Its stationary probability is $\pi_i=s_i/(2w)$. For a partition into modules $M_1,\ldots,M_m$, the exit rate $q_a$ is the stationary probability per step of leaving module $M_a$, and $q=\sum_a q_a$ is the total module-exit rate.

The stationary formula applies under the stated connected, undirected graph assumptions. A step means one transition of the walk. Since the walk is stationary, $\pi_i$ is the long-run fraction of steps spent at vertex $i$, and $q_a$ is the long-run fraction of steps that leave module $M_a$. For an undirected graph, each edge crossing a module boundary contributes flow in both directions across the walk; the total outward exit rate is

q_a=\frac{\sum_{i\in M_a,\ j\notin M_a}w_{ij}}{2w}.

The sum counts each crossing edge once from the module’s side. Equivalently, it is the total boundary weight divided by $2w$. The stationary node mass in module $M_a$ is $p_a=\sum_{i\in M_a}\pi_i$. Its module codebook is used both for visits to its vertices and for exits from that module, so its use rate is $p_a^{\circlearrowright}=p_a+q_a$.

The Map Equation

A codebook assigns short binary codewords to symbols that occur often. For symbol probabilities $r_1,\ldots,r_k$, the Shannon entropy $H(r)=-\sum_{\ell=1}^k r_\ell\log_2 r_\ell$ is the ideal average code length in bits per symbol. Infomap applies this idea at two levels. An index codebook records which module is entered after an exit; each module codebook records visits to its vertices and exits from that module.

Definition: The map equation for a partition is $$ L=qH(Q)+\sum_{a=1}^m p_a^{\circlearrowright}H(P_a). $$ Here $Q$ is the distribution of module exits, with probability $q_a/q$ for module $a$, and $P_a$ is module $a$'s distribution over its exit symbol and its node symbols: the exit probability is $q_a/p_a^{\circlearrowright}$, and the probability for vertex $i\in M_a$ is $\pi_i/p_a^{\circlearrowright}$. If $q=0$, the index-codebook term is defined as zero. $L$ is the expected code length in bits per random-walk step.

Each codebook’s entropy is multiplied by its use rate to put all terms on the same per-step scale. The exit symbol matters: omitting it would fail to account for the information needed to switch codebooks. The objective searches for a partition with small $L$; lower values indicate a shorter description of the stationary walk, not necessarily a more meaningful biological classification.

Why the Objective Has These Terms

The coding justification follows from how often each codebook is used. During a long stationary walk, module $a$'s codebook is used for each visit to one of its nodes and for each exit from it. These occur at rates $\pi_i$ for node $i$ and $q_a$ for the exit symbol, so the overall use rate is $p_a+q_a$. Conditional on using that codebook, the symbol probabilities are the node and exit rates divided by $p_a+q_a$. Its expected contribution per step is therefore $(p_a+q_a)H(P_a)$.

After an exit, the index codebook identifies the module to be entered next. Module $a$'s exit symbol occurs at rate $q_a$, so the index codebook is used at total rate $q$, with conditional symbol probabilities $q_a/q$. Its expected contribution per step is $qH(Q)$. Adding the index and module contributions gives the map equation. This is an entropy-based ideal coding length; actual finite codewords may require small additional overhead.

Worked Example: Calculating Exit Flow on a Weighted Path

Consider three vertices with edge weights $w_{12}=1$, $w_{23}=2$, and no other edges. Take the partition $M_1=\{1\}$ and $M_2=\{2,3\}$. The total edge weight is $w=3$. The strengths are $s_1=1$, $s_2=3$, and $s_3=2$, which sum to $6=2w$. Thus the stationary probabilities are $\pi_1=1/6$, $\pi_2=1/2$, and $\pi_3=1/3$.

The only crossing edge has weight 1. Therefore each module has exit rate $q_a=1/6$, and the total exit rate is $q=1/3$. The stationary node masses are $p_1=1/6$ and $p_2=1/2+1/3=5/6$, giving module codebook use rates $p_1^{\circlearrowright}=1/3$ and $p_2^{\circlearrowright}=1$.

The two exits are equally likely in the index codebook, so $H(Q)=1$ bit and its contribution is $(1/3)(1)=1/3$ bit per step. In the first module, the node and exit rates are both $1/6$, so its two code symbols each have probability $1/2$. Its contribution is $(1/3)(1)=1/3$ bit per step.

For the second module, the probabilities of the node-2, node-3, and exit symbols are respectively $(1/2)/1=1/2$, $(1/3)/1=1/3$, and $(1/6)/1=1/6$. The entropy is $H(P_2)=-(1/2)\log_2(1/2)-(1/3)\log_2(1/3)-(1/6)\log_2(1/6)\approx1.459$ bits. Its use rate is 1, so the total is $L\approx1/3+1/3+1.459=2.126$ bits per step. This partition is a valid coding scheme, but this calculation alone does not establish that it is preferable to every alternative.

Comparing Candidate Partitions

The following example shows how a partition can shorten the description when strong internal edges keep the walk within two regions. It also illustrates why every term, including the index cost, must be included.

Worked Example: Two Strongly Connected Pairs

Take four vertices with edge weights $w_{12}=4$, $w_{23}=1$, and $w_{34}=4$, with all other weights zero. The total edge weight is 9, and the strengths are $4,5,5,4$, summing to 18. Compare one module containing all vertices with the two-module partition $\{1,2\},\{3,4\}$.

For one module, there are no exits, and the node probabilities are $4/18,5/18,5/18,4/18$. Thus $L=H(4/18,5/18,5/18,4/18)\approx1.991$ bits per step.

For the two-module partition, the only crossing edge has weight 1. Each module’s exit rate is $1/18$, and the total exit rate is $q=2/18=1/9$. The index symbols have equal probabilities, so the index contribution is $qH(1/2,1/2)=1/9$ bit per step. Each module has stationary node mass $9/18$, making its codebook use rate $10/18=5/9$. In either module, the conditional code probabilities are $1/10$ for exit and $4/10,5/10$ for the two nodes. Their entropy is $H(1/10,4/10,5/10)\approx1.361$ bits.

The two module-codebook contributions total $2(5/9)(1.361)\approx1.512$ bits per step. Therefore $L\approx1/9+1.512=1.623$ bits per step, less than the one-module value of 1.991. Under this graph’s stationary flow, the two-pair partition gives a shorter description. The result reflects the relatively low rate of crossing the single bridge compared with the strong within-pair edges.

Worked Example: Why Splitting Too Far Can Cost More

Use the same four-vertex graph, but compare the two-pair partition with the finer partition $\{1,2\},\{3\},\{4\}$. Its boundary weights are 1 for $\{1,2\}$, 5 for $\{3\}$, and 4 for $\{4\}$. Dividing by $2w=18$, the exit rates are $1/18,5/18,4/18$, with total $q=10/18=5/9$.

The index exit probabilities are $1/10,5/10,4/10$. Their entropy is $H(1/10,5/10,4/10)\approx1.361$ bits, so the index contribution is $(5/9)(1.361)\approx0.756$ bits per step.

For module $\{1,2\}$, the node mass is $9/18$, so its codebook use rate is $10/18$. Its conditional probabilities are $1/10,4/10,5/10$, with entropy about 1.361 bits. Its contribution is therefore about $(10/18)(1.361)=0.756$ bits per step. For singleton $\{3\}$, its node and exit rates are both $5/18$, giving entropy 1 bit and contribution $(10/18)(1)=0.556$. For singleton $\{4\}$, both rates are $4/18$, giving another contribution of $(8/18)(1)=0.444$.

Adding the terms gives $L\approx0.756+0.756+0.556+0.444=2.512$ bits per step. This exceeds the two-module value of about 1.623. Although the finer partition has a separate codebook for each region, its much larger exit rate and index cost outweigh that benefit.

Assumptions, Diagnostics, and Alternatives

The calculations above assume a connected, undirected weighted graph with positive strengths and a stationary strength-weighted walk. For directed graphs, the stationary distribution and transition probabilities must instead be derived from the specified directed walk; the undirected strength formula cannot simply be reused. A graph with disconnected components does not have a unique stationary distribution across all components without an additional convention, such as specifying component-specific walks or adding teleportation. Those choices change the flow being compressed and should be reported.

Useful checks during calculation include verifying that node probabilities sum to 1, that $\sum_a q_a=q$, and that each module codebook’s node probabilities plus exit probability sum to 1. If a module has no exit, its exit symbol has probability zero and contributes no entropy. Numerically, use the convention $0\log_2(0)=0$. A computed negative entropy or an exit rate exceeding the total stationary probability is a sign of an implementation or normalization error.

Infomap differs from alternatives in what it optimizes. Modularity compares within-community edge weight with a degree-based null expectation, whereas the map equation measures the code length of a random walk. Walktrap uses distances based on short random walks to assess vertex similarity. These objectives can return different partitions because they answer different structural questions. Infomap’s result is especially interpretable as a flow-based compression, but it is not a hypothesis test and its shorter code does not establish that the groups are cell types or causal biological units.

The fitted partition can also depend on the graph construction, edge weights, and the walk convention. A graph that poorly represents cell neighborhoods can yield a precise optimization of an unhelpful flow model. Inspect whether modules are connected in the graph, whether important boundary edges or hubs dominate transitions, and whether small changes to graph construction alter the substantive interpretation. Infomap is typically optimized with a search algorithm rather than by enumerating every possible partition; consequently, a reported solution is an algorithmic candidate, not automatically a proof of the global minimum.

Common Pitfall

Common mistake: “The partition with the most within-module edges must have the smallest map equation.” This ignores how frequently the walk exits modules and how much information the index and module codebooks require. The correction is to compute $q_a$, all codebook distributions, and the full $L$ for each candidate partition; edge density alone does not determine the objective.

Key takeaway: Infomap treats communities as regions that organize random-walker flow into reusable codebooks. A partition is favored when the savings from locally coding repeated visits outweigh the cost of encoding module exits and module identities.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions below.

For a connected undirected graph with total edge weight $w$, what is the stationary probability of vertex $i$ in the strength-weighted random walk?
Why does the map equation include both an index-codebook term and module-codebook terms?
In the four-vertex example, what is the exit rate of each module in the partition $\{1,2\},\{3,4\}$?
Why can a finer partition have a larger map equation even if its modules are internally well connected?

Solutions. (1) It is $\pi_i=s_i/(2w)$, where $s_i$ is the sum of incident edge weights. (2) The index codebook identifies a module after an exit, while each module codebook identifies its visited vertices and its exit symbol; both costs occur during the walk. (3) The crossing edge has weight 1, so each module’s exit rate is $1/(2w)=1/18$. (4) More modules can increase the total exit rate and the cost of identifying which module the walk enters, so those coding costs may exceed any savings from local codebooks.