10 - Inhomogeneous Graphs

Summary

In this chapter, we consider a generalization of the classic random graph, where the probability of edge {i,j} is not the same for all pairs {i,j}. We call this the generalized binomial graph. Our main result on this model concerns the probability that it is connected. After this, we move onto a special case of this model, namely the expected degree model introduced by Chung and Lu. Here, edge probabilities are proportional to the weights of their endpoints. In this model, we prove results about the size of the largest components. The final section introduces a tool, called the configuration model, to generate a close approximation of a random graph with a fixed degree sequence.