map_equation

map_equation(G, communities, *, weight='weight', teleportation_probability=0.15)

Return the two-level map equation codelength of a partition of G.

The map equation [1] gives the theoretical lower bound on the average per-step codelength of a random walk on G under a two-level code: one index codebook over the modules, and one codebook per module over the nodes inside it plus an exit symbol. For the partition \(\mathsf{M}\) given by communities:

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

The index codebook is used at \(q_\curvearrowright\), the rate at which the walk changes module. Its entropy \(H(\mathcal{Q})\) is calculated from the module enter rates normalized by \(q_\curvearrowright\). Module \(i\)’s codebook is used at \(p^i_\circlearrowright\), its total node visit rate plus its exit rate. Its entropy \(H(\mathcal{P}^i)\) is calculated from the node visit rates and exit rate normalized by \(p^i_\circlearrowright\). The implementation evaluates the equivalent closed form as sums of \(x \log_2 x\).

The visit and transition rates the codebooks are built from, together called the flow, come from the walk itself. On an undirected graph a node’s rate is proportional to its weighted degree, \(p_\alpha = k_\alpha / 2m\). A directed graph uses Infomap’s default unrecorded teleportation-to-links flow model [2]. PageRank first supplies stationary node ranks; only a subsequent link-following step contributes to the recorded node visits and link flows. Computing directed flow requires SciPy.

Parameters:

GGraph, DiGraph, MultiGraph, or MultiDiGraph

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

communitieslist or iterable of set of nodes

A partition of the nodes of G.

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.

teleportation_probabilityfloat, optional (default=0.15)

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

Returns:

float

The average codelength in bits per random-walk step. Lower values mean better compression for partitions of the same graph under the same weight and teleportation_probability settings.

Raises:

NotAPartition

If communities is not a partition of the nodes of G.

ValueError

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

infomap_partitions

modularity

Notes

When evaluating a partition returned by infomap_communities(), pass the same weight and teleportation_probability values that were used for the search.

This function evaluates a flat partition under the two-level map equation. It does not evaluate the complete hierarchy returned by infomap_partitions().

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]

Lambiotte, R. & Rosvall, M. Ranking and clustering of nodes in networks with smart teleportation. Phys. Rev. E 85, 056107 (2012). https://doi.org/10.1103/PhysRevE.85.056107

Examples

Two triangles joined by a single edge, with one triangle per module:

>>> G = nx.barbell_graph(3, 0)
>>> nx.community.map_equation(G, [{0, 1, 2}, {3, 4, 5}])
2.3207303568337903

Coding the same walk with a single module costs more bits:

>>> nx.community.map_equation(G, [set(G)])
2.556656707462823