A Dynamic Erd\H{o}s\tire R\'enyi Graph Model

S. Rosengren, P. Trapman

2019, v.25, Issue 2, 275-301

ABSTRACT

In this article we study a dynamic Erd\H{o}s\tire R\'enyi graph model, in which, independently for each vertex pair, edges appear and disappear according to a Markov on-off process.

In studying the dynamic graph we present the following results. The first being on how long it takes for the graph to reach stationarity. We give an explicit expression for this time, as well as proving that this is the fastest time to reach stationarity among all strong stationary times.

The main result concerns the time it takes for the dynamic graph to reach a certain number of edges. We give an explicit expression for the expected value of such a time, as well as study its asymptotic behavior. This can be used to determine how a large component emerges, is it through many edges being present or by an unlikely configuration of fewer edges? In the critical case, a large component emerges through an unlikely configuration of relatively few edges.

Keywords: %Dynamic Erd\H{o}s-Rényi Graph; Erd\H{o}s\tire R\'enyi Graph; Markov Process; fastest time to stationarity; strong stationary times; hitting times} % insert keywords separated by a semicolon \AMSclass{Primary 05C80; Secondary 60G99

COMMENTS

Please log in or register to leave a comment