Skip to content

Configuration Model

The configuration model pipeline, including both the standard (unclustered) and clustered variants.

Top-level functions

configuration_model

Configuration model for network generation.

Generates random graphs with prescribed degree sequences. When a clustering coefficient (phi) is specified, the Clustered Configuration Model (CCM) is used to embed subgraph structure (triangles, K4 cliques).

The main entry points are:

configuration_model(degrees, phi=0.0, ...)
    Generate a graph from a degree sequence, optionally with clustering.

sample_network(n, pmf, max_degree, phi=0.0, ...)
    Sample degrees from a distribution and generate a graph.

sample_degree_sequence(n, pmf, max_degree, ...)
    Sample a degree sequence with guaranteed even sum.

configuration_model

configuration_model(
    degrees: NDArray[int_],
    phi: float = 0.0,
    rng: Generator | None = None,
    allow_self_loops: bool = False,
    allow_multi_edges: bool = False,
) -> csr_matrix

Generate a random graph with a prescribed degree sequence.

When phi is 0.0 (default), generates a standard configuration model graph using random stub-pairing. When phi > 0, uses the Clustered Configuration Model to embed triangles and K4 cliques for the target clustering.

Parameters:

Name Type Description Default
degrees NDArray[int_]

Degree sequence (length n, non-negative integers, even sum).

required
phi float

Target clustering coefficient in [0, 1]. Default 0.0 gives no clustering (standard configuration model).

0.0
rng Generator | None

Random generator for reproducibility.

None
allow_self_loops bool

If False (default), remove self-loops.

False
allow_multi_edges bool

If False (default), collapse multi-edges.

False

Returns:

Type Description
csr_matrix

Symmetric adjacency matrix in CSR format.

sample_network

sample_network(
    n: int,
    pmf: Callable[[NDArray[int_]], NDArray[floating]],
    max_degree: int,
    phi: float = 0.0,
    rng: Generator | None = None,
) -> csr_matrix

Generate a network with degrees sampled from a distribution.

Convenience function combining degree sampling with graph generation. Supports optional clustering via the phi parameter.

Parameters:

Name Type Description Default
n int

Number of nodes.

required
pmf Callable[[NDArray[int_]], NDArray[floating]]

Probability mass function P(D = k) for degrees.

required
max_degree int

Maximum degree to consider (truncates distribution).

required
phi float

Target clustering coefficient. Default 0.0 (no clustering).

0.0
rng Generator | None

Random generator for reproducibility.

None

Returns:

Type Description
csr_matrix

Symmetric adjacency matrix in CSR format.

sample_degree_sequence

sample_degree_sequence(
    n: int,
    pmf: Callable[[NDArray[int_]], NDArray[floating]],
    max_degree: int,
    rng: Generator | None = None,
) -> NDArray[int_]

Sample a degree sequence guaranteed to have even sum.

Uses conditional resampling: samples all degrees independently, then if the sum is odd, resamples one randomly chosen node from the parity-restricted distribution. This is unbiased and always completes in a single pass.

Parameters:

Name Type Description Default
n int

Number of nodes.

required
pmf Callable[[NDArray[int_]], NDArray[floating]]

Probability mass function P(D = k), vectorized over k. Should accept an array of degree values and return probabilities.

required
max_degree int

Maximum degree to consider (truncates distribution).

required
rng Generator | None

Random generator for reproducibility.

None

Returns:

Type Description
NDArray[int_]

Array of n degrees summing to an even number.

Example

Poisson(3) degree distribution

from scipy.stats import poisson rng = np.random.default_rng(42) degrees = sample_degree_sequence( ... 100, poisson(3).pmf, max_degree=20, rng=rng ... ) degrees.sum() % 2 0

Core utilities

core

Configuration model for generating random graphs with prescribed degree sequence.

sample_degree_sequence

sample_degree_sequence(
    n: int,
    pmf: Callable[[NDArray[int_]], NDArray[floating]],
    max_degree: int,
    rng: Generator | None = None,
) -> NDArray[int_]

