Typical distances in the directed configuration model

Pim van der Hoorn and Mariana Olvera-Cravioto
The Annals of Applied Probability
Volume 28, Number 3 (2018), 1739-1792.
June 1, 2018

Abstract

We analyze the  distribution of the distance between two nodes, sampled uniformly at random,  in digraphs generated via the directed configuration model, in the  supercritical regime. Under the assumption that the covariance between the  in-degree and out-degree is finite, we show that the distance grows  logarithmically in the size of the graph. In contrast with the undirected  case, this can happen even when the variance of the degrees is infinite. The  main tool in the analysis is a new coupling between a breadth-first graph  exploration process and a suitable branching process based on the  Kantorovich-Rubinstein metric. This coupling holds uniformly for a much  larger number of steps in the exploration process than existing ones, and is  therefore of independent interest.

Related publications