For the first part we will start with the recent survey paper
For the second part we will cover some sections from the book
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.
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.