---
title: Random Graphs
description: Random graphs study probability distributions over graphs. Learners will understand how network properties emerge as edges are added randomly, allowing them to model real-world networks like social systems and the internet.
category: mathematics
subcategory: graph-theory
difficulty: beginner, intermediate, advanced
url: /subject/random-graphs
---

# Random Graphs

Random graphs study probability distributions over graphs. Learners will understand how network properties emerge as edges are added randomly, allowing them to model real-world networks like social systems and the internet.

## Available Resources

4 Books • 3 Websites • 2 Papers

## Websites

### 1. Random Graphs and Complex Networks Notes

Free lecture notes by Remco van der Hofstad covering random graphs comprehensively.

**Difficulty:** Beginner | **Price:** Free

**Link:** https://www.win.tue.nl/~rhofstad/NotesRGCN.html

**Tags:** random-graphs, complex-networks, probability, erdos-renyi, configuration-model

### 2. Network Science (full online edition)

**Author:** Albert-László Barabási, Márton Pósfai

Interactive textbook, free from the author, whose chapters build the random network model and then break it: degree distributions, scale-free networks, the small-world property, robustness and percolation, each checked against real biological, social and technological network data.

**Difficulty:** Intermediate | **Language:** English | **Price:** Free

**Link:** https://networksciencebook.com/

**Tags:** network-science, scale-free-networks, random-networks, small-world-networks, network-robustness

### 3. Wolfram MathWorld

**Author:** Eric W. Weisstein

MathWorld is an online mathematics encyclopedia from Wolfram Research offering detailed, browsable articles on topics across the math spectrum, including algebra, geometry, calculus, and number theory. Each entry includes definitions, theorems, formulas, diagrams, worked examples, and links to further reading.

**Difficulty:** Intermediate | **Language:** English | **Price:** Free

**Link:** https://mathworld.wolfram.com

**Tags:** mathematics-reference, encyclopedia, abstract-algebra, number-theory, geometry

## Books

### 1. Networks (2nd Edition)

**Author:** Mark Newman

Comprehensive graduate textbook on network science covering how network data are gathered, centrality and structural measures, algorithms for large networks, random graph and configuration models, community detection, percolation and robustness, and epidemic and dynamical processes, with the underlying mathematics derived in full.

**Difficulty:** Intermediate | **Language:** English | **Price:** Paid

**Link:** https://www.amazon.com/dp/0198805098?tag=edmonddante07-20

**Tags:** network-science, random-graphs, percolation, epidemic-modeling, configuration-model

### 2. Introduction to Random Graphs

**Author:** Alan Frieze, Michał Karoński

Cambridge graduate text covering G(n,m) and G(n,p), thresholds, the phase transition and giant component, connectivity, Hamilton cycles, random regular graphs, and algorithmic applications. The authors host a continuously updated full PDF free at Carnegie Mellon.

**Difficulty:** Advanced | **Language:** English | **Price:** Free

**Link:** https://www.math.cmu.edu/users/af1p/BOOK.pdf

**Tags:** random-graphs, probabilistic-combinatorics, phase-transition, hamilton-cycles, graph-theory

### 3. Random Graphs

**Author:** Béla Bollobás

Second edition of the Cambridge monograph that systematized random graph theory: probability models, degree sequences, the evolution of random graphs and the giant component, connectivity, matchings, cliques, chromatic number, Hamilton cycles, and random regular graphs, with extensive references to the research literature.

**Difficulty:** Intermediate | **Language:** English | **Price:** Paid

**Link:** https://www.amazon.com/dp/0521797225?tag=edmonddante07-20

**Tags:** books, mathematics-statistics, graph-theory

### 4. Probabilistic Combinatorics and Its Applications

**Author:** Fan R. K. Chung

Lecture notes from a 1991 AMS short course edited by Béla Bollobás. Surveys of random graphs, martingale and isoperimetric inequalities, eigenvalue methods, branching processes and rapidly mixing Markov chains show how probabilistic arguments settle combinatorial problems.

**Difficulty:** Advanced | **Language:** English | **Price:** Paid

**Link:** https://www.amazon.com/dp/082185500X?tag=edmonddante07-20

**Tags:** probabilistic-combinatorics, random-graphs, probabilistic-method, markov-chains, martingale-inequalities

## Papers

### 1. A Random Walk Among Random Graphs

**Author:** Nicolas Curien

Master's-level lecture notes from Orsay whose central part gives three independent proofs that a giant component emerges in the Erdős–Rényi graph, approached via one-dimensional random walks, the cycle lemma and Bienaymé–Galton–Watson trees.

**Difficulty:** Advanced | **Language:** English | **Price:** Free

**Link:** https://arxiv.org/abs/2412.19752

**Tags:** random-graphs, erdos-renyi, giant-component, random-walks, galton-watson-trees

### 2. On the Evolution of Random Graphs (Erdős & Rényi, 1960)

**Author:** Paul Erdős, Alfréd Rényi

The 1960 paper that founded the field, tracking how G(n,M) changes as edges accumulate and identifying the sharp threshold at n/2 edges where a giant component of order n appears. Scanned original from Erdős's own archive.

**Difficulty:** Advanced | **Language:** English | **Price:** Free

**Link:** https://users.renyi.hu/~p_erdos/1960-10.pdf

**Tags:** random-graphs, erdos-renyi, phase-transition, giant-component, graph-theory

---

*This content is part of Dantes.io - Your Treasure Map to Knowledge*

*Curated by humans at Dantes.io. Personal study use welcome; republishing this curation requires permission (team@dantes.io).*

View this page online: https://dantes.io/subject/random-graphs