NEWS
Spatial Networks
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
Spatial Networks
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
- Stochastic geometry
- The random geometric graph, continuum percolation and their use in models of
wireless communication
- Algorithmic aspects of spatial network construction
and we will cover some of this material.
For the record I will maintain a list of networks
that are mentioned in the course.
Books
There are no books with precisely the focus of this course.
The most closely related, as regards math topics, are
- 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.
(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
- Newman (2010):
Networks: An Introduction.
Similar courses elsewhere
These are courses with useful info online.
Mostly with less mathematical emphasis.
Administration
Lecture times:
MWF 1.00 - 2.00pm room 330 EVANS
Office Hours
Thursdays 2.15 - 3.45 in 351 Evans
If you email me (aldous@stat.berkeley.edu) put "STAT 206" in subject line.
Requirements for students.
Students taking the course for credit need to do one of the following.
Class-by-class schedule
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.
-
- 11/13
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),
-
- 11/27
Supercritical continuum percolation (Penrose sec 10.2-10.3).
-
- Start student talks.
- 12/2
- 12/4
- 12/6
- 12/9
- 12/11