Metrics

Network structural analysis: clustering coefficients, triangle counting, and connectivity.

Clustering

clustering

Clustering coefficient and triangle counting for networks.

count_triangles

count_triangles(adjacency: SparseMatrix) -> int

Count the total number of triangles in an undirected network.

Uses the trace formula: triangles = trace(A³) / 6, where A is the adjacency matrix. Each triangle is counted 6 times (once per vertex and once per direction).

Parameters:

Name	Type	Description	Default
adjacency	SparseMatrix	Symmetric adjacency matrix (sparse or dense).	required

Returns:

Type	Description
int	Number of triangles in the network.

Example

from scipy.sparse import csr_matrix

Triangle: 0-1-2-0

adj = csr_matrix([[0, 1, 1], [1, 0, 1], [1, 1, 0]]) count_triangles(adj) 1

triangles_per_node

triangles_per_node(
    adjacency: SparseMatrix,
) -> NDArray[int_]

Count triangles incident to each node.

For node i, counts the number of triangles where i is a vertex. This equals (A³)_{ii} / 2 since each triangle at i is traversed in both directions.

Parameters:

Name	Type	Description	Default
adjacency	SparseMatrix	Symmetric adjacency matrix.	required

Returns:

Type	Description
NDArray[int_]	Array of length n with triangle counts per node.

Example

from scipy.sparse import csr_matrix

Triangle: 0-1-2-0, plus edge 0-3

adj = csr_matrix([ ... [0, 1, 1, 1], ... [1, 0, 1, 0], ... [1, 1, 0, 0], ... [1, 0, 0, 0] ... ]) triangles_per_node(adj) array([1, 1, 1, 0])

local_clustering

local_clustering(
    adjacency: SparseMatrix,
) -> NDArray[floating]

Compute local clustering coefficient for each node.

The local clustering coefficient C_i measures how close node i's neighbours are to forming a clique:

C_i = 2 * T_i / (k_i * (k_i - 1))

where T_i is the number of triangles containing i, and k_i is i's degree. Nodes with degree < 2 have clustering coefficient 0.

Parameters:

Name	Type	Description	Default
adjacency	SparseMatrix	Symmetric adjacency matrix.	required

Returns:

Type	Description
NDArray[floating]	Array of length n with clustering coefficients in [0, 1].

Example

from scipy.sparse import csr_matrix

Complete graph K3 (triangle)

adj = csr_matrix([[0, 1, 1], [1, 0, 1], [1, 1, 0]]) local_clustering(adj) array([1., 1., 1.])

global_clustering_coefficient

global_clustering_coefficient(
    adjacency: SparseMatrix,
) -> float

Compute the global clustering coefficient (transitivity).

Defined as the ratio of closed triplets (triangles × 3) to all connected triplets:

C = 3 * (number of triangles) / (number of connected triples)

This measures the overall tendency for nodes to cluster together.

Parameters:

Name	Type	Description	Default
adjacency	SparseMatrix	Symmetric adjacency matrix.	required

Returns:

Type	Description
float	Global clustering coefficient in [0, 1].

Example

from scipy.sparse import csr_matrix

Complete graph K4

adj = csr_matrix([ ... [0, 1, 1, 1], ... [1, 0, 1, 1], ... [1, 1, 0, 1], ... [1, 1, 1, 0] ... ]) global_clustering_coefficient(adj) 1.0

Connectivity

connectivity

Connected component analysis for sparse adjacency matrices.

MAX_CONNECTED_ATTEMPTS module-attribute

MAX_CONNECTED_ATTEMPTS = 1000

DisconnectedGraphError

Bases: RuntimeError

Raised when a generator fails to produce a connected graph.

is_connected

is_connected(adjacency: spmatrix) -> bool

Check whether an undirected graph forms a single connected component.

Parameters:

Name	Type	Description	Default
adjacency	spmatrix	Sparse adjacency matrix (symmetric, undirected).	required

Returns:

Type	Description
bool	True if the graph has exactly one connected component.