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.

## Dettaglio pubblicazione

2023, RANDOM STRUCTURES & ALGORITHMS, Pages 61-101 (volume: 63)

### Expansion and flooding in dynamic random networks with node churn (*01a Articolo in rivista*)

#### Becchetti L., Clementi A., Pasquale F., Trevisan L., Ziccardi I.

**keywords**