STAT C206A (= MATH C223A) Fall 2013: David Aldous
STAT 206, with catalog description
Advanced Topics in Probability and Stochastic Processes,
is intended to have a different subject each semester.
My subject is
This is a broad and diffuse topic which has been studied in many disciplines, but
the course will emphasize stochastic aspects.
We start with an overview in
this 100-page survey by Marc Barthelemy,
which examines models and data from a statistical physics viewpoint and shows some
interesting real data. The survey does not emphasize math theorems, but
I will use it as a starting point for discussing what is known mathematics and what are possible
math research problems.
- We then segue into more specific technical work,
from the list of possibly-relevant papers.
- There is no systematic definition-theorem-proof account of our central topic,
general random spatial networks, but the books below treat related topics such as
and we will cover some of this material.
- Stochastic geometry
- The random geometric graph, continuum percolation and their use in models of
- Algorithmic aspects of spatial network construction
For the record I will maintain a list of networks
that are mentioned in the course.
There are no books with precisely the focus of this course.
The most closely related, as regards math topics, are
(2,3,4,7 are on reserve in the Math-Stat library).
For a broad-ranging overview of quantitative aspects of networks, without specialized math,
by far the best book is
For a textbook on some basic math see
- Baccelli - Blaszczyszyn (2009):
Stochastic Geometry and Wireless Networks: Volume I Theory.
- Franceschetti - Meester (2007): Random networks for communication:
from statistical physics to information systems.
- Narasimhan - Smid (2007): Geometric spanner networks.
- Penrose (2003): Random geometric graphs.
- Preparata - Shamos (1993): Computational Geometry: An Introduction.
- Steele (1997): Probability theory and combinatorial optimization.
- Stoyan - Kendall - Mecke (1995): Stochastic geometry and its applications.
- Newman (2010):
Networks: An Introduction.
Similar courses elsewhere
These are courses with useful info online.
Mostly with less mathematical emphasis.
MWF 1.00 - 2.00pm room 330 EVANS
Thursdays 2.15 - 3.45 in 351 Evans
If you email me (firstname.lastname@example.org) put "STAT 206" in subject line.
Requirements for students.
Students taking the course for credit need to do one of the following.
This will mostly be a debriefing of what I have done, rather than a plan for the future......
- 8/30 Abstract graph, planar graph, spatial network, Delaunay triangulation.
- 9/4 Euler's formula, triangulations, planar duals, Gabriel graph.
- 9/6 Relationship between PPP and finite-n random model;
calculations with PPP; Gabriel gaph on random points.
- 9/9 Minimum spanning tree, relative neighborhood graph, Steiner tree.
- 9/11 Worst-case and average-case length of MST.
Start topics from Barthelemy (2011) survey. Road-dual networks,
hop distance, betweenness centrality.
- 9/13 Mention leaf-labeled spatial network.
Gastner - Newman (2006) study of k-hop networks.
Hub-spoke model from Aldous (2008a).
- 9/16 - 9/18 Continue hub-spoke model; approximate equidistribution conditions.
"Route-length in tree-networks" conjecture. Construction from Aldous-Kendall (2008);
three statistics for route-length efficiency.
- 9/20 Stretch: worst-case and average-case results.
And some slides from this lecture.
- 9/23 The beta-skeleton family and simulations.
Networks based on powers of edge-lengths.
- 9/25 We will go to 1011 Evans to hear Ravi Kannan talk on
A Point Process.
- 9/27 "your friends have more friends than you do" theorem. Ideas from
Barthelemy survey; assortivity coefficient, betweenness centrality,
P-space and L-space for rail networks.
- 9/30 Overview of next part of course. Subaddutivity and local weak convergence as
``first moment" methodologies for network length. Mention CLT and LD techniques.
- Slides from lectures above omitting material from other sources.
- 10/2 - 10/7 Material from Steele (1997). Basic subadditivity lemma,
application to longest common subsequence.
de Bruijn - Erdos subadditivity result. General
"subadditive Euclidean functionals" limit theorem.
Easy application to TSP. Indirect application in Aldous-Krikun (2006).
- 10/9 - 10/11; 10/18 Review variation distance; weak convergence and product spaces;
stationarity, ergodicity and relation to dynamical systems.
- 10/21 Local weak convergence for sequences.
- 10/23 - 10/25 Local weak convergence for spatial networks; outline
application to optimal networks.
- 10/28 Stochastic geometry: intersections of TRI network with fixed line.
- 10/30 The Poisson line process: construction and basic formulas.
- 11/1 Lower-bounding length for networks with given stretch.
- 11/4 The Poisson line process: more formulas.
- 11/6 - 11/8
Random networks with linear route-lengths, from Aldous (2009).
Application of general result to the RNG.
Technique of comparison with oriented percolation; outline proof of general result.
- 11/15 Subadditive ergodic theorem and the shape theorem for
first-passage percolation; limits of route-lengths in random networks (Aldous - Garet 2013).
- 11/18 Random geometric graphs. Definition, motifs (Penrose sec 3.1).
- 11/20 Maximum degree and connectivity.
- 11/22 - 11/25 Subcritical continuum percolation (Penrose sec 10.1),
Supercritical continuum percolation (Penrose sec 10.2-10.3).
- Start student talks.