Typical distances in the directed configuration model

DOI10.1214/17-AAP1342zbMATH Open1393.05101arXiv1511.04553OpenAlexW2962721852WikidataQ129799921 ScholiaQ129799921MaRDI QIDQ1661569FDOQ1661569

Authors: Mariana Olvera-Cravioto, Pim Van der Hoorn 

Publication date: 16 August 2018

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1511.04553

Recommendations

• The diameter of the directed configuration model
• Distances in random graphs with finite mean and infinite variance degrees
• Distances in random graphs with finite variance degrees
• Weighted distances in scale-free configuration models
• Universality for the distance in finite variance random graphs

zbMATH Keywords

branching processesdirected configuration modelcouplingsrandom digraphsKantorovich-Rubinstein distancetypical distances

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12)

Cites Work

• Random graphs and complex networks. Volume 1
• Title not available (Why is that?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Random graph dynamics
• On a conditionally Poissonian graph process
• Distances in random graphs with finite mean and infinite variance degrees
• Central limit theorems for the Wasserstein distance between the empirical and the true distributions
• Universality for the distance in finite variance random graphs
• Directed random graphs with given degree distributions
• Distances in random graphs with finite variance degrees
• Title not available (Why is that?)
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• The strong giant in a random digraph
• Large deviations in the supercritical branching process
• Distance in random graphs with infinite mean degrees
• How likely is an LLD degree sequence to be graphical?
• Generalized PageRank on directed configuration networks
• La densit� de la loi-limite d'un processus en cascade expansif

Cited In (4)

• Rankings in directed configuration models with heavy tailed in-degrees
• The diameter of the directed configuration model
• Universality for the distance in finite variance random graphs
• Limit theorems for assortativity and clustering in null models for scale-free networks

Uses Software

• WebGraph

This page was built for publication: Typical distances in the directed configuration model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1661569)