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 100page 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 possiblyrelevant papers.
 There is no systematic definitiontheoremproof 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 MathStat library).
For a broadranging 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.
Classbyclass 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 finiten random model;
calculations with PPP; Gabriel gaph on random points.
 9/9 Minimum spanning tree, relative neighborhood graph, Steiner tree.
 9/11 Worstcase and averagecase length of MST.
Start topics from Barthelemy (2011) survey. Roaddual networks,
hop distance, betweenness centrality.
 9/13 Mention leaflabeled spatial network.
Gastner  Newman (2006) study of khop networks.
Hubspoke model from Aldous (2008a).
 9/16  9/18 Continue hubspoke model; approximate equidistribution conditions.
"Routelength in treenetworks" conjecture. Construction from AldousKendall (2008);
three statistics for routelength efficiency.
 9/20 Stretch: worstcase and averagecase results.
And some slides from this lecture.
 9/23 The betaskeleton family and simulations.
Networks based on powers of edgelengths.
 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,
Pspace and Lspace 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 AldousKrikun (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 Lowerbounding length for networks with given stretch.

 11/4 The Poisson line process: more formulas.
 11/6  11/8
Random networks with linear routelengths, 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
firstpassage percolation; limits of routelengths 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.210.3).

 Start student talks.
 12/2
 12/4
 12/6
 12/9
 12/11