### Lectures

**Lecture 1**: Summary of topics discussed

- Practical course arrangements

- Definition: graph, adjacency matrix

- Representing graphs in computer memory

- Definition: random graph

- Uniform random graph with n nodes and m links

- Bernoulli graph with n nodes and link probability p

- Result: The probability that a large Bernoulli graph contains an isolated node converges to zero as n -> infinity and 0 < p < 1 is constant.

**Lecture 2**: Summary of topics discussed

- Stochastic slang: a.s., w.h.p.=a.a.s, i.i.d., w.pr.

- Asymptotic slang omega_n -> infty slowly

- 2nd moment method: Markov's and Chebyshev's inequalities

- Definition: Graph sequence, sequence of model with scale-dependent parameters

- Result: n^(-1) log n is a sharp threshold value for p=p_n for the connectivity of a large Bernoulli graph G_(n,p)

- Definition: Connected component, spanning tree, path equivalence class

**Lecture 3**: Summary of topics discussed

- Def: Inhomogeneous Bernoulli graph, stochastic block model, graphon

- Discussion: Community detection algorithms

- Def: Partial order, increasing function, upper set

- Def: Stochastic order on a general partially ordered space

- Def: Subgraph order

- Result: Strassen's coupling theorem

- Result: Stochastic ordering of inhomogeneous Bernoulli graphs

- Result: Connectivity of a random graph generated by a stochastic block model graphs

**Lecture 4**: Summary of topics discussed

- Def: Giant component

- Def: Galton-Watson branching process, offspring distribution, extinction, survival

- Result: Bernoulli graph admits a giant component when the limiting mean degree > 1, whereas all component are at most a constant times log n when the limiting mean degree < 1.

- Most of the long technical mathematical details of this lecture are skipped; they are available in [vdH, Chap 4] for the interested reader.

**Lecture 5**: Summary of topics discussed

- Def: Total variation distance, L

_{1}-distance, Hellinger distance

- Result: Coupling characterization and total variation distance and L

_{1}-distance

- Result: Total variation distance and hypothesis testing

- Result: Stochastic similarity of inhomogeneous Bernoulli graphs

**Lecture 6**: Summary of topics discussed

- Def: Degree distribution, joint degree distribution, empirical distribution

- Result: Mean degree in stochastic block models

- Def: Mixed Poisson distribution

- Result: Le Cam's inequality in Poisson approximation

- Result: Asymptotic independence of degrees in stochastic block models

**Lecture 7**: Summary of topics discussed

- Def: Graph isomorphism, automorphism, covering density, matching density

- Def: Subgraph, induced subgraph

- Result: Existence of R-isomorphic subgraphs for a sparse homogeneous Bernoulli graph

**: Summary of topics discussed**

Lecture 8

Lecture 8

- Maximum likelihood estimator of SBM parameters given node labeling

- Moment estimators of SBM parameters based on graphlet covering densities

**Lecture 9**: Summary of topics discussed

- Def: Strongly and weakly consistent estimator of the node labeling of an SBM

- Def: Hamming distance modulo label permutations

- Result: Existence of strongly and weakly consistent estimators (Mossel, Neeman, Sly 2016)

- Description of a the clustering algorithm of MSN16: spectral clustering, replica trick, hill climbing

9 Learning communities in stochastic block models.

For this lecture, there are no lecture notes. Instead, the lecture is based on the article

E Mossel, J Neeman, A Sly: Consistency thresholds for the planted bisection model, Electron J Probab 2016, https://projecteuclid.org/euclid.ejp/1457706457