Required: Probability, Advanced Probability.
Recommended: Measure and integral.
Or permission of the instructor.
Understand the fundamentals of random graph theory.
Explore connections to combinatorics, probability and statistical physics.
Discuss typical properties of large real-world networks.
Survey principal stochastic models and methods for the analysis of networks.
Networks are ubiquitous. The mathematical analysis of random models of networks was begun over half a century ago, most notably from the perspectives of probabilistic combinatorics and statistical physics. A most prominent model is the elegant Erdős-Rényi random graph (which has its origins as early as 1947) and this model has over the decades yielded many unexpected results and insights. In the past 15 years or so, there has been an explosive increase of research into probability spaces of graphs that exhibit real-world properties -- that is, large-scale properties exhibited by networks coming from, for example, biology, economics, high technology, and sociology. There are at least two major reasons for this explosion (aside from the huge pressure of interest from the aforementioned fields): one is that, practically speaking, algorithmics, statistics and computational power had advanced enough to be able to actually analyse and quantify this behaviour for massive networks such as the Internet; another is that, from many perspectives, the theory had sufficiently developed for the proposal and rigorous assessment of a wide range of candidate models of random graph. In this course, we shall follow this development, beginning with the Erdős-Rényi model, and eventually move towards more realistic models such as geometric, inhomogeneous, and preferential attachment random graph models.
The final grade is based on a combination of homework, a project/presentation, and/or (oral) examination.
Alon and Spencer. The probabilistic method, 3rd ed.