Stationary distribution and cover time of sparse directed configuration models
- PDF / 800,049 Bytes
- 56 Pages / 439.37 x 666.142 pts Page_size
- 18 Downloads / 206 Views
Stationary distribution and cover time of sparse directed configuration models Pietro Caputo1
· Matteo Quattropani1
Received: 24 September 2019 / Revised: 28 July 2020 © The Author(s) 2020
Abstract We consider sparse digraphs generated by the configuration model with given indegree and out-degree sequences. We establish that with high probability the cover time is linear up to a poly-logarithmic correction. For a large class of degree sequences we determine the exponent γ ≥ 1 of the logarithm and show that the cover time grows as n logγ (n), where n is the number of vertices. The results are obtained by analysing the extremal values of the stationary distribution of the digraph. In particular, we show that the stationary distribution π is uniform up to a poly-logarithmic factor, and that for a large class of degree sequences the minimal values of π have the form 1 1−γ (n), while the maximal values of π behave as 1 log1−κ (n) for some other n log n exponent κ ∈ [0, 1]. In passing, we prove tight bounds on the diameter of the digraphs and show that the latter coincides with the typical distance between two vertices. Mathematics Subject Classification Primary 05C81 · 60J10 · 60C05; Secondary 60G42
1 Introduction The problem of determining the cover time of a graph is a central one in combinatorics and probability [3–5,18,19,21,26]. In recent years, the cover time of random graphs has been extensively studied [1,14,16,17,20]. All these works consider undirected graphs, with the notable exception of the paper [17] by Cooper and Frieze, where the authors compute the cover time of directed Erd˝os-Renyi random graphs in the regime of strong connectivity, that is with a logarithmically diverging average degree. The
B
Pietro Caputo [email protected] Matteo Quattropani [email protected]
1
Dipartimento di Matematica e Fisica, Università di Roma Tre, Largo S. Leonardo Murialdo 1, 00146 Rome, Italy
123
P. Caputo, M. Quattropani
main difficulty in the directed case is that, in contrast with the undirected case, the graph’s stationary distribution is an unknown random variable. In this paper we address the problem of determining the cover time of sparse random digraphs with bounded degrees. More specifically, we consider random digraphs G with given in- and out-degree sequences, generated via the configuration model. For the sake of this introductory discussion let us look at the special case where all vertices have either in-degree 2 and out-degree 3 or in-degree 3 and out-degree 2, with the two types evenly represented in the vertex set V (G). We refer to this as the (2, 3)(3, 2) case. With high probability G is strongly connected and we may ask how long the random walk on G takes to cover all the nodes. The expectation of this quantity, maximized over the initial point of the walk defines Tcov (G), the cover time of G. We will show that with high probability as the number of vertices n tends to infinity one has Tcov (G) n logγ (n)
(1.1)
log 3 −1 ≤ a /b ≤ C for some constant where γ = log n n
Data Loading...
