Lectures

  • 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, L1-distance, Hellinger distance
    - Result: Coupling characterization and total variation distance and L1-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

    Lecture 8    : Summary of topics discussed
    - 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

Course home

Course home

Next section

Exercises►