Generates a scale-free network using the Barabási-Albert model.

Creates a random graph with a power-law degree distribution (scale-free). New nodes preferentially attach to existing high-degree nodes (“rich get richer”).

Time Complexity: O(nm)

Example

// Scale-free network with 1000 nodes, each connecting to 3 existing nodes
let graph = random.barabasi_albert(1000, 3, seed: Some(42))

Properties

• Power-law degree distribution: P(k) ~ k^(-3)
• Hub nodes with very high degree
• Small-world properties

Use Cases

• Social network modeling
• Citation network analysis
• Web graph simulation

Generates a Barabási-Albert graph with specified graph type.

Generates a random graph with specified degree sequence using the configuration model.

Time Complexity: O(M) where M is total edges. Returns Ok(graph) or Error(Nil) if pairing fails after retries.

Generates a Degree-Corrected Stochastic Block Model (DCSBM).

Extends SBM with node-specific degree parameters, allowing more realistic degree distributions while preserving community structure.

Parameters:

• n - Number of nodes
• k - Number of communities
• p_in - Probability within community
• p_out - Probability between communities
• thetas - Custom degree parameters for each node (optional)

Time Complexity: O(n²)

Generates a DCSBM graph with specified graph type.

Generates a random graph using the Erdős-Rényi G(n, m) model.

Unlike G(n, p) which includes each edge independently with probability p, G(n, m) guarantees exactly m edges in the resulting graph.

Time Complexity: O(m) expected

Example

// Random graph with 50 nodes and exactly 100 edges
let graph = random.erdos_renyi_gnm(50, 100, seed: Some(42))

Properties

• Exactly m edges (unlike G(n,p) which has expected m edges)
• Uniform distribution over all graphs with n nodes and m edges

Use Cases

• Fixed edge count requirements
• Random graph benchmarking
• Testing with specific densities

Generates an Erdős-Rényi G(n, m) graph with specified graph type.

Generates a random graph using the Erdős-Rényi G(n, p) model.

Each possible edge is included independently with probability p. For undirected graphs, each unordered pair is considered once.

Time Complexity: O(n²)

Example

// Sparse random graph with seed for reproducibility
let sparse = random.erdos_renyi_gnp(100, 0.05, seed: Some(42))

// Dense random graph
let dense = random.erdos_renyi_gnp(50, 0.8, seed: None)

Properties

• Expected number of edges: p × n(n-1)/2 (undirected) or p × n(n-1) (directed)
• Phase transition at p = 1/n (giant component emerges)

Use Cases

• Random network modeling
• Percolation studies
• Average-case algorithm analysis

Generates an Erdős-Rényi G(n, p) graph with specified graph type.

Generates a Random Geometric Graph (RGG).

Nodes are placed uniformly at random in a unit square [0, 1] x [0, 1]. Edges are created between any two nodes if their Euclidean distance is less than or equal to radius.

Time Complexity: O(n²)

Example

let rgg = random.geometric(100, 0.15, seed: Some(42))
// 100 nodes, connected if distance <= 0.15

Generates a Geometric graph with specified graph type.

Generates a hierarchical SBM with nested communities.

Time Complexity: O(n²)

Generates an HSBM graph with specified graph type.

Generates a Kronecker graph using recursive expansion (via R-MAT).

Parameters:

• k - Number of iterations (2^k nodes)
• initiator - 2x2 probability matrix #(a, b, c, d)
• m - Desired number of edges

Time Complexity: O(m log n)

Generates a random d-regular graph on n nodes.

A d-regular graph has every node with exactly degree d. This implementation uses a configuration model approach with retries to ensure simplicity (no self-loops or parallel edges).

Preconditions:

• n × d must be even (required for any d-regular graph)
• d < n (cannot have degree >= number of nodes in simple graph)
• d >= 0

Properties:

• Uniform distribution over all d-regular graphs (approximate)
• Exactly n nodes, (n × d) / 2 edges
• All nodes have degree exactly d

Time Complexity: O(n × d)

Example

// Generate a 3-regular graph with 10 nodes
let regular = random.random_regular(10, 3, seed: Some(42))

Use Cases

• Testing algorithms that need uniform degree distribution
• Expander graph approximations
• Network models where degree is constrained

Generates a random d-regular graph with specified graph type.

Generates a uniformly random tree on n nodes.

Creates a tree by starting with node 0 and repeatedly connecting new nodes to random nodes already in the tree. This produces a uniform distribution over all labeled trees.

Time Complexity: O(n²) expected

Example

let tree = random.random_tree(50, seed: Some(42))
// Random tree with 50 nodes, 49 edges

Properties

• Exactly n-1 edges (tree property)
• Connected
• Acyclic
• Uniform distribution over all labeled trees

Use Cases

• Random spanning tree generation
• Tree algorithm testing
• Network topology generation
• Phylogenetic tree simulation

Generates a random tree with specified graph type.

Generates a random graph matching the degree sequence of a given graph.

Time Complexity: O(N + M)

Generates a random graph using the R-MAT (Recursive MATRIX) model.

R-MAT is a fast generator for graphs with scale-free and small-world properties. It recursively partitions the adjacency matrix into four quadrants with specified probabilities.

Parameters:

• n - Number of nodes (must be a power of 2)
• m - Number of edges
• probs - Quad probabilities #(a, b, c, d) that sum to 1.0

Default Probs: #(0.57, 0.19, 0.19, 0.05) - standard scale-free parameters.

Time Complexity: O(m log n)

Example

let rmat = random.rmat(1024, 5000, None, seed: Some(42))
// 1024 nodes (2^10), 5000 edges

Generates an R-MAT graph with specified graph type.

Generates a graph using the Stochastic Block Model (SBM).

Nodes are assigned to communities, and edges are added with probabilities depending on community membership (higher probability within communities).

Parameters

• n - Number of nodes
• k - Number of communities
• p_in - Probability of edge within community
• p_out - Probability of edge between communities

Example

let sbm = random.sbm(100, 4, 0.3, 0.05, seed: Some(42))
// 100 nodes, 4 communities, high intra-community connectivity

Generates an SBM graph with specified graph type.

Generates a small-world network using the Watts-Strogatz model.

Generates a graph with both high clustering (like regular lattices) and short path lengths (like random graphs). Starts with a ring lattice and rewires edges with probability p.

Time Complexity: O(nk)

Example

// Small-world network: 100 nodes, 6 neighbors each, 10% rewiring
let graph = random.watts_strogatz(100, 6, 0.1, seed: Some(42))

Properties

• High clustering coefficient
• Short average path length
• p=0: regular lattice, p=1: random graph

Use Cases

• Social network modeling (six degrees of separation)
• Neural network topology
• Epidemic spread modeling

Generates a Watts-Strogatz graph with specified graph type.