braintools.analysis.graph.modularity

Contents

braintools.analysis.graph.modularity#

braintools.analysis.graph.modularity(conn, labels, *, directed=True, weighted=False, resolution=1.0)#

Compute the modularity of a given partition.

For a directed graph this is the Leicht–Newman modularity [1]

\[Q = \frac{1}{m} \sum_{ij} \left(A_{ij} - \gamma \frac{k_i^{out} k_j^{in}}{m}\right) \delta(c_i, c_j), \qquad m = \sum_{ij} A_{ij},\]

and for an undirected graph Newman’s modularity [2], the same expression on the symmetrised adjacency (where \(m\) is twice the number, or total weight, of edges and \(k^{out} = k^{in}\)). \(\gamma\) is the resolution. Matches networkx.community.modularity, including its treatment of self-loops.

Parameters:

  • conn (Any) – Square connectivity, rows pre and columns post. Self-loops are counted as in networkx: a directed self-loop adds its weight to the node’s in- and out-degree and to \(m\); in the undirected view it adds twice its weight to the node’s degree (\(A_{ii} = 2 w_{ii}\)).

  • labels (Any) – Community label of every node, shape (N,); any values that numpy.unique can sort (ints, strings, …).

  • directed (bool) – Leicht–Newman directed modularity, or Newman’s undirected modularity on the symmetrised graph.

  • weighted (bool) – Use the edge weights (which must be non-negative). The unit of Quantity weights cancels.

  • resolution (float) – Resolution \(\gamma\); smaller values favour larger communities.

Returns:

The modularity, or nan for a graph without edges.

Return type:

float

Raises:

ValueError – If the connectivity is not square, labels does not have one entry per node, or weighted=True with negative weights.

See also

clustering_coefficient

Local clustering.

Notes

Host-only (NumPy/SciPy): not traceable by jax.jit, jax.vmap or jax.grad.

References

Examples

>>> import numpy as np
>>> from braintools.analysis.graph import modularity
>>> two_pairs = np.array([[0, 1, 0, 0],
...                       [1, 0, 0, 0],
...                       [0, 0, 0, 1],
...                       [0, 0, 1, 0]])
>>> modularity(two_pairs, [0, 0, 1, 1])
0.5
>>> modularity(two_pairs, [0, 1, 0, 1], directed=False)
-0.5
Contents