Analysis of Complex Networks

17.1 Introduction

In this chapter we present some results on various types of random graphs that can be obtained by methods of analytic combinatorics. Our journey through random graphs starts with the simplest type, random trees, and goes on to more and more complex random graphs. The term “analytic combinatorics” summarizes the combinatorial and asymptotic analysis of certain properties of discrete structures that can be treated by means of a generating function; see the monograph by Flajolet and Sedgewick [24]. In fact, many combinatorial constructions have their counterpart in generating functions (GFs). In particular, if some strucure has a recursive description, then there is usually a GF approach to the counting problem for this structure. Trees, in particular rooted trees, are one of the most prominent structures that can be analyzed in that way. There are at least two major advantages of a GF approach. First, it is usually not only possible to count the number of objects of a given size but several parameters at the same time by introducing several variables. Second, GFs can be considered as analytic objects, more precisely as analytic functions, so that asymptotic methods like saddle point methods or a singularity analysis provide asymptotic expansions for the coefficients and also probabilistic limiting distributions.

This chapter is organized as follows. In Section 17.2 we discuss (rooted) trees. From a graph-theoretic viewpoint, trees have a very simple structure. Therefore, ...