Analysis of Complex Networks

17.4 The Random Graph Model of Erdőos and Rényi

In this section we want to present some results on the random graph model of Erdőos and Rényi [19, 20]. This model is defined as follows. Given are n vertices with labels 1,..., n and a probability p. Then each possible edge is included in the edge set of the graph with probability p, where all edges are treated independently. The resulting graph is denoted by G(n, p). A second model is considering the set of all graphs with n vertices and m edges and choosing one graph uniformly at random. This graph is called G(n, m) and it is known that the two models are equivalent in many respects, provided that p is close to m (see [28, Section 1.4] for details).

One interesting phenomenon of random graphs is the emergence of a giant component. If we let n → ∞ and set p = c/n, thenfor c < 1 a typical graph consists of small and simple components, that is, each component has a typical size of O(log n) and does not contain many cycles. If c > 1, then a typical graph consists of one giant component that comprises roughly two thirds of all vertices and many small and simple components. The phase transition occurring around c = 1 was thoroughly studied by Janson et al. [27].

17.4.1 Counting Connected Graphs with Wright's Method

When analyzing the phase transition at the emergence of a giant component, it is of prime importance to understand the behavior ...