Operations Research seminar

Operations Research seminar

Distances in directed random graphs with finite degree variance

Pim van der Hoorn, UT-EWI-SOR


We analyze the distance between two arbitrary nodes in the directed configuration model where we require the degrees to have finite variance. For undirected case, the distance has been shown to scale logarithmically in the size of the graph. We extend this result to the directed case, using two couplings. The first couples the graph, as seen from a breath first exploration, with a so-called thorny branching tree. Then, we couple this tree with a branching process and analyze this process to obtain the result. We also analyze the fluctuations around the obtained sample means.

Joint work with Mariana Olvera-Cravioto, Columbia University