@spec barabasi_albert(integer(), integer()) :: 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()) :: Yog.graph()

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

@spec erdos_renyi_gnm(integer(), integer()) :: 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()) :: Yog.graph()

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

@spec erdos_renyi_gnp(integer(), float()) :: 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()) :: Yog.graph()

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

@spec random_regular(integer(), integer()) :: 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()) :: Yog.graph()

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

@spec random_tree(integer()) :: 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()) :: Yog.graph()

Generates a random tree with specified graph type.

@spec watts_strogatz(integer(), integer(), float()) :: 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()) ::
  Yog.graph()

Generates a Watts-Strogatz graph with specified graph type.