Office Hours: Fridays 10.15 - 11.45 in 351 Evans.
If you email me (aldous@stat) put "STAT 260" in subject line.
Requirements for students. Students taking course for credit need to do one of the following. Most common option is
Kleinberg (Cornell):
The Structure of Information Networks
Mihail (Georgia Tech):
Algorithms for Complex Networks.
Grossglauser, Thiran (EPFL):
Models and Methods for Random Networks
van der Hofstad (TU Eindhoven):
Random Graphs and Complex Networks.
Watts (Columbia):
Networks and Complexity in Social Systems.
Saberi (Stanford): Information Networks.
Lecture 1: Tuesday Jan 16. The big picture as of year 2001, as sketched in the introduction of the Albert - Barabasi survey.
Lecture 2: Thursday Jan 18. Review of undergraduate branching processes, following lecture notes and quite similar to Durrett section 2.1.
Lecture 3: Tuesday Jan 23. Random graphs with prescribed degree distribution, following lecture notes and parallel to Durrett sections 3.1 and 3.4
Lectures 4 and 5: Thursday Jan 25 and Tuesday Jan 30. Details from Durrett section 2.3: components in sub/supercritical Erdos-Renyi random graphs.
Lecture 6: Thursday Feb 1. Critical behavior of the Erdos-Renyi random graph: probabilistic methods. ; see also Durrett sec. 2.7.
Lecture 7: Thursday Feb 8. Barabasi-Albert proportional attachment model; from Durrett secs 4.1 and 4.2.
Lecture 8: Tuesday Feb 13. Yule process heuristics for proportional attachment models, following lecture notes. Somewhat relevant is A Brief History of Generative Models for Power Law and Lognormal Distributions by Michael Mitzenmacher.
Lecture 9: Thursday Feb 15. Lecture based on The small-world phenomenon: an algorithmic perspective (J. Kleinberg). See also his recent update/survey Complex Networks and Decentralized Search Algorithms as a source for reading projects.
Lectures 10 and 11: Tuesday February 20 and Thursday February 22. A tractable complex network model based on the stochastic mean-field model of distance. Some of my own work, in this short paper and this longer paper. Check out these cute Java simulations of the stochastic mean-field model of distance.
Lecture 12: Tuesday February 27. Lecture based on A Dynamic Model of Social Network Formation (B. Skyrms and R. Pemantle). Check Google Scholar for subsequent papers citing this -- good source of projects.
Lectures 13 and 14: Thursday March 1 and Tuesday March 6. The CHKNS model; from Durrett Chapter 7.
Lectures 15 - 16: Thursday March 8 and Tuesday March 13. Continuum percolation and the STIRG model. From Chapter 11 of Models and Methods for Random Networks
Lectures 17 - 18: Thursday March 15 and Tuesday March 20. Transport capacity in the STIRG model. From Chapter 12 of Models and Methods for Random Networks
Lecture 19: Thursday March 22. Flow through complete graph with random edge-capacities. See draft paper.
Lecture 20: Tuesday April 3. Lecture based on Spatial Gossip and Resource Location Protocols by D Kempe, J. Kleinberg and A Demers.
Lecture 21: Thursday April 5. Some suggested projects. And lecture based on A simple model of global cascades on random networks by Duncan J. Watts.
Lecture 22: Tuesday April 10. Flow through a complex network. Based on Universal behavior of load distribution in scale-free networks (K.-I. Goh et al); Congestion and centrality in traffic flow on complex networks (P. Holme); Dynamics of jamming transitions in complex networks (P. Echenique and J. Gomez-Gardenes and Y. Moreno). Search and congestion in complex networks (A. Arenas et al).
Lecture 23: Thursday April 12. Lecture based on The effects of spatial constraints on the evolution of weighted complex networks by Alain Barrat, Marc Barthelemy and Alessandro Vespignani.
Lecture 24: Tuesday April 17. Based on Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications by Lun Li, David Alderson, John C. Doyle, and Walter Willinger.
Lecture 25: Thursday April 19. Lecture based on A Comparative Analysis of Influenza Vaccination Programs by Shweta Bansal, Babak Pourbohloul, Lauren Ancel Meyers; Threshold Effects for Two Pathogens Spreading on a Network by Mark Newman.
Tuesday April 24
Javed Ahmed. Whom You Know Matters: Venture Capital Networks and Investment Performance by YV Hochberg, A Ljunqvist and Y Lu.
Thursday April 26
Joanne Lee. Bayesian Learning in Social Networks by Douglas Gale (NYU) and Shachar Kariv (UC Berkeley).
Moorea Brega. Cooperation and the Emergence of Role Differentiation in the Dynamics of Social Networks by Victor M. Eguiluz, Martin G. Zimmermann, Camilo J. Cela-Conde, and Maxi San Miguel.
Sumitra Ganesh. Maximizing the spread of influence through a social network by John Kleinberg.
Tuesday May 1
Partha Dey. Dynamic Random Geometric Graphs by Josep Diaz, Dieter Mitsche, Xavier Perez.
Jian Ding. Sampling Regular Graphs and a Peer-to-Peer Network by Colin Cooper, Martin Dyer, Catherine Greenhill.
Guy Bresler. Isomorphism and embedding problems for infinite limits of scale-free graphs by Robert Kleinberg and Jon Kleinberg.
Thursday May 3.
Alan Sly. On the spread of viruses on the internet by Noam Berger, Christian Borgs, Jennifer T. Chayes, Amin Saberi.
Shankar Bhamidi. "Self Organization and the growth of cities" based on two books: The Self-Organizing economy (Krugman) and Cities and Complexity (Michael Batty).
Alexandre Stauffer. The evolution of navigable small-world networks by Oskar Sandberg and Ian Clarke.
Later
Alexandre Skorokhod Near Optimal Routing for Small-World Networks with Augmented Local Awarenes by Jianyang Zeng, Wen-Jing Hsu, Jiangdian Wang.