Sample a degree sequence guaranteed to have even sum.

Uses conditional resampling: samples all degrees independently, then if the sum is odd, resamples one randomly chosen node from the parity-restricted distribution. This is unbiased and always completes in a single pass.

Parameters:

Name Type Description Default
n int

Number of nodes.

required
pmf Callable[[NDArray[int_]], NDArray[floating]]

Probability mass function P(D = k), vectorized over k. Should accept an array of degree values and return probabilities.

required
max_degree int

Maximum degree to consider (truncates distribution).

required
rng Generator | None

Random generator for reproducibility.

None

Returns:

Type Description
NDArray[int_]

Array of n degrees summing to an even number.

Example

Poisson(3) degree distribution

from scipy.stats import poisson rng = np.random.default_rng(42) degrees = sample_degree_sequence( ... 100, poisson(3).pmf, max_degree=20, rng=rng ... ) degrees.sum() % 2 0

edges_to_csr

edges_to_csr(
    rows: NDArray[int_],
    cols: NDArray[int_],
    num_nodes: int,
    allow_self_loops: bool = False,
    allow_multi_edges: bool = False,
) -> csr_matrix

Build a symmetric CSR adjacency matrix directly from one-directional edges.

Constructs CSR arrays via an argsort-based row ordering, bypassing COO intermediate allocation. Each edge (i, j) is stored in both directions.

Parameters:

Name Type Description Default
rows NDArray[int_]

Source node for each edge.

required
cols NDArray[int_]

Target node for each edge.

required
num_nodes int

Number of nodes in the graph.

required
allow_self_loops bool

If False, filter self-loops before construction.

False
allow_multi_edges bool

If False, collapse multi-edges to single edges.

False

Returns:

Type Description
csr_matrix

Symmetric adjacency matrix in CSR format.

configuration_model

configuration_model(
    degrees: NDArray[int_],
    rng: Generator | None = None,
    allow_self_loops: bool = False,
    allow_multi_edges: bool = False,
) -> csr_matrix

Generate a random graph with a prescribed degree sequence.

Uses the configuration model: creates stubs for each node according to its degree, then randomly pairs stubs to form edges.

Parameters:

Name Type Description Default
degrees NDArray[int_]

Degree sequence (length n array of non-negative integers). Sum must be even.

required
rng Generator | None

Optional random generator for reproducibility.

None
allow_self_loops bool

If False, remove self-loops from the result.

False
allow_multi_edges bool

If False, collapse multi-edges to single edges.

False

Returns:

Type Description
csr_matrix

Adjacency matrix in CSR format.

Raises:

Type Description
ValueError

If degree sum is odd (impossible to pair all stubs).

Example

degrees = np.array([2, 2, 2, 2]) # 4-cycle possible adj = configuration_model(degrees, rng=np.random.default_rng(42)) adj.sum(axis=1).A1 # Realized degrees array([2, 2, 2, 2])

Clustered configuration model

clustered

Clustered Configuration Model (CCM) for networks with prescribed clustering.

Implements the algorithm from Ritchie et al. (2014) "Higher-order structure and epidemic dynamics in clustered networks", Journal of Theoretical Biology.

The CCM generates random graphs with a prescribed degree sequence AND a target clustering coefficient by explicitly constructing triangle AND K4 (complete square) motifs. This is crucial because K4 cliques contain 4 triangles each, contributing significantly to clustering.

clustered_configuration_model

clustered_configuration_model(
    degrees: NDArray[int_],
    phi: float = 0.0,
    rng: Generator | None = None,
    allow_self_loops: bool = False,
    allow_multi_edges: bool = False,
) -> csr_matrix

Generate a random graph with prescribed degree sequence and clustering.

Implements the Clustered Configuration Model (CCM) from Ritchie et al. (2014) which constructs networks by explicitly forming triangle AND K4 (complete square) motifs. K4 cliques are essential because each contains 4 triangles.

