Expansion and flooding in dynamic random networks with node churn

We study expansion and flooding in evolving graphs, when nodes and edges are continuously created and removed. We consider a model with Poisson node inter-arrival and exponential node survival times. Upon joining the network, a node connects to d = O(1) random nodes, while an edge disappears whenever one of its endpoints leaves the network. For this model, we show that, although the graph has Ω d (n) isolated nodes with large, constant probability, flooding still informs a fraction 1 − exp(−Ω(d)) of the nodes in time O(log n). Moreover, at any given time, the graph exhibits a “large-set expansion” property. We further consider a model in which each edge leaving the network is replaced by a fresh, random one. In this second case, we prove that flooding informs all nodes in time O(log n), with high probability. Moreover, the graph is a vertex expander with high probability.