In this chapter, we describe the main goal of the book, its organization, course outline, and suggestions for instructions and self-study. The textbook material is aimed for a one-semester undergraduate/graduate course for mathematics and computer science students. The course might also be recommended for students of physics, interested in networks and the evolution of large systems, as well as engineering students, specializing in telecommunication. Our textbook aims to give a gentle introduction to the mathematical foundations of random graphs and to build a platform to understand the nature of real-life networks. The text is divided into three parts and presents the basic elements of the theory of random graphs and networks. To help the reader navigate through the text, we have decided to start with describing in the preliminary part (Part I) the main technical tools used throughout the text. Part II of the text is devoted to the classic Erdős–Rényi–Gilbert uniform and binomial random graphs. Part III concentrates on generalizations of the Erdős–Rényi–Gilbert models of random graphs whose features better reflect some characteristic properties of real-world networks.

Large real-world networks although being globally sparse, in terms of the number of edges, have their nodes/vertices connected by relatively short paths. In addition, such networks are locally dense, i.e., vertices lying in a small neighborhood of a given vertex are connected by many edges. This observation is called the “small-world” phenomenon, and it has generated many attempts, both theoretical and experimental, to build and study appropriate models of small-world networks. The first attempt to explain this phenomenon and to build a more realistic model was introduced by Watts and Strogatz in 1998 followed by the publication of an alternative approach by Kleinberg in 2000. The current chapter is devoted to the presentation of both models.