FROM RANDOM GRAPHS TO COMPLEX NETWORKS

STAT 206, Spring 2003, David Aldous

This is ther "debrief" version, after course finished.

Topics

The course will have three parts.

Current work on complex networks and models of the Internet

Aspects of the classical Erdos-Renyi model

Graphs on random points in $d$-dimensional space

For the first part we will start with the recent survey paper

Statistical Mechanics of Complex Networks by Albert and Barabasi.

For the second part we will cover some sections from the book

Random Graphs by Svante Janson, Tomasz Luczak, Andrzej Rucinski (Wiley, 2000).

For the third part we will cover some sections from the forthcoming book

Random Geometric Graphs by Mathew Penrose (Oxford, 2003).

Lectures

Links are to scribe notes. These have not been checked carefully.

Lecture 1: Tuesday Jan 21.Introduction, from Albert-Barabasi paper.

Lecture 2: Thursday Jan 23. Review of undergraduate branching processes.

Lecture 3: Tuesday Jan 28. Random graphs with prescribed degree distribution.

Lecture 4: Thursday Jan 30. Proportional Attachment models and the Yule process

Lecture 5: Tuesday February 4. Cluster coefficients and the Newman-Watts small world model.

Lecture 6: Tuesday February 6. Proportional attachment models via analytics.

Lecture 7: Tuesday February 11. Critical behavior of the Erdos-Renyi random graph: probabilistic methods.

Lecture 8: Thursday February 13. Graph diameter in the proportional attachment model. Lecture based on

Lecture 9: Tuesday February 18. Continuation; description of very general proportional attachment model from A general model of web graphs (A. Frieze and C. Cooper). The simple ``copy factor" model from Stochastic models for the web graph (R. Kumar et al).

Lecture 10: Thursday February 20. Lecture based on The small-world phenomenon: an algorithmic perspective (J. Kleinberg).

Lectures 11 and 12: Tuesday February 25 and Thursday February 27. A tractable complex network model based on the stochastic mean-field model of distance. Some of my own current work.

Lecture 13: Tuesday March 4. Gibbs distributions and entropy

Lecture 14: Tuesday March 11. Lecture based on Network Topology Generators: Degree-based vs Structural (Tangmunarunkit et al).

Lecture 15: Thursday March 13. Flow through a complex network. Based on Congestion and centrality in traffic flow on complex networks (P. Holme); Search and congestion in complex networks (A. Arenas et al) Universal behavior of load distribution in scale-free networks (K.-I. Goh et al).

Lecture 16: Tuesday March 18. Lecture based on A Dynamic Model of Social Network Formation (B. Skyrms and R. Pemantle).

Lecture 17: Thursday March 20. Lecture based on Hierarchical Organization in complex networks (Ravasz and Barabasi).

Lecture 18: Tuesday April 1. Emergence of giant component: Theorem 5.4 of Janson-Luczak-Rucinski.

Lecture 19: Thursday April 3. The giant component in the just-supercritical regime: section 5.4 of Janson-Luczak-Rucinski.

Lecture 20: Tuesday April 8. Chromatic number of sparse random graphs: section 7.1 of Janson-Luczak-Rucinski.

Lecture 22: Tuesday April 15. Calculations with Poisson point processes: bounds on TSP length, and maxima of empty squares.

Lecture 23: Thursday April 17. Random geometric graphs: induced subgraphs; heuristics for maximal degree and connectivity.

Lecture 24: Tuesday April 22. Subcritical continuum percolation. Sections 9.6 and 10.1 of Penrose.

Lecture 25: Thursday April 24. Supercritical continuum percolation. Sections 10.2 and 10.3 of Penrose.

Student talks

Tuesday April 29. Elitza Maneva will talk on LDPC codes: an introduction. (A. Shokrollahi).

Andrej Bogdanov will speak on On the Eigenvalue Power Law (M. Mihail and C, Papadimitriou).

Thursday May 1 Sinem Coleri and Mustafa Ergen will speak on

Critical Power for Asymptotic Connectivity in Wireless Networks (P. Gupta and P.R. Kumar)

Covering Algorithms, continuum percolation and the geometry of wireless networks (L. Booth et al)

Ad hoc wireless networks with noisy links (L. Booth et al).

Tuesday May 6 Kenji Obata will talk on Divide and Conquer martingales (J.H. Kim and V. H/ Vu).

Ashwin Ganesan will talk on Optimization in complex networks

James Lee will talk on Optimal construction of edge-disjoint paths in random graphs. (Broder et al).

Thursday May 8 David Ratajczak and Alex Fabricant and Brighten Godfrey will speak on their own work on Simple power conservation in sensor networks

Stephen Sorkin will talk on
Path Planning and Expansive Configuration Spaces (Motwani et al).

Tuesday May 13

Tanya Roosta Small world phenomena and the dynamics of information

Lakshminarayanan Subramanian What do current Internet topology generators not model?

Madhav Chandrasekher will speak on Evolutionary stability in stochastic games.

Samantha Riesenfeld will talk on Link analysis and page rank algorithms.

Requirements for students

Students taking course for credit need to do one of the following. Most common option is

Read and present in class a recent research paper

Other options are

scribe several classes
do some little research (simulations and/or theory) on some new models I will suggest.

Some papers

with brief comments on those I have read.

Survey papers

Statistical Mechanics of Complex Networks (Albert and Barabasi). Wide-ranging survey without math details.
Mathematical results on scale-free random graphs (B. Bollobas). Useful survey emphasizing precise statments of known rigorous results.
Evolution of networks (S.N. Dorogovtsev and J.F.F. Mendes).

Random graphs with prescribed degree distribution

A critical point for random graphs with a given degree sequence and also The size of the largest component of a random graph on a fixed degree sequence (both by M. Molloy and B. Reed).
The two papers above give a rigorous treatment of the Lecture 3 material on random graphs with prescribed degree distribution.
A Random Graph Model for Massive Graphs (W. Aiello and F. Chung and L. Liu). More detailled study of special case of previous papers.

Preferential attachment models

The degree sequence of a scale-free random graph process (B. Bollobas, O. Riordan, J. Spencer, G. Tusnady).
Rigorous proof of limit distribution of vertex-degree in one of the basic models from Lecture 4.
Popularity based random graph models leading to a scale-free degree sequence (P.G. Buckley and D. Osthus). Rigorous proof in more general power law model.
The Diameter of a Scale-Free Random Graph (B. Bollobas and O. Riordan). This is the subject of Lecture 8.
Directed Scale-Free Graphs (B. Bollobas, C. Borgs, J. Chayes and O. Riordan).

Small World models

Most relevant to Lecture 5 is the short survey paper

Models of the Small World: a Review (Mark Newman).

Critical random graphs

Lecture 7 is based on my technical paper Brownian excursions, critical random graphs and .... A briefer summary is on pages 99 - 102 of Combinatorial Stochastic Processes (Jim Pitman).

Other resources

John Kleinberg (Cornell) has a web page for his Fall 2002 course The structure of information networks which has many useful links to WWW models.