@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

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

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

@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.

@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

@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

@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.

@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

@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.

@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.

@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

@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

@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

@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

@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.

@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
• Random Regular Graph

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

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

@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

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

Generates a random tree with specified graph type.

@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

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

@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

@spec sbm_with_labels(integer(), integer(), float(), float(), keyword()) ::
  {Yog.graph(), %{required(Yog.node_id()) => 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

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

Generates an SBM graph with specified graph type.

@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

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

Generates a Watts-Strogatz graph with specified graph type.

@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.