braintools.analysis.graph.clustering_coefficient

braintools.analysis.graph.clustering_coefficient(conn, *, directed=True, weighted=False, average=True)

Compute the local clustering coefficient, or its average over nodes.

With directed=True this is Fagiolo’s directed clustering [1], which counts all eight kinds of directed triangles around node \(i\):

\[C_i = \frac{\left[(A + A^\top)^3\right]_{ii}} {2\left[d_i^{tot}(d_i^{tot} - 1) - 2 d_i^{\leftrightarrow}\right]},\]

with \(d^{tot}\) the in- plus out-degree and \(d^{\leftrightarrow}\) the number of reciprocated neighbours. With directed=False the graph is symmetrised and \(C_i = [A^3]_{ii} / (k_i (k_i - 1))\) [2]. Nodes with fewer than two neighbours have \(C_i = 0\).

With weighted=True the adjacency \(A\) is replaced by \(\hat W^{1/3}\), with \(\hat W = W / \max(W)\) (geometric mean of the triangle weights [3], signed cube root as networkx), while the degrees stay unweighted. The result matches networkx.clustering and networkx.average_clustering with the same directedness and weight='weight' / weight=None.

Parameters:

• conn (Any) – Square connectivity, rows pre and columns post. Self-loops are ignored (also in the weight normalisation, where networkx would include them).

• directed (bool) – Treat the graph as directed (Fagiolo) or undirected (symmetrised; the pair weight is the mean of the directions present).

• weighted (bool) – Use the edge weights. They are normalised by their maximum, so their unit cancels (a Quantity is accepted). The largest weight must be positive.

• average (bool) – Return the mean over all nodes (nodes with zero clustering included, as networkx.average_clustering) instead of the per-node array.

Returns:

The average clustering (nan for a graph with no nodes), or the per-node clustering of shape (N,).

Return type:

float | ndarray

Raises:

ValueError – If the connectivity is not square, or weighted=True and the largest weight is not positive.

See also

small_world_index

Clustering and path length relative to random graphs.

motif_counts

Directed triad census.

Notes

The diagonal of the matrix cube is computed as row sums of \((A A) \circ A^\top\) with sparse products evaluated in row chunks, so no dense \(N \times N\) array is formed. The cost is about the number of length-2 paths, \(\sum_k d_k^2\).

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

References

[1]

G. Fagiolo, “Clustering in complex directed networks,” Physical Review E 76, 026107 (2007).

[2]

D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature 393, 440-442 (1998).

[3]

J.-P. Onnela, J. Saramäki, J. Kertész and K. Kaski, “Intensity and coherence of motifs in weighted complex networks,” Physical Review E 71, 065103 (2005).

Examples

>>> import numpy as np
>>> from braintools.analysis.graph import clustering_coefficient
>>> triangle_plus_tail = np.array([[0, 1, 1, 0],
...                                [1, 0, 1, 0],
...                                [1, 1, 0, 1],
...                                [0, 0, 1, 0]])
>>> clustering_coefficient(triangle_plus_tail, directed=False, average=False)
array([1.        , 1.        , 0.33333333, 0.        ])
>>>
>>> round(clustering_coefficient(triangle_plus_tail, directed=False), 4)
0.5833