Flooding time in edge-Markovian dynamic graphs

Abstract

We introduce stochastic time-dependency in evolving graphs: starting from an arbitrary initial edge probability distribution, at every time step, every edge changes its state (existing or not) according to a two-state Markovian process with probabilities p (edge birth-rate) and q (edge death-rate). If an edge exists at time t then, at time t+1, it dies with probability q. If instead the edge does not exist at time t, then it will come into existence at time t+1 with probability p.