MS-E1603 - Random Graphs and Network Statistics D, Lecture, 13.9.2021-21.10.2021

Topic outline

• Lectures
  The lectures follow the lecture notes: Random graphs and network statistics (Lasse Leskelä, 2019).
  Updates to lecture notes are announced separately.
  
  Online lecturer contact hours every Mon 12:15–14:00 via Zoom (Meeting ID: 665 4105 4702, https://aalto.zoom.us/j/66541054702).
  

  • Select activity 1 Graphs and random graphs

    1 Graphs and random graphs

  • Select activity L01-0 Introduction (14 min)

    

    L01-0 Introduction (14 min) File MP4

    Completion

    Students must

    

    View

    Overview of course contents and learning outcomes

  • Select activity L01-1 Graphs (20 min)

    

    L01-1 Graphs (20 min) File MP4

    Completion

    Students must

    

    View

    Definition of a graph and its adjacency matrix

  • Select activity L01-2 Bernoulli random graphs (28 min)

    

    L01-2 Bernoulli random graphs (28 min) File MP4

    Completion

    Students must

    

    View

    Definition and probability distribution of a Bernoulli random graph

  • Select activity L01-3 Random graph features (13 min)

    

    L01-3 Random graph features (13 min) File MP4

    Completion

    Students must

    

    View

    Interesting events and random variables related to random graphs

  • Select activity 2 Isolated nodes in Bernoulli random graphs

    2 Isolated nodes in Bernoulli random graphs

  • Select activity L02-0 Introduction (4 min)

    

    L02-0 Introduction (4 min) File MP4

    Completion

    Students must

    

    View

    Existence of isolated nodes in a Bernoulli random graph
  • Select activity L02-1 Mean number of isolated nodes (20 min)

    

    L02-1 Mean number of isolated nodes (20 min) File MP4

    Completion

    Students must

    

    View

    Mean number of isolated nodes in dense and sparse graphs.

  • Select activity L02-2 Markov's inequality (4 min)

    

    L02-2 Markov's inequality (4 min) File MP4

    Completion

    Students must

    

    View

    Markov's inequality related the mean and the tail of a distribution

  • Select activity L02-3 Nonexistence of isolated nodes (4 min)

    

    L02-3 Nonexistence of isolated nodes (4 min) File MP4

    Completion

    Students must

    

    View

    Nonexistence of isolated nodes in sufficiently dense graphs.

  • Select activity L02-4 Existence of isolated nodes (9 min)

    

    L02-4 Existence of isolated nodes (9 min) File MP4

    Completion

    Students must

    

    View

    Existence of isolated nodes.

  • Select activity L02-5 Chebyshev's inequality (2 min)

    

    L02-5 Chebyshev's inequality (2 min) File MP4

    Completion

    Students must

    

    View

    Chebyshev's inequality
    

  • Select activity L02-6 Second moment method (6 min)

    

    L02-6 Second moment method (6 min) File MP4

    Completion

    Students must

    

    View

    Second moment method for proving that a random integer is strictly positive with high probability

  • Select activity L02-7 Variance of isolated node count (16 min)

    

    L02-7 Variance of isolated node count (16 min) File MP4

    Completion

    Students must

    

    View
  • Select activity L02-8 Connectivity threshold (15 min)

    

    L02-8 Connectivity threshold (15 min) File MP4

    Completion

    Students must

    

    View

    Connectivity threshold for Bernoulli random graphs
    

  • Select activity L02-9 Simulation (1 min)

    

    L02-9 Simulation (1 min) File MP4

    Completion

    Students must

    

    View

    Simulated Bernoulli graphs below and above the critical threshold, for n=500.

  • Select activity 3 Inhomogeneous Bernoulli graphs and stochastic or...

    3 Inhomogeneous Bernoulli graphs and stochastic ordering

  • Select activity L03-1 Objectives (1 min)

    

    L03-1 Objectives (1 min) File MP4

    Completion

    Students must

    

    View

    Learning objectives

  • Select activity L03-2 Inhomogeneous Bernoulli graphs (16 min)

    

    L03-2 Inhomogeneous Bernoulli graphs (16 min) File MP4

    Completion

    Students must

    

    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
    

  • Select activity L03-3 Stochastic coupling method (22 min)

    

    L03-3 Stochastic coupling method (22 min) File MP4

    Completion

    Students must

    

    View

    Stochastic coupling method, illustration for ordering tails of binomial random variables
    

  • Select activity L03-4 Partial orders (8 min)

    

    L03-4 Partial orders (8 min) File MP4

    Completion

    Students must

    

    View

    Partial orders, increasing functions, upper sets
    

  • Select activity L03-5 Stochastic orders (15 min)

    

    L03-5 Stochastic orders (15 min) File MP4

    Completion

    Students must

    

    View

    Stochastic orders and Strassen's coupling theorem
    

  • Select activity L03-6 Subgraph order (13 min)

    

    L03-6 Subgraph order (13 min) File MP4

    Completion

    Students must

    

    View

    Subgraph order and monotone graph properties

  • Select activity L03-7 Stochastic ordering of Bernoulli graphs (14 min)

    

    L03-7 Stochastic ordering of Bernoulli graphs (14 min) File MP4

    Completion

    Students must

    

    View

    Stochastic ordering of inhomogeneous Bernoulli graphs
    

  • Select activity L03-8 Connectivity of inhomogeneous Bernoulli graphs (4 min)

    

    L03-8 Connectivity of inhomogeneous Bernoulli graphs (4 min) File MP4

    Completion

    Students must

    

    View

    Connectivity of inhomogeneous Bernoulli graphs
    

  • Select activity 4 Giant components

    4 Giant components

  • Select activity Outline (5 min)

    

    Outline (5 min) File MP4

    Completion

    Students must

    

    View

    Topics and learning goals

  • Select activity Branching processes (8 min)

    

    Branching processes (8 min) File MP4

    Completion

    Students must

    

    View

    Branching processes and Galton-Watson trees
    

  • Select activity Generating functions (13 min)

    

    Generating functions (13 min) File MP4

    Completion

    Students must

    

    View

    Generating function of a probability distribution

  • Select activity Population size generating function (6 min)

    

    Population size generating function (6 min) File MP4

    Completion

    Students must

    

    View

    Generating function of the population size distribution at time t

  • Select activity Extinction probability (13 min)

    

    Extinction probability (13 min) File MP4

    Completion

    Students must

    

    View

    Probability of eventual extinction

  • Select activity Sure extinction (16 min)

    

    Sure extinction (16 min) File MP4

    Completion

    Students must

    

    View

    Sure extinction occurs when the mean number of children is at most one

  • Select activity Bernoulli graph components (25 min)

    

    Bernoulli graph components (25 min) File MP4

    Completion

    Students must

    

    View

    Bernoulli graphs with average degree strictly larger than one admit a unique giant component

  • Select activity 5 Coupling and stochastic similarity

    5 Coupling and stochastic similarity

  • Select activity Outline (3 min)

    

    Outline (3 min) File MP4

    Completion

    Students must

    

    View

    Outline of topics and learning objectives

  • Select activity Total variation distance (3 min)

    

    Total variation distance (3 min) File MP4

    Completion

    Students must

    

    View

    Definition of total variation distance for probability distributions on a countable space
    

  • Select activity Total variation theorem (i) (18 min)

    

    Total variation theorem (i) (18 min) File MP4

    Completion

    Students must

    

    View

    Total variation theorem (i): Total variation distance equals half L¹-distance
    

  • Select activity Total variation theorem (ii) (4 min)

    

    Total variation theorem (ii) (4 min) File MP4

    Completion

    Students must

    

    View

    Total variation theorem (ii): Upper bound using an arbitrary coupling
    

  • Select activity Total variation theorem (iii) (6 min)

    

    Total variation theorem (iii) (6 min) File MP4

    Completion

    Students must

    

    View

    Total variation theorem (iii): Existence of an optimal coupling
    

  • Select activity Example: Optimal coupling of coin flips (7 min)

    

    Example: Optimal coupling of coin flips (7 min) File MP4

    Completion

    Students must

    

    View

    Optimal coupling of two Bernoulli distributions
    

  • Select activity Discussion: General measurable spaces (9 min)

    

    Discussion: General measurable spaces (9 min) File MP4

    Completion

    Students must

    

    View

    Total variation distance for probability measures on a general measurable space (not part of course requirements)
    

  • Select activity Hypothesis testing (25 min)

    

    Hypothesis testing (25 min) File MP4

    Completion

    Students must

    

    View

    Average error in binary hypothesis testing and the likelihood ratio test
  • Select activity Hellinger distance (11 min)

    

    Hellinger distance (11 min) File MP4

    Completion

    Students must

    

    View

    Hellinger distance between two probability distributions

  • Select activity Statistical similarity of Bernoulli graphs (8 min)

    

    Statistical similarity of Bernoulli graphs (8 min) File MP4

    Completion

    Students must

    

    View

    Statistical similarity of Bernoulli random graphs, upper bound on total variation distance
    

  • Select activity 6 Degree distributions

    6 Degree distributions

  • Select activity Lecture notes - Chapter 6 updated

    

    Lecture notes - Chapter 6 updated File PDF

    Completion

    Students must

    

    View

    Updated version (2020-09-24) of Chapter 6 in the lecture notes

  • Select activity Outline (2 min)

    

    Outline (2 min) File MP4

    Completion

    Students must

    

    View

    Outline of topics and learning goals.

  • Select activity Stochastic block models (30 min)

    

    Stochastic block models (30 min) File MP4

    Completion

    Students must

    

    View

    Stochastic block models: definition, average degree, sparsity

  • Select activity Poisson approximation (21 min)

    

    Poisson approximation (21 min) File MP4

    Completion

    Students must

    

    View

    Approximating a sum of coin flips by a Poisson distribution, a.k.a. Le Cam's inequality

  • Select activity Blockwise SBM degree distribution (14 min)

    

    Blockwise SBM degree distribution (14 min) File MP4

    Completion

    Students must

    

    View

    Blockwise degree distribution in a stochastic block model
    

  • Select activity Mixed Poisson distribution (6 min)

    

    Mixed Poisson distribution (6 min) File MP4

    Completion

    Students must

    

    View

    Mixed Poisson distribution: Definition and representation as a random integer
    

  • Select activity Typical SBM degree distribution (10 min)

    

    Typical SBM degree distribution (10 min) File MP4

    Completion

    Students must

    

    View

    Degree distribution of a typical node in a stochastic block model
    

  • Select activity Approximate independence (3 min)

    

    Approximate independence (3 min) File MP4

    Completion

    Students must

    

    View

    Approximate independence of random variables (decoupling)
    

  • Select activity 7 Subgraph statistics

    7 Subgraph statistics

  • Select activity 1 Outline (8 min)

    

    1 Outline (8 min) File MP4

    Completion

    Students must

    

    View

    Outline of topics and learning goals.

  • Select activity Subgraphs (16 min)

    

    Subgraphs (16 min) File MP4

    Completion

    Students must

    

    View

    Subgraphs and induced subgraphs.

  • Select activity Graph morphisms (19 min)

    

    Graph morphisms (19 min) File MP4

    Completion

    Students must

    

    View

    Graph morphisms: Homomorphisms and embeddings

  • Select activity Graph isomorphisms (6 min)

    

    Graph isomorphisms (6 min) File MP4

    Completion

    Students must

    

    View

    Graph isomorphisms and automorphims.

  • Select activity Subgraph densities (18 min)

    

    Subgraph densities (18 min) File MP4

    Completion

    Students must

    

    View

    Subgraph counting. Matching and covering subgraph densities.

  • Select activity Subgraph counts in Bernoulli graphs (15 min)

    

    Subgraph counts in Bernoulli graphs (15 min) File MP4

    Completion

    Students must

    

    View

    Expected subgraph counts in homogeneous Bernoulli random graphs.

  • Select activity Lollipops and critical subgraph thresholds (10 min)

    

    Lollipops and critical subgraph thresholds (10 min) File MP4

    Completion

    Students must

    

    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.

  • Select activity 8 Learning SBM parameters

    8 Learning SBM parameters

  • Select activity Lecture notes - Chapter 8 updated

    

    Lecture notes - Chapter 8 updated File PDF

    Completion

    Students must

    

    View

    Updates and corrections to Chapter 8
    

  • Select activity Outline (4 min)

    

    Outline (4 min) File MP4

    Completion

    Students must

    

    View

    Outline of topics and learning goals 

  • Select activity Statistical inference from block network data (23 min)

    

    Statistical inference from block network data (23 min) File MP4

    Completion

    Students must

    

    View

    Learning tasks associated with block network data.

  • Select activity MLE of block interaction matrix given block memberships (21 min)

    

    MLE of block interaction matrix given block memberships (21 min) File MP4

    Completion

    Students must

    

    View

    Maximum likelihood estimation of the block interaction matrix when the block memberships are known (or estimated by other means)
    

  • Select activity Doubly stochastic block models (9 min)

    

    Doubly stochastic block models (9 min) File MP4

    Completion

    Students must

    

    View

    Doubly stochastic block models,  Bayesian approach using a prior block membership distribution
    

  • Select activity Estimating subgraph densities (19 min)

    

    Estimating subgraph densities (19 min) File MP4

    Completion

    Students must

    

    View

    Estimating theoretical model subgraph densities using empirical subgraph densities computed from the observed graph sample
    

  • Select activity Moment method for learning block interaction parameters (14 min)

    

    Moment method for learning block interaction parameters (14 min) File MP4

    Completion

    Students must

    

    View

    Moment method for learning block interaction parameters based on subgraph covering densities
    

  • Select activity 9 Learning block memberships from network data

    9 Learning block memberships from network data

  • Select activity Outline (1 min)

    

    Outline (1 min) File MP4

    Completion

    Students must

    

    View

    Outline of learning goals and topics.

  • Select activity Spectral clustering (47 min)

    

    Spectral clustering (47 min) File MP4

    Completion

    Students must

    

    View

    Spectral clustering method for recovering block memberships

  • Select activity Spectral clustering - discussion (11 min)

    

    Spectral clustering - discussion (11 min) File MP4

    Completion

    Students must

    

    View

    Discussion about spectral graph theory techniques: graph Laplacians, random walks, adjacency matrix powers

  • Select activity MLE estimation for homogeneous block models (11 min)

    

    MLE estimation for homogeneous block models (11 min) File MP4

    Completion

    Students must

    

    View

    Maximum likelihood estimation of block memberships in homogeneous stochastic block models, reduction to min-cut problem
    

  • Select activity Block membership estimation accuracy (11 min)

    

    Block membership estimation accuracy (11 min) File MP4

    Completion

    Students must

    

    View

    Measuring error rates using symmetric Hamming distances, strongly and weakly consistent estimators

  • Select activity 10 Advanced network models

    10 Advanced network models

  • Select activity Outline (1 min)

    

    Outline (1 min) File MP4

    Completion

    Students must

    

    View

    Outline of topics and learning goals 

  • Select activity Transitivity (19 min)

    

    Transitivity (19 min) File MP4

    Completion

    Students must

    

    View

    Transitivity (a.k.a. global clustering coefficient) of a nonrandom graph
    

  • Select activity Model transitivity (27 min)

    

    Model transitivity (27 min) File MP4

    Completion

    Students must

    

    View

    Transitivity of a statistical network model
    

  • Select activity Random intersection graphs (25 min)

    

    Random intersection graphs (25 min) File MP4

    Completion

    Students must

    

    View

    Random intersection graphs.  Presentation based on the article:
    

    Moment-based parameter estimation in binomial random intersection graph models [J Karjalainen, L Leskelä 2017]

  • Select activity Next-generation network models (11 min)

    

    Next-generation network models (11 min) File MP4

    Completion

    Students must

    

    View

    Next-generation network models: Random geometric graphs on hyperbolic spaces, network models with overlapping communities, preferential attachment and hybrid models
    

  • Select activity Closing words (4 min)

    

    Closing words (4 min) File MP4

    Completion

    Students must

    

    View

    Closing words of the lecture series
    

  • Select activity A Supplementary material

    A Supplementary material

  • Select activity Probability inequalities

    

    Probability inequalities File PDF

    Completion

    Students must

    

    Mark as done