In this chapter we investigate graph distances in preferential attachment models. We focus on typical distances as well as the diameter of preferential attachment models. We again rely on path-counting techniques, as well as local limit results. Since the local limit is a rather involved quantity, some parts of our analysis are considerably harder than those in Chapters 6 and 7.

In this chapter we investigate the distance structure of the configuration model by investigating its typical distances and its diameter. We adapt the path-counting techniques in Chapter 6 to the configuration model, and obtain typical distances from the “giant is almost local” proof. To understand the ultra-small distances for infinite-variance degree configuration models, we investigate the generation growth of infinite-mean branching processes. The relation to branching processes informally leads to the power-iteration technique that allows one to deduce typical distance results in random graphs in a relatively straightforward way.

In this chapter we investigate the small-world structure in rank-1 and general inhomogeneous random graphs. For this, we develop path-counting techniques that are interesting in their own right.