CoreSource checked

Erdos-Renyi Graph Generation

Generates a random graph by independently including possible edges with fixed probability.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Randomness & Sampling
Difficulty: Intermediate
Family: Random Graphs
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 5
Code example: Ready
Visualization: Ready

Overview

The Erdos-Renyi model creates graphs by flipping an independent random choice for each possible edge, or by choosing a fixed number of edges uniformly. It is a baseline model for studying random graph behavior.

Core Concepts

random graph generationrandom graphsrandom samplingrandomness sampling

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(V + E)

Average

O((V + E) log V)

Worst

O(V^2 + E)

Space

O(V + E)

When to Use

Use when independent edge probability is the desired graph model.
Use as a simple baseline before using richer network models.

When Not to Use

Avoid when degree distribution, clustering, or community structure must resemble real networks.
Avoid when edge independence is an unrealistic assumption for the experiment.

What It Does

Enumerates possible edges between nodes
Samples each edge independently or samples a fixed edge count
Returns a random graph instance

Use Cases

Random graph experiments and benchmarks
Testing graph algorithms under controlled density
Studying connectivity thresholds and component structure

Inputs

Vertex count n and model parameters (edge probability p, attachment count m, or degree sequence)
PRNG seed

Outputs

Sampled graph adjacency list G = (V, E)
Realized degree distribution and connectivity structure

Key Formulas (1)

Independent edge probability

P(edge(u,v)) = p

P(edge(u,v)) = p

Samples every possible edge independently with the same probability.

Pseudocode

1.Create n isolated nodes
2.For each allowed pair of nodes
3.Draw u uniformly from [0, 1)
4.Add the edge if u < p
5.Return the generated graph

Canonical Example

Input: n = 4 nodes, p = 0.5, seed = 7
Output: a random subset of the six possible undirected edges
Explanation: Each possible edge is included independently with probability 0.5.

Implementation Notes

Choose directed versus undirected and whether self-loops are allowed.
Use a fixed seed for repeatable tests.
For sparse graphs, sample edges without iterating every possible pair when performance matters.

Common Pitfalls

Confusing G(n, p) with G(n, m) changes the density model.
Using p values without considering n can make graphs almost empty or almost complete.
Uncontrolled random seeds make experiments hard to reproduce.