braintools.analysis.graph.small_world_index

braintools.analysis.graph.small_world_index#

braintools.analysis.graph.small_world_index(conn, *, n_random=10, n_sources=None, seed=None)#

Compute the small-world index \(\sigma\) against random graphs.

\[\sigma = \frac{C / C_r}{L / L_r},\]

with \(C\) the average clustering and \(L\) the characteristic path length of the undirected, unweighted view of the graph, and \(C_r\), \(L_r\) their means over n_random Erdős–Rényi graphs \(G(N, M)\) with the same numbers of nodes and edges [1]. \(\sigma > 1\) indicates a small-world network.

The reference is Erdős–Rényi with the same density, not the degree-preserving rewiring of networkx.sigma (whose Python edge swaps do not scale); for graphs with broad degree distributions the two references differ.

Parameters:

  • conn (Any) – Square connectivity; symmetrised, self-loops and weights ignored.

  • n_random (int) – Number of random reference graphs.

  • n_sources (int | None) – Number of sampled BFS sources for the path lengths (see characteristic_path_length()); None uses all nodes.

  • seed (None | int | Generator) – Seed of the random graphs and the source sampling.

Returns:

Named tuple (sigma, clustering, clustering_random, path_length, path_length_random). sigma is nan when a ratio is undefined (e.g. no triangles in the random graphs, or no edges).

Return type:

SmallWorldResult

Raises:

ValueError – If the connectivity is not square or n_random < 1.

See also

clustering_coefficient

The clustering \(C\).

characteristic_path_length

The path length \(L\).

Notes

Path lengths of disconnected graphs (real or random) are over reachable pairs, as in characteristic_path_length().

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 small_world_index
>>> n, k = 200, 6
>>> ring = np.zeros((n, n))
>>> for shift in range(1, k // 2 + 1):
...     ring[np.arange(n), (np.arange(n) + shift) % n] = 1
>>> result = small_world_index(ring + ring.T, n_random=3, seed=0)
>>> round(result.clustering, 2)
0.6
>>> bool(result.sigma > 1)
True