Probability and Spatial Networks

David Aldous
University of California, Berkeley (UC Berkeley)

Network design and analysis have been studied in many different applied contexts, yet many simple-to-state abstracted mathematical problems have not been studied very systematically. For a road network on n cities, what is the trade-off between total network length and the efficiency of the network in providing short routes? For an airline network on n cities, requiring routes to have an average of no more that 3 hops, how short can network length be? Such questions can involve probability in several ways. First, the ``average case" model of randomly-distributed cities is a natural counterpart to worst-case analysis. Second, while upper bounds on performance are obtained by explicit construction, lower bounds need more mathematical arguments provided by classical integral geometry. Third, the Poisson line process turns out to be very useful!

[Joint work with Wilf Kendall. The two papers discussed are available at and ]

Audio (MP3 File, Podcast Ready) Presentation (PDF File)

Back to Workshop III: Random and Dynamic Graphs and Networks