6 - Generalized Random Graphs

Summary

In this chapter, we discuss inhomogeneous random graphs, in which the equal edge probabilities of the Erdős–Rényi random graph are replaced by edge occupation statuses that are independent but not equally distributed. Indeed, in the models studied here, the edge probabilities are moderated by certain vertex weights. These weights can be taken to be deterministic or random, and both options will be considered in this chapter. An important example, on which we focus in this chapter, is the so-called generalized random graph. We show that this model has a power-law degree distribution when the weights do so. As such, this is one of the simplest adaptions of the Erdős–Rényi random graph having a power-law degree sequence.

Organisation of this Chapter

This chapter is organized as follows. In Section 6.1, we motivate the model and in Section 6.2 we introduce it formally. In Section 6.3, we investigate the degree of a fixed vertex in the generalized random graph, and in Section 6.4, we investigate the degree sequence of the generalized random graph. In Section 6.5, we study the generalized random graph with i.i.d. vertex weights. In Section 6.6, we show that the generalized random graph, conditioned on its degrees, is a uniform random graph with these degrees. In Section 6.7, we study when two inhomogeneous random graphs are asymptotically equivalent, meaning that they have the same asymptotic probabilities. Finally, in Section 6.8, we introduce several more models of inhomogeneous random graphs similar to the generalized random graph that have been studied in the literature, such as the so-called Chung-Lu or random graph with prescribed expected degrees and the Norros–Reittu or Poisson graph process model. We close this chapter with notes and discussion in Section 6.9 and exercises in Section 6.10.

Motivation of the Model

In the Erdős–Rényi random graph, every vertex plays the same role, leading to a completely homogeneous random graph. Of course, vertices do have different degrees, but the amount of variability in degrees in the Erdős–Rényi random graph is much smaller than in many real-world applications. In this chapter, we explain a possible way of extending the Erdős– Rényi random graph model to include a higher amount of inhomogeneity.