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
|
singles |
NDArray[int_]
|
Node IDs for single-edge stubs. Each node i appears
|
corner_counts |
NDArray[int_]
|
Per-node corner allocation (for diagnostics). |
single_counts |
NDArray[int_]
|
Per-node single allocation (for diagnostics). |
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 |
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
¶
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
¶
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. |
Refuse
dataclass
¶
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. |
Erased
dataclass
¶
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.
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
¶
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
¶
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. |
Repeated
dataclass
¶
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
¶
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
¶
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
¶
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. |
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