Small-worlds, complex networks, and random graphs

Empirical findings have shown that many real-world networks share fascinating features. Indeed, many real-world networks are small worlds, in the sense that typical distances are much smaller than the size of the network. Further, many real-world networks are scale-free in the sense that there is a high variability in the number of connections of the elements of the networks. Therefore, such networks are highly inhomogeneous. Spurred by these empirical findings, models have been proposed for such networks. In this lecture series, we discuss empirical findings of real-world networks, and describe some of the random graph models proposed for them. In particular, we will discuss the configuration model, generalized random graphs and preferential attachment models. We then discuss the small-world phenomenon in these random graph models and its link to `six degrees of separation'. We highlight some of the ingredients used in the proofs, namely the tree-like nature of the random graphs under consideration and the use of branching processes. A rough outline of the lecture series is as follows: Lecture 1: Real-world networks and random graphs; Lecture 2: Small-world phenomenon in random graphs