Hierarchy and the multilevel map equation

Concept

At a glance

The multilevel map equation lets Infomap discover how many levels of nested structure your network contains, with no resolution parameter to tune.

Limits of a two-level partition

Real networks rarely organise into one flat layer of modules. Scientific disciplines hold sub-fields that hold research topics, and cities hold neighbourhoods that hold blocks. A plain two-level partition, one index codebook over one set of leaf modules, sees only one cross-section of that structure at a time.

The two-level map equation has a resolution limit [Kawamoto and Rosvall, 2015]: modules with too few internal links go missing, because merging them into a larger module shortens the two-level description. The threshold grows with the logarithm of the total boundary-crossing traffic; the toggle below gives the exact bound. In a nested network the two-level method must choose between resolving the fine-grained modules and capturing the coarse super-groups.

The multilevel map equation lifts the limit: it allows nested index codebooks to any depth. It adds a level only when that level shortens the total description, so you read the depth of the output tree off the data. Multilevel is the default; pass two_level=True to disable it.

Nested addresses

Think of the two-level map as a street address with two parts: city and street. That works for a small country. For the whole world you need at least country → city → street, and for a large nation country → state → city → street. Each extra level earns its place only when travellers stay inside the smaller unit often enough that the added name pays for itself in shorter directions overall.

The multilevel map equation applies the same logic to random-walk descriptions. Each level of hierarchy adds a set of nested codebooks. When a walker stays inside a module for a long time, giving that module its own sub-codebook for the nodes it visits shortens the description. The same objective, description length, decides whether to add another sub-level: Infomap keeps adding levels until none shortens the description, then stops.

The result is a tree of modules. Each leaf is a network node. Internal tree nodes are modules at different granularities. You can read off the coarse super-group membership at level 1, the fine-grained triangle membership at level 2, and so on.

Nested codebooks

The two-level map equation (see the map equation chapter) uses one index codebook to describe inter-module movements and one codebook per module to describe intra-module node visits:

\[ L(\mathsf{M}) = q_{\curvearrowright} H(\mathcal{Q}) + \sum_{i} p_{\circlearrowright}^i H(\mathcal{P}^i). \]

The hierarchical extension [Rosvall and Bergstrom, 2011] replaces the single index codebook with a tree of nested index codebooks. Each module \(i\) at the top level has its own sub-index codebook \(\mathcal{Q}^i\) for directing the random walker among its sub-modules. Those sub-modules can have their own sub-sub-index codebooks, and so on. The total description length becomes a recursive sum:

\[ L(\mathsf{M}) = q_{\curvearrowright} H(\mathcal{Q}) + \sum_{i} L(\mathsf{M}^i), \]

where each sub-map \(\mathsf{M}^i\) contributes

\[ L(\mathsf{M}^i) = q_{\circlearrowright}^i H(\mathcal{Q}^i) + \sum_{j} L(\mathsf{M}^{ij}), \]

and the recursion bottoms out at the leaf level with

\[ L(\mathsf{M}^{ij\ldots k}) = p_{\circlearrowright}^{ij\ldots k} H(\mathcal{P}^{ij\ldots k}). \]

The rate \(q_{\circlearrowright}^i\) at which the walker uses module \(i\)’s sub-index codebook depends on the local traffic within module \(i\). It does not depend on a global cut size that grows with the whole network. This is why the resolution limit relaxes; see [Kawamoto and Rosvall, 2015], §IV.

Infomap searches for the hierarchical partition that minimises the total \(L\) using a fast stochastic recursive algorithm. It first generates top-level modules, then recursively applies the same procedure inside each module to find sub-modules. It adds or removes levels wherever the description shortens. The search converges to a locally optimal hierarchical tree.

Resolution limit: why two-level fails and hierarchy helps

You can derive the two-level map equation’s resolution limit analytically [Kawamoto and Rosvall, 2015]. For an undirected network with cut size \(C\) (total number of links crossing module boundaries), the two-level method can fail to detect a module with \(l_c\) internal links when

\[ \frac{4^{l_c}}{l_c + 1} \lesssim C. \]

Contrast this with modularity, whose resolution limit grows with the size of the whole network: it cannot resolve communities with fewer than roughly \(\sqrt{m/2}\) internal links, where \(m\) is the total link count (see Reading Infomap through Louvain and Leiden). The map equation’s dependence on the local cut size \(C\) rather than the global \(m\) is already much less restrictive, but it does not vanish.

The hierarchical map equation evaluates the analogous update with the effective network size equal to the super-module plus its boundary links, not the full network. Because a super-module is much smaller than the full network, the cut size that gates a fine-level split is tiny. The search therefore resolves fine-level modules that the two-level stage would swallow. For networks with a pronounced nested structure the hierarchical method all but eliminates the resolution limit; see [Kawamoto and Rosvall, 2015], §IV.

Nine triangles, three super-groups

The nine-triangles network from the examples on mapequation.org is built for exactly this: twenty-seven nodes in nine triangles, arranged in three super-groups of three triangles each. Weight-1 links join the triangles inside a super-group; the three links between super-groups are weaker, 0.8. We build it by hand and let Infomap find the nesting automatically; it also ships ready-made as infomap.datasets.nine_triangles().

Build the network

import networkx as nx
import infomap

links = []

# Nine triangles: nodes {1, 2, 3}, {4, 5, 6}, ..., {25, 26, 27}
for t in range(9):
    a, b, c = 3 * t + 1, 3 * t + 2, 3 * t + 3
    links += [(a, b, 1.0), (a, c, 1.0), (b, c, 1.0)]

