infomap_communities

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

Find communities in G with the two-level Infomap heuristic.

Infomap searches for a partition that compresses the flow of a random walk on G. The flow consists of the walk’s node-visit and link-transition rates. The map equation literature calls a community a module.

For a two-level partition \(\mathsf{M}\), the objective is the map equation [1] [2]:

\[L(\mathsf{M}) = q_\curvearrowright H(\mathcal{Q}) + \sum_i p^i_\circlearrowright H(\mathcal{P}^i)\]

The first term codes transitions between modules. The second codes node visits and module exits inside each module. Lower codelength means that the partition compresses the flow better. See map_equation() for the full definition.

This function runs num_trials randomized searches and returns the lowest-codelength partition found. infomap_partitions() optimizes the multilevel map equation separately [3], so this result is not guaranteed to match any level of its hierarchy.

Modularity, which louvain_communities and leiden_communities optimize, compares link weights against a null model rather than following flow, and can select a different partition on the same graph.

The search moves nodes between neighboring modules, aggregates modules, and applies Infomap’s fine- and coarse-tuning passes. 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 partition 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:

list of sets of nodes

The lowest-codelength two-level partition found across num_trials searches. The sets are disjoint and together contain every node of G. Their order is arbitrary.

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_partitions

map_equation()

louvain_communities

leiden_communities

Notes

The search is stochastic. With unchanged graph iteration order, a fixed seed reproduces its random choices. num_trials increases the search coverage without guaranteeing 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 partition.

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

References

[1]

Rosvall, M. & Bergstrom, C.T. Maps of random walks on complex networks reveal community structure. PNAS 105, 1118-1123 (2008). https://doi.org/10.1073/pnas.0706851105

[2]

Rosvall, M., Axelsson, D. & Bergstrom, C.T. The map equation. Eur. Phys. J. Special Topics 178, 13-23 (2009). https://doi.org/10.1140/epjst/e2010-01179-1

[3]

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.barbell_graph(5, 0)
>>> communities = nx.community.infomap_communities(G, seed=42, num_trials=10)
>>> sorted(map(sorted, communities))
[[0, 1, 2, 3, 4], [5, 6, 7, 8, 9]]