braintools.analysis.graph.motif_counts

Contents

braintools.analysis.graph.motif_counts#

braintools.analysis.graph.motif_counts(conn, *, max_wedges=100000000)#

Count the directed triad classes (triad census) and dyads.

Every unordered triple of nodes is classified into one of the 16 isomorphism classes of directed graphs on three nodes, named by the Holland–Leinhardt MAN code (numbers of mutual, asymmetric and null dyads, plus a letter for the orientation) [1]. The counts match networkx.triadic_census; the reciprocity matches networkx.reciprocity.

Parameters:

  • conn (Any) – Square connectivity, rows pre and columns post, treated as directed and unweighted. Self-loops are ignored by the triad and dyad census and counted as unreciprocated edges by the reciprocity (both as networkx).

  • max_wedges (int) – Size limit. The cost is dominated by the number of wedges (paths of length two in the undirected view), \(\sum_k d_k (d_k - 1)\) with \(d_k\) the number of neighbours of node \(k\). Graphs with more wedges raise instead of running for a long time; raise the limit to proceed anyway.

Returns:

Named tuple (triads, dyads, reciprocity).

Return type:

MotifCounts

Raises:

ValueError – If the connectivity is not square or has more than max_wedges wedges.

See also

clustering_coefficient

Directed clustering (Fagiolo).

Notes

The census is computed without enumerating triples. Triads with one connected dyad are counted per edge from the number of nodes adjacent to neither end; triads with two connected dyads per centre node from its in-, out- and mutual neighbour counts, minus the closed ones; and the seven closed classes from masked sparse products of the mutual and asymmetric adjacency matrices (e.g. 030C is \(\mathrm{tr}(S^3)/3\) with \(S\) the asymmetric part). 003 is the remainder of \(\binom{N}{3}\). Counts are exact integers.

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 motif_counts
>>> cycle = np.array([[0, 1, 0], [0, 0, 1], [1, 0, 0]])  # 0 -> 1 -> 2 -> 0
>>> result = motif_counts(cycle)
>>> result.triads['030C'], result.triads['003']
(1, 0)
>>> result.dyads
{'mutual': 0, 'asymmetric': 3, 'null': 0}
>>> result.reciprocity
0.0
Contents