Welcome!

Plan for today:

• The Big Picture & Short Recap
  • §1 Motivation for random graphs
  • §2 Erdős–Rényi random graph
  • §3 Properties of $ER_n(\lambda / n)$ that are dicussed in chapter 4
• The supercritical regime of $ER_n(\lambda / n)$
  • §4 Intuition
  • §5 Law of large numbers
  • §6 Central limit theorem
  • §7$^{*}$ The discrete duality principle

§1 Motivation for random graphs

• model large and complex networks using
  • (1) local and (2) probabilistic rules
    1. lower conceptual overhead, "divide and conquer" principle
    2. give us the ability to describe complexity in nets
• study properties of these models
  • properties of large nets <-> limiting properties of their models
  • thus, we consider graph sequences and study properties of their limits

§2 Erdős–Rényi random graph

• the simplest imaginable model of a random network
• it has a phase transition in the size of the maximal connected component (when p varies)
  • simple but it still has some very interesting properties

• recall def. of $ER_n(p)$:
  • $n$ vertices
  • each pair of vertices is independently connected with a fixed prob. $p$
• hence, the degree of a vertex ~ $ Bin(n-1,p)$
• hereafter we consider $ER_n(\lambda / n)$ since:
  • we want the expected degree $(n-1)p$ to be constant for large $n$
  • i.e. with $p = \lambda / n$, we get $(n-1)p = \frac{(n-1)}{n} \lambda \approx \lambda$

§3 Properties of $ER_n(\lambda / n)$ that are dicussed in chapter 4

• we study connected components / the largest connected component
• connected components can be described as branching processes
  • B.P. have a phase transition
    • expected offspring $E[X] < 1$, then $\eta =$ extinction prob. $=1$
    • expected offspring $E[X] > 1$, then $\eta < 1$ i.e. the process survives with positive prob.

• connected components of $ER_n(\lambda / n)$ have a related phase transition
  • the subcritical regime: expected degree $\approx \lambda < 1$
    • connected components are small, the largest of order $log(n)$ i.e. we have $$ \frac{|C_{\text{max}}|}{log(n)} \xrightarrow[]{P} \frac{1}{I_{\lambda}}$$
  • the supercritical regime: expected degree $\approx \lambda > 1$
    • simulation last time -> there is one giant connected component
    • Q: what can we prove in this setting?

-> Erdös-Rényi Random Graph, The supercritical regime notebook