O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required