yog - v5.0.0

yog/generator/random

Stochastic graph generators for random graph models.

Random generators use randomness to model real-world networks with properties like scale-free distributions, small-world effects, and community structure.

Available Generators

GeneratorModelComplexityKey Property
erdos_renyi_gnpG(n, p)O(n²)Each edge with probability p
erdos_renyi_gnmG(n, m)O(m)Exactly m random edges
barabasi_albertPreferentialO(nm)Scale-free (power-law degrees)
watts_strogatzSmall-worldO(nk)High clustering + short paths
random_treeUniform treeO(n²)Uniformly random spanning tree

Quick Start

import yog/generator/random
import yog/model

pub fn main() {
  // Random network models
  let sparse = random.erdos_renyi_gnp(100, 0.05)      // Sparse random (p=5%)
  let exact = random.erdos_renyi_gnm(50, 100)         // Exactly 100 edges
  let scale_free = random.barabasi_albert(1000, 3)    // Scale-free network
  let small_world = random.watts_strogatz(100, 6, 0.1) // Small-world (10% rewire)
  let tree = random.random_tree(50)                   // Random spanning tree
}

Network Models Explained

Erdős-Rényi G(n, p)

Erdős-Rényi G(n, m)

Barabási-Albert (Preferential Attachment)

Watts-Strogatz (Small-World)

Random Tree

References

Values

barabasi_albert

</> 
pub fn barabasi_albert(n: Int, m: Int) -> model.Graph(Nil, Int)

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)

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

barabasi_albert_with_type

</> 
pub fn barabasi_albert_with_type(
  n: Int,
  m: Int,
  graph_type: model.GraphType,
) -> model.Graph(Nil, Int)

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

erdos_renyi_gnm

</> 
pub fn erdos_renyi_gnm(n: Int, m: Int) -> model.Graph(Nil, Int)

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)

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

erdos_renyi_gnm_with_type

</> 
pub fn erdos_renyi_gnm_with_type(
  n: Int,
  m: Int,
  graph_type: model.GraphType,
) -> model.Graph(Nil, Int)

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

erdos_renyi_gnp

</> 
pub fn erdos_renyi_gnp(n: Int, p: Float) -> model.Graph(Nil, Int)

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
let sparse = random.erdos_renyi_gnp(100, 0.05)

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

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

erdos_renyi_gnp_with_type

</> 
pub fn erdos_renyi_gnp_with_type(
  n: Int,
  p: Float,
  graph_type: model.GraphType,
) -> model.Graph(Nil, Int)

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

random_tree

</> 
pub fn random_tree(n: Int) -> model.Graph(Nil, Int)

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)
// 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

random_tree_with_type

</> 
pub fn random_tree_with_type(
  n: Int,
  graph_type: model.GraphType,
) -> model.Graph(Nil, Int)

Generates a random tree with specified graph type.

watts_strogatz

</> 
pub fn watts_strogatz(
  n: Int,
  k: Int,
  p: Float,
) -> model.Graph(Nil, Int)

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)

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

watts_strogatz_with_type

</> 
pub fn watts_strogatz_with_type(
  n: Int,
  k: Int,
  p: Float,
  graph_type: model.GraphType,
) -> model.Graph(Nil, Int)

Generates a Watts-Strogatz graph with specified graph type.

✨ Search Document