MS-E1603 - Random Graphs and Network Statistics D, 07.09.2020-15.10.2020
Kurssiasetusten perusteella kurssi on päättynyt 15.10.2020 Etsi kursseja: MS-E1603
Osion kuvaus
-
The lectures follow the lecture notes: Random graphs and network statistics (Lasse Leskelä, 2019).
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-
Overview of course contents and learning outcomes
-
Definition of a graph and its adjacency matrix
-
Definition and probability distribution of a Bernoulli random graph
-
Interesting events and random variables related to random graphs
-
Existence of isolated nodes in a Bernoulli random graph
-
Mean number of isolated nodes in dense and sparse graphs.
-
Markov's inequality related the mean and the tail of a distribution
-
Nonexistence of isolated nodes in sufficiently dense graphs.
-
Existence of isolated nodes.
-
Chebyshev's inequality
-
Second moment method for proving that a random integer is strictly positive with high probability
-
-
Connectivity threshold for Bernoulli random graphs
-
Simulated Bernoulli graphs below and above the critical threshold, for n=500.
-
Learning objectives
-
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
-
Stochastic coupling method, illustration for ordering tails of binomial random variables
-
Partial orders, increasing functions, upper sets
-
Stochastic orders and Strassen's coupling theorem
-
Subgraph order and monotone graph properties
-
Stochastic ordering of inhomogeneous Bernoulli graphs
-
Connectivity of inhomogeneous Bernoulli graphs
-
Topics and learning goals
-
Branching processes and Galton-Watson trees
-
Generating function of a probability distribution
-
Generating function of the population size distribution at time t
-
Probability of eventual extinction
-
Sure extinction occurs when the mean number of children is at most one
-
Bernoulli graphs with average degree strictly larger than one admit a unique giant component
-
Outline of topics and learning objectives
-
Definition of total variation distance for probability distributions on a countable space
-
Total variation theorem (i): Total variation distance equals half L1-distance
-
Total variation theorem (ii): Upper bound using an arbitrary coupling
-
Total variation theorem (iii): Existence of an optimal coupling
-
Optimal coupling of two Bernoulli distributions
-
Total variation distance for probability measures on a general measurable space (not part of course requirements)
-
Average error in binary hypothesis testing and the likelihood ratio test
-
Hellinger distance between two probability distributions
-
Statistical similarity of Bernoulli random graphs, upper bound on total variation distance
-
Updated version (2020-09-24) of Chapter 6 in the lecture notes
-
Outline of topics and learning goals.
-
Stochastic block models: definition, average degree, sparsity
-
Approximating a sum of coin flips by a Poisson distribution, a.k.a. Le Cam's inequality
-
Blockwise degree distribution in a stochastic block model
-
Mixed Poisson distribution: Definition and representation as a random integer
-
Degree distribution of a typical node in a stochastic block model
-
Approximate independence of random variables (decoupling)
-
Outline of topics and learning goals.
-
Subgraphs and induced subgraphs.
-
Graph morphisms: Homomorphisms and embeddings
-
Graph isomorphisms and automorphims.
-
Subgraph counting. Matching and covering subgraph densities.
-
Expected subgraph counts in homogeneous Bernoulli random graphs.
-
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.
-
Updates and corrections to Chapter 8
-
Outline of topics and learning goals
-
Learning tasks associated with block network data.
-
Maximum likelihood estimation of the block interaction matrix when the block memberships are known (or estimated by other means)
-
Doubly stochastic block models, Bayesian approach using a prior block membership distribution
-
Estimating theoretical model subgraph densities using empirical subgraph densities computed from the observed graph sample
-
Moment method for learning block interaction parameters based on subgraph covering densities
-
Outline of learning goals and topics.
-
Spectral clustering method for recovering block memberships
-
Discussion about spectral graph theory techniques: graph Laplacians, random walks, adjacency matrix powers
-
Maximum likelihood estimation of block memberships in homogeneous stochastic block models, reduction to min-cut problem
-
Measuring error rates using symmetric Hamming distances, strongly and weakly consistent estimators
-
Outline of topics and learning goals
-
Transitivity (a.k.a. global clustering coefficient) of a nonrandom graph
-
Transitivity of a statistical network model
-
Random intersection graphs. Presentation based on the article:
Moment-based parameter estimation in binomial random intersection graph models [J Karjalainen, L Leskelä 2017]
-
Next-generation network models: Random geometric graphs on hyperbolic spaces, network models with overlapping communities, preferential attachment and hybrid models
-
Closing words of the lecture series
-