The diameter of the directed configuration model
The paper studies random digraphs generated using the directed configuration model. In this model, an \(n\)-vertex digraph is generated as follows: given a bidegree sequence \(\mathfrak{d}_n = ((d_1^-, d_1^+),\dots, (d_n^-, d_n^+))\) with \(\sum_{i} d_i^- = \sum_i d_i^+\), then one gives \(d_i^-\) heads and \(d_i^+\) tails to each vertex \(i\) and forms a digraph by choosing a random assignment between all heads and tails. This generates a random \(n\)-vertex digraph \(G_n\) with a fixed degree sequence \(\mathfrak{d}_n\). Usually one considers a sequence \((\mathfrak{d}_n)_n\) of degree sequences and investigates the properties which hold probability tending to one as \(n\) tends to infinity. The paper studies the diameter, i.e. the maximum distance between any two vertices of \(G_n\). The main result of the paper shows that, under weak assumptions on the sequence \((\mathfrak{d}_n)_n\), the diameter of \(G_n\) divided by \(\log n\) converges in probability (when \(n\) tends to infinity) to a constant, which is determined explicitly. The assumptions needed for the result to work are that the sequences \((\mathfrak{d}_n)_n\) converge in distribution, in the first moment, and in a second moment, to a discrete probability distribution \(D\) on \(\mathbb{Z}^2_{\geq 0}\) with finite expectations and second moments. The proof relies on the analysis of a breadth first search edge-exploration process of random digraphs and its coupling with the corresponding branching process. The main result is also used to deduce results in other random digraph models.
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Bootstrap percolation in living neural networks
- Characterizing optimal sampling of binary contingency tables via the configuration model
- Diameter and stationary distribution of random r-out digraphs
- scientific article; zbMATH DE number 193053 (Why is no real title available?)
- scientific article; zbMATH DE number 3410334 (Why is no real title available?)
- scientific article; zbMATH DE number 7651064 (Why is no real title available?)
- On Recent Theorems Concerning the Supercritical Galton-Watson Process
- Probability Inequalities for Sums of Bounded Random Variables
- Probability. Theory and examples.
- Random graphs and complex networks. Volume 1
- Random walk on sparse random digraphs
- Some limit theorems for the total progeny of a branching process
- Stationary distribution and cover time of sparse directed configuration models
- The critical behavior of random digraphs
- The diameter of random regular graphs
- The diameter of sparse random graphs
- The diameter of sparse random graphs
- The giant component of the directed configuration model revisited
- The graph structure of a deterministic automaton chosen at random
- The probability that a random multigraph is simple
- The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
- The strong giant in a random digraph
- The transitive closure of a random digraph
- Typical distances in the directed configuration model
- Typical distances in the directed configuration model
- On the length of the shortest path in a sparse Barak-Erdős graph
- On the degree sequence of random geometric digraphs
- A Phase Transition for the Diameter of the Configuration Model
- The giant component of the directed configuration model revisited
- The diameter of randomly perturbed digraphs and some applications
- Rankings in directed configuration models with heavy tailed in-degrees
- The diameter of the directed configuration model
- Universality for the directed configuration model: metric space convergence of the strongly connected components at criticality
- Minimum stationary values of sparse random directed graphs
- Are giants in random digraphs `almost' local?
- Percolation in simple directed random graphs with a given degree distribution
- Diameter and stationary distribution of random r-out digraphs
- The configuration model for partially directed graphs
- Diameters in preferential attachment models
This page was built for publication: The diameter of the directed configuration model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2686613)
