Lectures
Updates to lecture notes are announced separately.
The first lecture takes place on Mon 7 Sep 2020 at 12:15–14:00 online via Zoom (Meeting ID: 621 762 3715, https://aalto.zoom.us/j/6217623715
1 Graphs and random graphs
- FileL01-0 Introduction (14 min) FileVideo file (MP4)View
Overview of course contents and learning outcomes
- FileL01-2 Bernoulli random graphs (28 min) FileVideo file (MP4)View
Definition and probability distribution of a Bernoulli random graph
- FileL01-3 Random graph features (13 min) FileVideo file (MP4)View
Interesting events and random variables related to random graphs
2 Isolated nodes in Bernoulli random graphs
- FileL02-0 Introduction (4 min) FileVideo file (MP4)ViewExistence of isolated nodes in a Bernoulli random graph
- FileL02-1 Mean number of isolated nodes (20 min) FileVideo file (MP4)View
Mean number of isolated nodes in dense and sparse graphs.
- FileL02-2 Markov's inequality (4 min) FileVideo file (MP4)View
Markov's inequality related the mean and the tail of a distribution
- FileL02-3 Nonexistence of isolated nodes (4 min) FileVideo file (MP4)View
Nonexistence of isolated nodes in sufficiently dense graphs.
- FileL02-4 Existence of isolated nodes (9 min) FileVideo file (MP4)View
Existence of isolated nodes.
- FileL02-6 Second moment method (6 min) FileVideo file (MP4)View
Second moment method for proving that a random integer is strictly positive with high probability
- FileL02-7 Variance of isolated node count (16 min) FileVideo file (MP4)View
- FileL02-8 Connectivity threshold (15 min) FileVideo file (MP4)View
Connectivity threshold for Bernoulli random graphs
- FileL02-9 Simulation (1 min) FileVideo file (MP4)View
Simulated Bernoulli graphs below and above the critical threshold, for n=500.
3 Inhomogeneous Bernoulli graphs and stochastic ordering
- FileL03-2 Inhomogeneous Bernoulli graphs (16 min) FileVideo file (MP4)View
Inhomogeneous Bernoulli graphs, including latent position graph models as special cases, especially Erdös-Rényi graphs, stochastic block models, random intersection graphs, random geometric graphs, and graphons
- FileL03-3 Stochastic coupling method (22 min) FileVideo file (MP4)View
Stochastic coupling method, illustration for ordering tails of binomial random variables
- FileL03-4 Partial orders (8 min) FileVideo file (MP4)View
Partial orders, increasing functions, upper sets
- FileL03-5 Stochastic orders (15 min) FileVideo file (MP4)View
Stochastic orders and Strassen's coupling theorem
- FileL03-6 Subgraph order (13 min) FileVideo file (MP4)View
Subgraph order and monotone graph properties
- FileL03-7 Stochastic ordering of Bernoulli graphs (14 min) FileVideo file (MP4)View
Stochastic ordering of inhomogeneous Bernoulli graphs
- View
Connectivity of inhomogeneous Bernoulli graphs
4 Giant components
- FileBranching processes (8 min) FileVideo file (MP4)View
Branching processes and Galton-Watson trees
- FileGenerating functions (13 min) FileVideo file (MP4)View
Generating function of a probability distribution
- FilePopulation size generating function (6 min) FileVideo file (MP4)View
Generating function of the population size distribution at time t
- FileSure extinction (16 min) FileVideo file (MP4)View
Sure extinction occurs when the mean number of children is at most one
- FileBernoulli graph components (25 min) FileVideo file (MP4)View
Bernoulli graphs with average degree strictly larger than one admit a unique giant component
5 Coupling and stochastic similarity
- FileTotal variation distance (3 min) FileVideo file (MP4)View
Definition of total variation distance for probability distributions on a countable space
- FileTotal variation theorem (i) (18 min) FileVideo file (MP4)View
Total variation theorem (i): Total variation distance equals half L1-distance
- FileTotal variation theorem (ii) (4 min) FileVideo file (MP4)View
Total variation theorem (ii): Upper bound using an arbitrary coupling
- FileTotal variation theorem (iii) (6 min) FileVideo file (MP4)View
Total variation theorem (iii): Existence of an optimal coupling
- FileExample: Optimal coupling of coin flips (7 min) FileVideo file (MP4)View
Optimal coupling of two Bernoulli distributions
- FileDiscussion: General measurable spaces (9 min) FileVideo file (MP4)View
Total variation distance for probability measures on a general measurable space (not part of course requirements)
- FileHypothesis testing (25 min) FileVideo file (MP4)ViewAverage error in binary hypothesis testing and the likelihood ratio test
- FileHellinger distance (11 min) FileVideo file (MP4)View
Hellinger distance between two probability distributions
- FileStatistical similarity of Bernoulli graphs (8 min) FileVideo file (MP4)View
Statistical similarity of Bernoulli random graphs, upper bound on total variation distance
6 Degree distributions
- FileLecture notes - Chapter 6 updated FilePDF documentView
Updated version (2020-09-24) of Chapter 6 in the lecture notes
- FileStochastic block models (30 min) FileVideo file (MP4)View
Stochastic block models: definition, average degree, sparsity
- FilePoisson approximation (21 min) FileVideo file (MP4)View
Approximating a sum of coin flips by a Poisson distribution, a.k.a. Le Cam's inequality
- FileBlockwise SBM degree distribution (14 min) FileVideo file (MP4)View
Blockwise degree distribution in a stochastic block model
- FileMixed Poisson distribution (6 min) FileVideo file (MP4)View
Mixed Poisson distribution: Definition and representation as a random integer
- FileTypical SBM degree distribution (10 min) FileVideo file (MP4)View
Degree distribution of a typical node in a stochastic block model
- FileApproximate independence (3 min) FileVideo file (MP4)View
Approximate independence of random variables (decoupling)
7 Subgraph statistics
- FileGraph morphisms (19 min) FileVideo file (MP4)View
Graph morphisms: Homomorphisms and embeddings
- FileSubgraph densities (18 min) FileVideo file (MP4)View
Subgraph counting. Matching and covering subgraph densities.
- FileSubgraph counts in Bernoulli graphs (15 min) FileVideo file (MP4)View
Expected subgraph counts in homogeneous Bernoulli random graphs.
- FileLollipops and critical subgraph thresholds (10 min) FileVideo file (MP4)View
Lollipops provide a famous counterexample for which the expected subgraph count can be large in a Bernoulli graph which does not contain any such lollipops with high probability.
8 Learning SBM parameters
- FileStatistical inference from block network data (23 min) FileVideo file (MP4)View
Learning tasks associated with block network data.
- View
Maximum likelihood estimation of the block interaction matrix when the block memberships are known (or estimated by other means)
- FileDoubly stochastic block models (9 min) FileVideo file (MP4)View
Doubly stochastic block models, Bayesian approach using a prior block membership distribution
- FileEstimating subgraph densities (19 min) FileVideo file (MP4)View
Estimating theoretical model subgraph densities using empirical subgraph densities computed from the observed graph sample
- View
Moment method for learning block interaction parameters based on subgraph covering densities
9 Learning block memberships from network data
- FileSpectral clustering (47 min) FileVideo file (MP4)View
Spectral clustering method for recovering block memberships
- FileSpectral clustering - discussion (11 min) FileVideo file (MP4)View
Discussion about spectral graph theory techniques: graph Laplacians, random walks, adjacency matrix powers
- FileMLE estimation for homogeneous block models (11 min) FileVideo file (MP4)View
Maximum likelihood estimation of block memberships in homogeneous stochastic block models, reduction to min-cut problem
- FileBlock membership estimation accuracy (11 min) FileVideo file (MP4)View
Measuring error rates using symmetric Hamming distances, strongly and weakly consistent estimators
10 Advanced network models
- FileTransitivity (19 min) FileVideo file (MP4)View
Transitivity (a.k.a. global clustering coefficient) of a nonrandom graph
- FileModel transitivity (27 min) FileVideo file (MP4)View
Transitivity of a statistical network model
- FileRandom intersection graphs (25 min) FileVideo file (MP4)ViewRandom intersection graphs. Presentation based on the article:
Moment-based parameter estimation in binomial random intersection graph models [J Karjalainen, L Leskelä 2017]
- FileNext-generation network models (11 min) FileVideo file (MP4)View
Next-generation network models: Random geometric graphs on hyperbolic spaces, network models with overlapping communities, preferential attachment and hybrid models
A Supplementary material
- FileProbability inequalities FilePDF document