braintools.analysis.graph.characteristic_path_length

braintools.analysis.graph.characteristic_path_length#

braintools.analysis.graph.characteristic_path_length(conn, *, directed=True, n_sources=None, seed=None)#

Compute the characteristic path length and the global efficiency.

Shortest paths are counted in hops (the graph is treated as unweighted) with breadth-first search (scipy.sparse.csgraph.shortest_path):

\[L = \frac{1}{|R|} \sum_{(i, j) \in R} d_{ij}, \qquad E = \frac{1}{N (N - 1)} \sum_{i \neq j} \frac{1}{d_{ij}},\]

with \(R\) the reachable ordered pairs \(i \neq j\) [1] [2]. On a (strongly) connected graph these equal networkx.average_shortest_path_length and, for undirected graphs, networkx.global_efficiency. On a disconnected graph \(L\) is over reachable pairs only and \(E\) counts unreachable pairs as 0 (for a directed graph \(E\) is the directed generalisation [2]).

Parameters:

  • conn (Any) – Square connectivity, rows pre and columns post. Self-loops and weights are ignored.

  • directed (bool) – Follow edge directions, or treat the graph as undirected.

  • n_sources (int | None) – Number of source nodes, sampled uniformly without replacement, to estimate \(L\) and \(E\) on large graphs (cost \(O(n_{sources} (N + E))\) instead of \(O(N (N + E))\)). The sums then run over pairs whose source is in the sample. None (or a value >= N) uses every node, giving the exact values.

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

Returns:

Named tuple (path_length, efficiency, n_reachable, n_sources).

Return type:

PathLengthResult

Raises:

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

See also

small_world_index

Path length relative to random graphs.

Notes

Sources are processed in chunks so that each block of distances holds at most about \(2^{22}\) entries.

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 characteristic_path_length
>>> chain = np.array([[0, 1, 0], [0, 0, 1], [0, 0, 0]])  # 0 -> 1 -> 2
>>> result = characteristic_path_length(chain)
>>> result.path_length, result.n_reachable
(1.3333333333333333, 3)
>>> round(result.efficiency, 4)
0.4167
>>>
>>> characteristic_path_length(chain, directed=False).path_length
1.3333333333333333