infomap_partitions

infomap_partitions(G, *, weight='weight', seed=None, num_trials=1, teleportation_probability=0.15)

Return an iterator over the nested partitions of a multilevel Infomap hierarchy.

Infomap searches for a multilevel partition with the multilevel map equation [1], which gives every internal module its own index codebook rather than keeping a single one at the top. The hierarchy is computed when this function is called. The returned iterator exposes one flat partition per level, coarsest first.

The first partition contains the top-level modules. Each later partition refines the previous one, and the last contains the leaf modules. A branch without deeper submodules remains unchanged at later levels. This hierarchy is optimized separately from the two-level partition returned by infomap_communities().

Unlike louvain_partitions and leiden_partitions, which run from finer partitions to coarser ones, this function follows the Infomap hierarchy from its top modules down to its leaf modules.

Directed graphs use the unrecorded teleportation-to-links flow model described by map_equation() and require SciPy.

Parameters:

GGraph, DiGraph, MultiGraph, or MultiDiGraph

An undirected or directed first-order graph. Parallel edges are summed.

weightstring or None, optional (default=”weight”)

The name of an edge attribute holding the numerical weight. Higher weights represent stronger flow and make an edge more likely to be traversed; they should not represent distances or costs. Weights must be finite and non-negative. If None, or if an edge does not have the attribute, that edge has weight 1.

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

num_trialsint, optional (default=1)

Number of randomized searches. The hierarchy with the lowest codelength is returned. Runtime is approximately proportional to num_trials. Must be a positive integer.

teleportation_probabilityfloat, optional (default=0.15)

Teleportation probability for the directed-flow random walk, as in map_equation(). Ignored for undirected graphs. Values must lie in the interval [0, 1].

Returns:

iterator of list of sets of nodes

An iterator over the partitions of G, coarsest first. The sets in each partition are disjoint, cover every node, and have arbitrary order.

Raises:

ValueError

If num_trials is not a positive integer, if any edge weight is negative or not finite, if the weights are too large to sum as floats, or if a directed graph’s teleportation_probability is outside the interval [0, 1].

PowerIterationFailedConvergence

If PageRank fails to converge when computing directed flow.

See also

infomap_communities

map_equation()

louvain_partitions

Notes

With unchanged graph iteration order, a fixed seed reproduces the stochastic search. Increasing num_trials explores more candidate hierarchies but does not guarantee a global optimum.

Self-loops contribute to node visit rates and within-module flow, but never to boundary-crossing flow. They can therefore affect codelengths and the returned hierarchy.

A single level of one community is valid. It means that none of the hierarchies found compresses the flow better than the one-level baseline under the selected flow model.

map_equation() scores a flat partition under the two-level objective. It does not score the complete hierarchy returned here.

References

[1]

Rosvall, M. & Bergstrom, C.T. Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems. PLoS ONE 6(4), e18209 (2011). https://doi.org/10.1371/journal.pone.0018209

Examples

>>> G = nx.ring_of_cliques(12, 6)
>>> levels = list(nx.community.infomap_partitions(G, seed=0, num_trials=10))
>>> [len(level) for level in levels]
[3, 12]