For homogeneous degree-5 networks (the paper's focus): - φ=0.2: 50% of nodes get (1 K4 + 1 triangle), 50% get 5 single edges - φ=0.4: All nodes get (1 K4 + 1 triangle)

Parameters:

Name Type Description Default
degrees NDArray[int_]

Degree sequence (length n array of non-negative integers). Sum must be even. Currently optimized for homogeneous degree-5.

required
phi float

Target clustering coefficient in [0, 1]. For degree-5 networks, maximum achievable is ~0.4 without overlapping motifs.

0.0
rng Generator | None

Optional random generator for reproducibility.

None
allow_self_loops bool

If False, remove self-loops from the result.

False
allow_multi_edges bool

If False, collapse multi-edges to single edges.

False

Returns:

Type Description
csr_matrix

Adjacency matrix in CSR format.

Raises:

Type Description
ValueError

If degree sum is odd or phi is out of range.

Example

degrees = np.full(100, 5, dtype=np.int_) # Homogeneous k=5 adj = clustered_configuration_model( ... degrees, phi=0.4, rng=np.random.default_rng(42) ... )

sample_clustered_network

sample_clustered_network(
    n: int,
    pmf: Callable[[NDArray[int_]], NDArray[floating]],
    max_degree: int,
    phi: float = 0.0,
    rng: Generator | None = None,
) -> csr_matrix

Generate a clustered network with degrees sampled from a distribution.

Convenience function that combines degree sampling with the CCM algorithm.

Parameters:

Name Type Description Default
n int

Number of nodes.

required
pmf Callable[[NDArray[int_]], NDArray[floating]]

Probability mass function P(D = k) for the degree distribution.

required
max_degree int

Maximum degree to consider.

required
phi float

Target clustering coefficient in [0, 1].

0.0
rng Generator | None

Optional random generator for reproducibility.

None

Returns:

Type Description
csr_matrix

Adjacency matrix in CSR format.

Example

from scipy.stats import poisson adj = sample_clustered_network( ... n=100, ... pmf=poisson(4).pmf, ... max_degree=20, ... phi=0.3, ... rng=np.random.default_rng(42) ... )

Stub partition

partition

Multinomial partitioning of stubs into corner types and singles.

Implements Step 2 of the CCM algorithm: partitioning allocated stubs into hyperstub bins for motif formation.

Reference

Ritchie et al. (2014) "Higher-order structure and epidemic dynamics in clustered networks", Journal of Theoretical Biology 348, 21-32.

StubPartition dataclass

StubPartition(
    corners: NDArray[int_],
    singles: NDArray[int_],
    corner_counts: NDArray[int_],
    single_counts: NDArray[int_],
)

Result of partitioning stubs into hyperstub bins.

Attributes:

Name Type Description
corners NDArray[int_]

Node IDs for corner hyperstubs. Each node i appears corner_counts[i] times, ready for connector algorithms.

singles NDArray[int_]

Node IDs for single-edge stubs. Each node i appears single_counts[i] times, for standard configuration model.

corner_counts NDArray[int_]

Per-node corner allocation (for diagnostics).

single_counts NDArray[int_]

Per-node single allocation (for diagnostics).

total_corners property

total_corners: int

Total corner count across all nodes.

total_singles property

total_singles: int

Total single stub count across all nodes.

MixedCardinalityError

Bases: ValueError

Raised when a motif has corners with different cardinalities.

The current implementation assumes uniform-cardinality motifs (e.g., triangles, complete graphs) following Ritchie et al. (2014). Support for mixed-cardinality motifs (e.g., G7/diamond, G14/bowtie) requires a more sophisticated allocation strategy.

partition_stubs

partition_stubs(
    stubs: NDArray[int_],
    motif: Motif,
    phi: float,
    rng: Generator,
) -> StubPartition

Multinomially partition stubs into corners and singles.

For each node with k stubs, probabilistically allocates corners based on phi. Each corner consumes cardinality stubs; remaining stubs become singles for standard configuration model pairing.

This implements Step 2 of the CCM algorithm from Ritchie et al. (2014), which assumes all motif corners have equal cardinality (i.e., fully connected subgraphs like triangles or complete graphs).

Parameters:

Name Type Description Default
stubs NDArray[int_]

Stub count per node (length n). Typically from prepare_stubs.

required
motif Motif

Motif defining corner structure. Must have uniform cardinality (all corners equivalent), e.g., G2 (triangle), G8 (K4), G29 (K5).

required
phi float

Clustering parameter in [0, 1]. Fraction of maximum possible corners to allocate on average. Higher values produce more clustered networks.

required
rng Generator

Random generator for reproducibility.

required

Returns:

Type Description
StubPartition

StubPartition containing hyperstub bins ready for connector algorithms.

Raises:

Type Description
MixedCardinalityError

If motif has corners with different cardinalities.

ValueError

If phi is outside [0, 1].

Note

The assumption of uniform cardinality follows the original CCM paper (Ritchie et al., 2014), which uses triangles exclusively. Extending to mixed-cardinality motifs requires coordinated allocation to maintain corner type ratios.

Example

from craeft.networks.generation.motifs import G2 from craeft.networks.generation.distributions import ( ... prepare_stubs, Poisson, ... ) rng = np.random.default_rng(42) stubs = prepare_stubs(Poisson(mu=6.0), n=100, rng=rng) partition = partition_stubs(stubs, G2, phi=0.5, rng=rng) partition.total_corners # Number of triangle corners allocated 150 partition.total_singles # Remaining stubs for single edges 300

Connectors

Strategies for forming motif instances from hyperstub arrays.

connectors

Hyperstub connection algorithms.

Three strategies with different speed/bias tradeoffs for forming motif instances from allocated hyperstubs.

Reference

Ritchie et al. (2015): "Generation and analysis of networks with a prescribed degree sequence and subgraph family"

Connector dataclass

Connector()

Bases: ABC

Base class for hyperstub connection algorithms.

A connector takes bins of hyperstubs (nodes allocated to participate in motif instances) and forms the actual edges by matching hyperstubs into complete motif instances.

connect abstractmethod

connect(
    hyperstubs: NDArray[int_], motif: Motif, rng: Generator
) -> tuple[NDArray[int_], NDArray[int_]]

Connect hyperstubs to form motif instances.

Parameters:

Name Type Description Default
hyperstubs NDArray[int_]

Array of node IDs, where each node appears once per hyperstub allocated to it. Length must be divisible by motif.num_nodes.

required
motif Motif

The motif structure to instantiate.

required
rng Generator

Random number generator.

required

Returns:

Type Description
NDArray[int_]

Tuple of (rows, cols) arrays representing edges. Each motif

NDArray[int_]

instance contributes motif.num_edges edges.

Repeated dataclass

Repeated(max_attempts: int = 1000)

Bases: Connector

Resample on collision until valid or exhausted.

Samples k hyperstubs at a time. If any node appears twice in the sample (a collision), discards and resamples. On success, removes those hyperstubs and continues until fewer than k remain.

Attributes:

Name Type Description
max_attempts int

Maximum consecutive failures before stopping.

connect

connect(
    hyperstubs: NDArray[int_], motif: Motif, rng: Generator
) -> tuple[NDArray[int_], NDArray[int_]]

Connect hyperstubs with resampling on collision.

Refuse dataclass

Refuse(max_attempts: int = 100)

Bases: Connector

Unbiased connection via rejection sampling.

Shuffles all hyperstubs and partitions into groups of k. If any group contains a collision (same node twice), rejects the entire batch and reshuffles. Guarantees uniform sampling from valid configurations.

Attributes:

Name Type Description
max_attempts int

Maximum batch rejections before giving up.

connect

connect(
    hyperstubs: NDArray[int_], motif: Motif, rng: Generator
) -> tuple[NDArray[int_], NDArray[int_]]

Connect hyperstubs with full batch rejection on collision.

Erased dataclass

Erased()

Bases: Connector

Fastest connection with post-hoc edge removal.

Shuffles hyperstubs and partitions into groups without collision checking. Forms all motif instances, then removes self-loops and duplicate edges. Fastest approach but produces biased output (high-degree nodes lose edges).

Use when speed is critical and slight bias is acceptable.

connect

connect(
    hyperstubs: NDArray[int_], motif: Motif, rng: Generator
) -> tuple[NDArray[int_], NDArray[int_]]

Connect hyperstubs and erase invalid edges post-hoc.

get_connector

get_connector(name: ConnectorName) -> Connector

Get a connector by name.

Parameters:

Name Type Description Default
name ConnectorName

One of "repeated", "refuse", or "erased".

required

Returns:

Type Description
Connector

Connector instance with default configuration.

Raises:

Type Description
ValueError

If name is not recognized.

Pairing

Strategies for pairing single (non-motif) stubs into edges.

pairing

Configuration model pairing for single stubs.

Implements Step 4 of the CCM algorithm: pairing remaining single stubs to form simple edges, while avoiding multi-edges with existing motif edges.

Three strategies with different speed/bias tradeoffs mirror the connector strategies in ccm/connectors.py.

Reference

Ritchie et al. (2014) "Higher-order structure and epidemic dynamics in clustered networks", Journal of Theoretical Biology 348, 21-32.

Pairer dataclass

Pairer()

Bases: ABC

Base class for single stub pairing algorithms.

A pairer takes single stubs and existing edges, then pairs stubs to form new edges while avoiding self-loops and multi-edges.

pair abstractmethod

pair(
    singles: NDArray[int_],
    existing_edges: set[tuple[int, int]],
    rng: Generator,
) -> PairingResult

Pair single stubs to form edges.

Parameters:

Name Type Description Default
singles NDArray[int_]

Array of node IDs, where each node appears once per single stub allocated to it.

required
existing_edges set[tuple[int, int]]

Set of edges already formed (from motifs). Each edge is a tuple (min_id, max_id) in canonical form.

required
rng Generator

Random number generator.

required

Returns:

Type Description
PairingResult

PairingResult containing formed edges and unpaired count.

PairingResult dataclass

PairingResult(
    rows: NDArray[int_], cols: NDArray[int_], unpaired: int
)

Result of pairing single stubs.

Attributes:

Name Type Description
rows NDArray[int_]

Source node IDs for each edge.

cols NDArray[int_]

Target node IDs for each edge.

unpaired int

Number of stubs that couldn't be paired.

num_edges property

num_edges: int

Number of edges formed.

Repeated dataclass

Repeated(max_attempts: int = 100)

Bases: Pairer

Resample individual pairs on collision until valid or exhausted.

For each consecutive pair in the shuffled stubs, checks validity. If invalid, swaps one stub with a random later position and retries.

Attributes:

Name Type Description
max_attempts int

Maximum retries per pair before skipping.

pair

pair(
    singles: NDArray[int_],
    existing_edges: set[tuple[int, int]],
    rng: Generator,
) -> PairingResult

Pair stubs with per-pair retry on collision.

Refuse dataclass

Refuse(max_attempts: int = 1000)

Bases: Pairer

Unbiased pairing via batch rejection sampling.

Shuffles all stubs and pairs consecutively. If any pair is invalid (self-loop or multi-edge), rejects the entire batch and reshuffles. Guarantees uniform sampling from valid configurations.

Attributes:

Name Type Description
max_attempts int

Maximum batch rejections before giving up.

pair

pair(
    singles: NDArray[int_],
    existing_edges: set[tuple[int, int]],
    rng: Generator,
) -> PairingResult

Pair stubs with full batch rejection on any collision.

Erased dataclass

Erased()

Bases: Pairer

Fastest pairing with post-hoc edge removal.

Shuffles stubs and pairs consecutively without collision checking. Then removes self-loops, multi-edges, and duplicates with existing edges. Fastest approach but produces biased output (high-degree nodes lose edges).

pair

pair(
    singles: NDArray[int_],
    existing_edges: set[tuple[int, int]],
    rng: Generator,
) -> PairingResult

Pair stubs and erase invalid edges post-hoc.

get_pairer

get_pairer(name: PairerName) -> Pairer

Get a pairer by name.

Parameters:

Name Type Description Default
name PairerName

One of "repeated", "refuse", or "erased".

required

Returns:

Type Description
Pairer

Pairer instance with default configuration.

Raises:

Type Description
ValueError

If name is not recognized.

pair_singles

pair_singles(
    singles: NDArray[int_],
    existing_edges: set[tuple[int, int]],
    rng: Generator,
    strategy: PairerName = "repeated",
) -> PairingResult

Pair single stubs to form edges using the specified strategy.

Convenience function that selects and applies a pairing strategy.

Parameters:

Name Type Description Default
singles NDArray[int_]

Array of node IDs (from StubPartition.singles).

required
existing_edges set[tuple[int, int]]

Edges already formed from motifs. Each edge should be in canonical form (min_id, max_id).

required
rng Generator

Random number generator.

required
strategy PairerName

Pairing strategy - "repeated", "refuse", or "erased".

'repeated'

Returns:

Type Description
PairingResult

PairingResult with formed edges and unpaired stub count.

Example

from craeft.networks.generation.configuration_model.partition import ( ... partition_stubs, ... ) from craeft.networks.generation.motifs import G2, Repeated rng = np.random.default_rng(42)

... after partition and motif connection ...

existing = {(0, 1), (1, 2), (0, 2)} # triangle edges singles = np.array([0, 1, 3, 3, 4, 4]) result = pair_singles(singles, existing, rng, strategy="repeated") result.num_edges 3

Assembly

assembly

Adjacency matrix assembly from edge lists.

Step 5 of the CCM algorithm: combine motif edges and single edges into a final sparse adjacency matrix.

Reference

Ritchie et al. (2014) "Higher-order structure and epidemic dynamics in clustered networks", Journal of Theoretical Biology 348, 21-32.

AssemblyResult dataclass

AssemblyResult(
    adjacency: csr_matrix,
    num_motif_edges: int,
    num_single_edges: int,
)

Final network from CCM assembly.

Attributes:

Name Type Description
adjacency csr_matrix

Sparse adjacency matrix (CSR format, symmetric).

num_motif_edges int

Edges contributed by motif instances.

num_single_edges int

Edges contributed by single stub pairing.

num_edges property

num_edges: int

Total edges in the network (undirected count).

assemble

assemble(
    num_nodes: int,
    motif_edges: tuple[NDArray[int_], NDArray[int_]],
    pairing: PairingResult,
) -> AssemblyResult

Assemble adjacency matrix from motif and single edges.

Combines edges from motif instances (Step 3) and single stub pairing (Step 4) into a sparse symmetric adjacency matrix. Removes any self-loops and collapses multi-edges.

Parameters:

Name Type Description Default
num_nodes int

Total nodes in the network.

required
motif_edges tuple[NDArray[int_], NDArray[int_]]

Tuple of (rows, cols) arrays from connector.connect().

required
pairing PairingResult

Result from pair_singles().

required

Returns:

Type Description
AssemblyResult

AssemblyResult containing the sparse adjacency matrix and

AssemblyResult

diagnostic edge counts.

Example

import numpy as np from craeft.networks.generation.configuration_model.pairing import ( ... PairingResult, ... ) motif_edges = (np.array([0, 0, 1]), np.array([1, 2, 2])) pairing = PairingResult( ... rows=np.array([3, 4]), ... cols=np.array([4, 5]), ... unpaired=0, ... ) result = assemble(6, motif_edges, pairing) result.num_edges 5