# `Yog.Generator.Random`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/generator/random.ex#L1)

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

| Generator | Model | Complexity | Key Property |
|-----------|-------|------------|--------------|
| `erdos_renyi_gnp/2` | G(n, p) | O(n²) | Each edge with probability p |
| `erdos_renyi_gnm/2` | G(n, m) | O(m) | Exactly m random edges |
| `barabasi_albert/2` | Preferential | O(nm) | Scale-free (power-law degrees) |
| `watts_strogatz/3` | Small-world | O(nk) | High clustering + short paths |
| `random_tree/1` | Uniform tree | O(n²) | Uniformly random spanning tree |
| `random_regular/2` | d-regular | O(nd) | All nodes have degree d |

## Quick Start (Not Doctests - Random Output)

    # Random network models (output varies due to randomness)
    # sparse = Yog.Generator.Random.erdos_renyi_gnp(100, 0.05)      # Sparse random (p=5%)
    # exact = Yog.Generator.Random.erdos_renyi_gnm(50, 100)         # Exactly 100 edges
    # scale_free = Yog.Generator.Random.barabasi_albert(1000, 3)    # Scale-free network
    # small_world = Yog.Generator.Random.watts_strogatz(100, 6, 0.1) # Small-world (10% rewire)
    # tree = Yog.Generator.Random.random_tree(50)                   # Random spanning tree

## Network Models Explained

### Erdős-Rényi G(n, p)
- Each possible edge included independently with probability p
- Expected edges: p × n(n-1)/2 (undirected) or p × n(n-1) (directed)
- Phase transition at p = 1/n (giant component emerges)
- **Use for**: Random network modeling, percolation studies

### Erdős-Rényi G(n, m)
- Exactly m edges added uniformly at random
- Uniform distribution over all graphs with n nodes and m edges
- **Use for**: Fixed edge count requirements, specific density testing

### Barabási-Albert (Preferential Attachment)
- Starts with m₀ nodes, adds nodes connecting to m existing nodes
- New nodes prefer high-degree nodes ("rich get richer")
- Power-law degree distribution: P(k) ~ k^(-3)
- **Use for**: Social networks, citation networks, web graphs

### Watts-Strogatz (Small-World)
- Starts with ring lattice (high clustering)
- Rewires edges with probability p (creates shortcuts)
- Balances local clustering with global connectivity
- **Use for**: Social networks, neural networks, epidemic modeling

### Random Tree
- Builds tree by connecting new nodes to random existing nodes
- Produces uniform distribution over all labeled trees
- **Use for**: Spanning trees, hierarchical structures

## References

