Some Introductory Notes on Random Graphs

As the concept of graph plays a fundamental role in every aspect of complex networks, in this chapter, we will provide a brief introduction to graph theory with particular focus on models of random graphs for their role of furnishing the simplest and more effective way to exhibit large scale graphs having properties similar to the real life networks (like for instance the world wide web). After recalling basic notation and concepts on graphs, we will consider three different models of random graphs for their crucial role in the analysis and simulation of large scale networks. We will make an attempt to present both rigorous mathematical results and applications examples, without much details, but with precise references to retrieve them. We will restrict our analysis to specific aspects that are of much interest for us and for the purpose of this book, in particular we will analyze the asymptotic behavior of random graphs when the size tends to infinity, in terms of connectivity, existence of giant components, distances, and local topological structure.