Typical distances in the directed configuration model

DOI10.1214/17-AAP1342MaRDI QIDQ1661569zbMATH OpenOpenAlexWikidataFDO

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)

Full work available at URL https://arxiv.org/abs/1511.04553, https://projecteuclid.org/euclid.aoap/1527840031

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)

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.

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

Cites work

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

Cited in

(8)

• Rankings in directed configuration models with heavy tailed in-degrees
• Depth first exploration of a configuration model
• The diameter of the directed configuration model
• Universality for the distance in finite variance random graphs
• Strong couplings for static locally tree-like random graphs
• Distance between two random \(k\)-out digraphs, with and without preferential attachment
• Limit theorems for assortativity and clustering in null models for scale-free networks
• The configuration model for partially directed graphs

Describes a project that uses

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)