- [Erdős-Rényi Model](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model)
- [Barabási-Albert Model](https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model)
- [Watts-Strogatz Model](https://en.wikipedia.org/wiki/Watts%E2%80%93Strogatz_model)
- [Scale-Free Networks](https://en.wikipedia.org/wiki/Scale-free_network)
- [Small-World Network](https://en.wikipedia.org/wiki/Small-world_network)

# `barabasi_albert`

```elixir
@spec barabasi_albert(integer(), integer(), integer() | nil) :: Yog.graph()
```

Generates a scale-free graph using the Barabási-Albert preferential attachment model.

Starts with m nodes and adds n-m new nodes. Each new node connects to m existing
nodes with probability proportional to their degree ("rich get richer").

**Time Complexity:** O(nm)

## Examples

    iex> ba = Yog.Generator.Random.barabasi_albert(20, 2)
    iex> Yog.Model.order(ba)
    20

## Properties

- Power-law degree distribution: P(k) ~ k^(-3)
- Scale-free: no characteristic node degree
- High degree nodes (hubs) emerge naturally

## Use Cases

- Social networks
- Citation networks
- Web graphs
- Biological networks

# `barabasi_albert_with_type`

```elixir
@spec barabasi_albert_with_type(
  integer(),
  integer(),
  Yog.graph_type(),
  integer() | nil
) :: Yog.graph()
```

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

# `configuration_model`

```elixir
@spec configuration_model(
  [integer()],
  keyword()
) :: {:ok, Yog.graph()} | {:error, term()}
```

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

Creates a random graph where each node has exactly the degree specified,
using the stub-matching (configuration model) approach.

## Parameters
  - `degrees` - List of desired degrees for each node [d1, d2, ..., dn]

## Options
  - `:seed` - Random seed for reproducibility
  - `:allow_multiedges` - Allow parallel edges (default: false)
  - `:allow_selfloops` - Allow self-loops (default: false)
  - `:max_retries` - Maximum attempts to create simple graph (default: 100)

## Returns
  `{:ok, graph}` on success, `{:error, reason}` if impossible or retries exceeded

## Examples

    iex> # Create graph with specific degree sequence
    ...> degrees = [3, 3, 2, 2, 2]
    ...> {:ok, g} = Yog.Generator.Random.configuration_model(degrees)
    iex> Yog.Model.order(g)
    5

## Algorithm

1. Create stubs: For each node i, create d_i "half-edges"
2. Random matching: Randomly pair up all stubs
3. Form edges: Each pair of stubs becomes an edge

For simple graphs (no self-loops or multi-edges), the algorithm rejects
invalid configurations and retries up to max_retries.

# `dcsbm`

```elixir
@spec dcsbm(integer(), integer(), float(), float(), keyword()) :: Yog.graph()
```

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

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

## Options
  - `:degree_dist` - Degree distribution: `:power_law`, `:poisson`, or custom list
  - `:gamma` - Power-law exponent (default: 2.5)
  - `:seed` - Random seed
  - `:community_sizes` - List of community sizes (must sum to `n`)

## Examples

    iex> dcsbm = Yog.Generator.Random.dcsbm(100, 3, 0.3, 0.02,
    ...>   degree_dist: :power_law, gamma: 2.5)
    iex> Yog.Model.order(dcsbm)
    100

# `erdos_renyi_gnm`

```elixir
@spec erdos_renyi_gnm(integer(), integer(), integer() | nil) :: Yog.graph()
```

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

Exactly m edges are added uniformly at random from all possible edges.

**Time Complexity:** O(m)

## Examples

    iex> graph = Yog.Generator.Random.erdos_renyi_gnm(10, 15)
    iex> Yog.Model.order(graph)
    10

## Properties

- Uniform distribution over all graphs with n nodes and m edges
- Fixed edge count (unlike G(n,p) which has random edge count)

## Use Cases

- Fixed edge count requirements
- Specific density testing
- Comparative studies

# `erdos_renyi_gnm_with_type`

```elixir
@spec erdos_renyi_gnm_with_type(
  integer(),
  integer(),
  Yog.graph_type(),
  integer() | nil
) :: Yog.graph()
```

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

# `erdos_renyi_gnp`

```elixir
@spec erdos_renyi_gnp(integer(), float(), integer() | nil) :: Yog.graph()
```

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

## Examples

    iex> # Generate a sparse random graph (output varies)
    ...> sparse = Yog.Generator.Random.erdos_renyi_gnp(10, 0.3)
    iex> Yog.Model.order(sparse)
    10
    iex> # Generate a denser random graph
    ...> dense = Yog.Generator.Random.erdos_renyi_gnp(5, 0.8)
    iex> Yog.Model.order(dense)
    5

## 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`

```elixir
@spec erdos_renyi_gnp_with_type(integer(), float(), Yog.graph_type(), integer() | nil) ::
  Yog.graph()
```

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

# `geometric`

```elixir
@spec geometric(
  integer(),
  keyword()
) :: Yog.graph()
```

Generates a random geometric graph in 2D unit square.

Nodes are placed uniformly at random in [0,1]×[0,1], and edges connect
nodes within distance r.

## Options
  - `:radius` or `:r` - Connection threshold distance (default: 0.1)
  - `:seed` - Random seed for reproducibility
  - `:metric` - Distance metric: `:euclidean` (default) or `:manhattan`
  - `:periodic` - Whether to use periodic boundary conditions (torus, default: false)

## Examples

    iex> # Dense network with large radius
    ...> dense = Yog.Generator.Random.geometric(100, radius: 0.3)
    iex> Yog.Model.order(dense)
    100

    iex> # Sparse network with small radius
    ...> sparse = Yog.Generator.Random.geometric(100, radius: 0.05)
    iex> Yog.Model.order(sparse)
    100

## References

- Penrose, M. "Random Geometric Graphs." Oxford University Press, 2003.

# `geometric_nd`

```elixir
@spec geometric_nd(
  integer(),
  keyword()
) :: Yog.graph()
```

Generates a random geometric graph in d-dimensional unit hypercube.

## Options
  - `:dimensions` or `:d` - Number of dimensions (default: 2)
  - `:radius` - Connection threshold (default: 0.1)
  - `:seed` - Random seed

## Examples

    iex> # 3D spatial network
    ...> net3d = Yog.Generator.Random.geometric_nd(100, dimensions: 3, radius: 0.2)
    iex> Yog.Model.order(net3d)
    100

# `hsbm`

```elixir
@spec hsbm(
  integer(),
  keyword()
) :: Yog.graph()
```

Generates a hierarchical SBM with nested communities.

## Options
  - `:levels` - Number of hierarchy levels (default: 2)
  - `:branching` - Branching factor at each level (default: 2)
  - `:p_in` - Probability within leaf communities (default: 0.3)
  - `:p_out` - Probability between root communities (default: 0.01)
  - `:probs` - Explicit probability list of length `levels + 1`
  - `:seed` - Random seed

## Examples

    iex> hsbm = Yog.Generator.Random.hsbm(80,
    ...>   levels: 2, branching: 2, p_in: 0.4, p_mid: 0.1, p_out: 0.01)
    iex> Yog.Model.order(hsbm)
    80

# `kronecker`

```elixir
@spec kronecker(integer(), [[float()]], keyword()) :: Yog.graph()
```

Generates a Kronecker graph using recursive expansion.

Starting from a small initiator matrix, recursively expands using Kronecker
multiplication to create a graph with realistic properties like power-law
degree distributions, small diameter, and high clustering.

## Parameters
  - `k` - Number of recursive iterations (results in 2^k nodes)
  - `initiator` - 2×2 probability matrix [[a, b], [c, d]]

## Options
  - `:n_edges` - Target number of edges (default: estimated from probabilities)
  - `:seed` - Random seed
  - `:directed` - Whether graph should be directed (default: true)

## Examples

    iex> # Standard Kronecker initiator
    ...> initiator = [[0.9, 0.5], [0.5, 0.1]]
    ...> kron = Yog.Generator.Random.kronecker(4, initiator)
    iex> Yog.Model.order(kron)
    16

    iex> # Undirected version
    ...> initiator = [[0.9, 0.5], [0.5, 0.1]]
    ...> kron = Yog.Generator.Random.kronecker(3, initiator, directed: false)
    iex> Yog.Model.order(kron)
    8

## References

- Leskovec et al., "Kronecker graphs: An approach to modeling networks", JMLR 2010

# `kronecker_general`

```elixir
@spec kronecker_general(integer(), [[float()]], keyword()) :: Yog.graph()
```

Generates a Kronecker graph with a larger initiator matrix.

Supports 3×3 or larger initiators for more complex community structure.

## Parameters
  - `k` - Number of iterations (results in n^k nodes where n is initiator size)
  - `initiator` - n×n initiator matrix

## Options
  - `:seed` - Random seed
  - `:directed` - Whether graph should be directed (default: true)

## Examples

    iex> # 3x3 initiator for 3-community structure (use k=1 for simplicity)
    ...> init_3x3 = [[0.8, 0.3, 0.2], [0.3, 0.6, 0.2], [0.2, 0.2, 0.5]]
    ...> kron3 = Yog.Generator.Random.kronecker_general(1, init_3x3)
    iex> Yog.Model.order(kron3)
    3

# `power_law_graph`

```elixir
@spec power_law_graph(
  integer(),
  keyword()
) :: {:ok, Yog.graph()} | {:error, term()}
```

Generates a random graph with power-law degree distribution.

Creates a graph with degrees following a power law P(k) ~ k^(-gamma),
using the configuration model approach.

## Options
  - `:gamma` - Power-law exponent (default: 2.5, must be > 2)
  - `:k_min` - Minimum degree (default: 1)
  - `:k_max` - Maximum degree (default: n-1)
  - `:seed` - Random seed
  - `:max_retries` - Maximum attempts (default: 100)

## Examples

    iex> # Generate with fixed seed for reproducibility
    ...> result = Yog.Generator.Random.power_law_graph(50, gamma: 2.5, seed: 42)
    ...> case result do
    ...>   {:ok, pl} -> Yog.Model.order(pl)
    ...>   {:error, _} -> 0  # May fail due to retries
    ...> end
    50

## Notes

The power-law distribution is generated using the configuration model,
which differs from the Barabási-Albert preferential attachment model.
This approach generates the degree sequence first, then randomizes connections.

For gamma > 2, the expected degree is finite and the graph is well-defined.

# `random_regular`

```elixir
@spec random_regular(integer(), integer(), integer() | nil) :: Yog.graph()
```

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

## Examples

    iex> # Generate a 3-regular graph with 10 nodes
    ...> reg = Yog.Generator.Random.random_regular(10, 3)
    iex> Yog.Model.order(reg)
    10
    iex> # Every node has degree 3
    ...> degrees = for v <- 0..9, do: length(Yog.neighbors(reg, v))
    iex> Enum.all?(degrees, fn d -> d == 3 end)
    true
    iex> # Total edges = n*d/2 = 15
    ...> Yog.Model.edge_count(reg)
    15

## Algorithm

Uses a configuration model:
1. Create d "stubs" for each of the n nodes
2. Randomly pair stubs to form edges
3. Reject and retry if self-loops or parallel edges form

## Use Cases

- Testing algorithms that need uniform degree distribution
- Expander graph approximations
- Network models where degree is constrained
- Comparison with scale-free networks

## References

- [Configuration Model](https://en.wikipedia.org/wiki/Configuration_model)
- [Random Regular Graph](https://en.wikipedia.org/wiki/Random_regular_graph)

# `random_regular_with_type`

```elixir
@spec random_regular_with_type(
  integer(),
  integer(),
  Yog.graph_type(),
  integer() | nil
) :: Yog.graph()
```

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

# `random_tree`

```elixir
@spec random_tree(integer(), integer() | nil) :: Yog.graph()
```

Generates a uniformly random tree on n nodes.

Each labeled tree has equal probability of being generated.

**Time Complexity:** O(n²)

## Examples

    iex> tree = Yog.Generator.Random.random_tree(10)
    iex> Yog.Model.order(tree)
    10
    iex> # A tree has exactly n-1 edges
    ...> Yog.Model.edge_count(tree)
    9

## Properties

- Exactly n-1 edges
- Connected and acyclic
- Uniform distribution over all labeled trees

## Use Cases

- Spanning trees
- Hierarchical structures
- Network design

# `random_tree_with_type`

```elixir
@spec random_tree_with_type(integer(), Yog.graph_type(), integer() | nil) ::
  Yog.graph()
```

Generates a random tree with specified graph type.

# `randomize_degree_sequence`

```elixir
@spec randomize_degree_sequence(
  Yog.graph(),
  keyword()
) :: {:ok, Yog.graph()} | {:error, term()}
```

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

Creates a randomized version of the input graph with the same degree
sequence but random connections (configuration model applied to observed degrees).

## Options
  - `:seed` - Random seed for reproducibility
  - `:max_retries` - Maximum attempts (default: 100)

## Examples

    iex> original = Yog.Generator.Classic.star(5)
    ...> {:ok, randomized} = Yog.Generator.Random.randomize_degree_sequence(original)
    iex> Yog.Model.order(randomized)
    5

## Use Cases

- Null models in network analysis
- Degree-preserving randomization
- Testing which network properties are explained by degree sequence alone

# `rmat`

```elixir
@spec rmat(integer(), integer(), float(), float(), float(), float(), keyword()) ::
  Yog.graph()
```

Generates a Kronecker graph using the fast R-MAT (Recursive Matrix) algorithm.

The R-MAT algorithm generates Kronecker graphs in O(E × log V) time instead
of O(V²), making it scalable to billions of edges. Used in the Graph500 benchmark.

## Parameters
  - `n_nodes` - Number of nodes (must be power of 2)
  - `n_edges` - Number of edges to generate
  - `a, b, c, d` - Probabilities for the four quadrants (should sum to 1.0)

## Options
  - `:seed` - Random seed
  - `:noise` - Add small noise to probabilities to avoid self-loops (default: true)
  - `:undirected` - Make undirected by symmetrizing (default: false)

## Examples

    iex> # Standard R-MAT parameters (creates hub structure)
    ...> rmat = Yog.Generator.Random.rmat(1024, 8192, 0.45, 0.15, 0.15, 0.25)
    iex> Yog.Model.order(rmat)
    1024

    iex> # Undirected version
    ...> undir = Yog.Generator.Random.rmat(512, 2048, 0.5, 0.2, 0.2, 0.1,
    ...>   undirected: true)
    iex> Yog.Model.order(undir)
    512

## References

- Chakrabarti et al., "R-MAT: A recursive model for graph mining", SDM 2004
- Graph500 benchmark: https://graph500.org/

# `sbm`

```elixir
@spec sbm(integer(), integer(), float(), float(), keyword()) :: Yog.graph()
```

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

## Options
  - `:seed` - Random seed for reproducibility
  - `:community_sizes` - List of community sizes (must sum to `n`)
  - `:balanced` - Whether to use equal-sized communities (default: `true`)

## Examples

    iex> sbm = Yog.Generator.Random.sbm(100, 4, 0.3, 0.05)
    iex> Yog.Model.order(sbm)
    100

# `sbm_with_labels`

```elixir
@spec sbm_with_labels(integer(), integer(), float(), float(), keyword()) ::
  {Yog.graph(), %{required(Yog.node_id()) =&gt; integer()}}
```

Returns the SBM graph along with community assignments.

## Examples

    iex> {_graph, communities} = Yog.Generator.Random.sbm_with_labels(100, 4, 0.3, 0.05)
    iex> map_size(communities)
    100
    iex> communities[0] in 0..3
    true

# `sbm_with_labels_and_type`

```elixir
@spec sbm_with_labels_and_type(
  integer(),
  integer(),
  float(),
  float(),
  Yog.graph_type(),
  keyword()
) :: {Yog.graph(), %{required(Yog.node_id()) =&gt; integer()}}
```

# `sbm_with_type`

```elixir
@spec sbm_with_type(
  integer(),
  integer(),
  float(),
  float(),
  Yog.graph_type(),
  keyword()
) :: Yog.graph()
```

Generates an SBM graph with specified graph type.

# `watts_strogatz`

```elixir
@spec watts_strogatz(integer(), integer(), float(), integer() | nil) :: Yog.graph()
```

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

Starts with a ring lattice where each node connects to k nearest neighbors.
Then rewires each edge with probability p to create shortcuts.

**Time Complexity:** O(nk)

## Examples

    iex> ws = Yog.Generator.Random.watts_strogatz(20, 4, 0.1)
    iex> Yog.Model.order(ws)
    20

## Properties

- High clustering coefficient (like regular lattice)
- Short average path length (like random graph)
- Tunable with p: p=0 is regular, p=1 is random

## Use Cases

- Social networks
- Neural networks
- Epidemic modeling
- Power grids

# `watts_strogatz_with_type`

```elixir
@spec watts_strogatz_with_type(
  integer(),
  integer(),
  float(),
  Yog.graph_type(),
  integer() | nil
) ::
  Yog.graph()
```

Generates a Watts-Strogatz graph with specified graph type.

# `waxman`

```elixir
@spec waxman(
  integer(),
  keyword()
) :: Yog.graph()
```

Generates a Waxman graph (distance-based probabilistic edges).

Unlike strict geometric graphs, Waxman graphs connect nodes with
probability decreasing with distance: P(u,v) = β × exp(-d(u,v)/(α×L))
where L is the maximum distance.

## Options
  - `:alpha` - Distance decay parameter (default: 0.1)
  - `:beta` - Edge probability scaling (default: 0.5)
  - `:seed` - Random seed

## Examples

    iex> wax = Yog.Generator.Random.waxman(50, alpha: 0.15, beta: 0.4)
    iex> Yog.Model.order(wax)
    50

## References

- Waxman, B. M. "Routing of multipoint connections." IEEE JSAC, 1988.

---

*Consult [api-reference.md](api-reference.md) for complete listing*