Erdős–Rényi Random Graphs

Status: placeholder — write lecture notes here before teaching.

Goals¶

• Graphs as data: adjacency matrix, degree sequence

• The model $G(n,p)$: each edge present independently with probability $p$

• Degree distribution (binomial, Poisson limit)

• First NetworkX experiments: sample $G(n,p)$, plot degrees

Outline¶

1. Motivation: social / web / citation networks

2. Definition of $G(n,p)$ and $G(n,m)$

3. Expected number of edges, expected degree

4. Degree distribution

5. Lab: NetworkX — generate graphs, compare empirical degrees to theory

Sources¶

• Blum, Hopcroft, Kannan, Foundations of Data Science, Ch. 7

• Lab notebooks in this folder: 1_Introduction.ipynb, 2_Fundamentals.ipynb