Expected flooding time in continuous time edge- markovian graphs

This paper studies the flooding time in evolving undirected graphs where the presence of edges is regulated by independent ON–OFF processes. This class of graphs includes continuous-time edge-Markovian graphs. We first derive the exact expression of the expected flooding time in matrix form, that we specialize in the large scale and quasi-sparse (i.e., when the edges are ON for a small time) regimes. The analysis is extended to the more general case where nodes are independently idle with some probability. A lower and an upper bound for the flooding time that can be computed with reduced complexity are then proposed. We claim that our general results can be applied to analyze the information diffusion speed in social and telecommunication networks, as well as the spreading of infection in epidemic networks.