# Weight-1 links join the three triangles inside each super-group
for base in (0, 9, 18):
    links += [
        (base + 2, base + 4, 1.0),
        (base + 3, base + 7, 1.0),
        (base + 6, base + 8, 1.0),
    ]

# Weaker links join the three super-groups into a ring
links += [(5, 10, 0.8), (9, 19, 0.8), (18, 23, 0.8)]

G = nx.Graph()
for u, v, w in links:
    G.add_edge(u, v, weight=w)

print(f"Nodes: {G.number_of_nodes()}, Edges: {G.number_of_edges()}")

Nodes: 27, Edges: 39

Run multilevel Infomap

from infomap import Network, run

net = Network()
for u, v, w in links:
    net.add_link(u, v, w)
result = run(net, num_trials=10, seed=123)

print(f"Tree depth (num_levels): {result.num_levels}")
print(f"Top-level modules:       {result.num_top_modules}")
print(f"Map equation codelength: {result.codelength:.4f} bits/step")

# The text below reads these exact counts; assert so the build catches drift.
assert result.num_levels == 3
assert result.num_top_modules == 5

# The bundled copy is the same network; the two must agree exactly.
result_pkg = infomap.run(infomap.datasets.nine_triangles(),
                         num_trials=10, seed=123)
assert result.codelength == result_pkg.codelength

Tree depth (num_levels): 3
Top-level modules:       5
Map equation codelength: 3.3719 bits/step

As num_levels shows, the tree is three levels deep — but not everywhere, and num_top_modules is five, not three. Two of the super-groups are kept as intermediate modules that nest their three triangles; the third super-group’s triangles sit directly under the root. The reason is the map equation itself: an intermediate module is only worth having if the index codebook it adds costs less than the description it saves. Once two super-groups are in place, the third no longer pays for its own codebook — listing its three triangles at the top level is cheaper — so the optimal tree of this perfectly symmetric network is ragged. (Dropping all three super-groups at once would cost 0.13 bits; dropping exactly one saves 0.014 bits.)

Read module assignments at each level

# Coarsest level (level 1): two super-groups plus the three triangles of the third
modules_l1 = result.modules(level=1)

# Finer level (level 2): the nine individual triangles
modules_l2 = result.modules(level=2)

print("Level-1 assignment (top modules):")
print(modules_l1)

print("\nLevel-2 assignment (triangles):")
print(modules_l2)

assert len(set(modules_l2.values())) == 9

Level-1 assignment (top modules):
{16: 1, 17: 1, 18: 1, 11: 1, 12: 1, 10: 1, 13: 1, 15: 1, 14: 1, 20: 2, 21: 2, 19: 2, 22: 2, 24: 2, 23: 2, 25: 2, 26: 2, 27: 2, 7: 3, 8: 3, 9: 3, 4: 4, 6: 4, 5: 4, 2: 5, 3: 5, 1: 5}

Level-2 assignment (triangles):
{16: 1, 17: 1, 18: 1, 11: 2, 12: 2, 10: 2, 13: 3, 15: 3, 14: 3, 20: 4, 21: 4, 19: 4, 22: 5, 24: 5, 23: 5, 25: 6, 26: 6, 27: 6, 7: 7, 8: 7, 9: 7, 4: 8, 6: 8, 5: 8, 2: 9, 3: 9, 1: 9}

Pass level=-1 for the finest (leaf) level whatever the tree depth.

Visualise both levels side by side

from myst_nb import glue

import matplotlib.pyplot as plt
from docs_viz import draw_partition

fig, axes = plt.subplots(1, 2, figsize=(9, 4), layout="constrained")

# Same flow in both panels; only the level of the grouping differs.
flow = {n.node_id: n.flow for n in result.nodes()}

draw_partition(G, modules_l1, ax=axes[0], flow=flow)
axes[0].set_title("Level 1: top modules", fontsize=11)

draw_partition(G, modules_l2, ax=axes[1], flow=flow)
axes[1].set_title("Level 2: triangles", fontsize=11)

fig.suptitle("Two levels of hierarchy, discovered automatically", fontsize=12)
glue("fig-hierarchy-and-the-multilevel-map", fig, display=False)
plt.close(fig)
../_images/b2a9f059ecb82ebce2bad4ddeb2141c5b5c7f334f1d3f5d3d9bb09d9dbb98044.png

Fig. 3 The same nested network at two levels of the hierarchy Infomap discovers. Left: the five top-level modules — two super-groups, and the three triangles of the third super-group listed directly under the root. Right: the nine fine triangles. Both panels share one layout, so the levels read against each other.

This matches the theoretical picture [Rosvall and Bergstrom, 2011]. The network has dense intra-triangle flow, moderately dense intra-super-group flow (the unit-weight links joining a super-group’s triangles), and weak inter-super-group flow (the three 0.8 links). Nested codebooks capture those scales, but only where a codebook pays for itself: two super-groups earn an index codebook of their own, the third does not, and the hierarchical map equation lands on that ragged three-level tree because it is more compressed than a uniform three-level tree, a flat two-level partition, or a one-level description.

API pointers

All on Result: num_levels, num_top_modules, modules() (pass level=k, or level=-1 for the leaf level), and effective_num_modules(); see Reading the result. The engine option two_level=True restricts the search to two levels — leave it off for the full hierarchy.

Going deeper