Expansion and Flooding in Dynamic Random Networks with Node Churn

We study expansion and information diffusion properties of dynamic networks, i.e., networks whose topologies evolve over time as nodes enter or leave the system and edges are continuously created or destroyed. In this scenario, we investigate flooding as a basic information diffusion mechanism. We are interested in models that are likely to result in sparse networks, i.e., in networks containing
$O(n)$
edges, with
$n$
the number of nodes that are present at any given time of interest, with a focus on models in which edges are created randomly according to simple probabilistic mechanisms, rather than according to carefully designed distributed algorithms. In this perspective, in all models we consider, upon joining the network, a node connects to
$d=O(1)$
random nodes currently in the system. On the other hand, an edge remains alive as long as both its endpoints are. For the case in which edges that fail (because one endpoint left the network) are not replaced, we show that, although the network is likely to contain
$\Omega_{d}(n)$
isolated nodes, flooding still informs a fraction
$1-\exp(-\Omega(d))$
of the nodes in time
$\mathrm{O}(\log n)$
with large, constant probability. Moreover, we are able to show, that at any given time, the graph exhibits a “large-set expansion” property. We further investigate models that exhibit edge regeneration, meaning that, whenever an edge
$(v, w)$
established by
$v$
fails because
$w$
leaves the network, it is replaced by a new random edge
$(v, z)$
. We show that models with edge regeneration result in evolving networks that, at any given time, are vertex expanders with high probability, so that flooding takes
$\mathrm{O}(\log n)$
time. The above results hold both for a simplfied streaming model of node churn and in a more realistic, continuous-time setting, in which the interval between two consecutive node arrivals follows a Poisson distribution, while nodes' lifetimes follow an exponential distribution. Previous work considered models in which either the vertex set is fixed or edges are established according to more or less sophisticated algorithms. Our motivation for studying models with simple and random edge creation mechanisms is to move one step further towards models that may eventually capture key aspects of the formation of social or peer-to-peer networks.