We study expansion and information diffusion in dynamic networks, that is in networks in which nodes and edges are continuously created and destroyed. We consider information diffusion by {em flooding}, the process by which, once a node is informed,
it broadcasts its information to all its neighbors. We study models in which the network is {em sparse}, meaning that it has $mathcal{O}(n)$ edges, where $n$ is the number of nodes, and in which edges are created randomly, rather than according to a carefully designed distributed algorithm. In our models, when a node is born, it connects to $d=mathcal{O}(1)$ random other nodes. An edge remains alive as long as both its endpoints do. If no further edge creation takes place, we show that, although the network will have $Omega_d(n)$ isolated nodes, it is possible, with large constant probability, to inform a $1-exp(-Omega(d))$ fraction of nodes in $mathcal{O}(log n)$ time. Furthermore, the graph exhibits, at any given time, a large-set expansion property. We also consider models with {em edge regeneration}, in which if an edge $(v,w)$ chosen by $v$ at birth goes down because of the death of $w$, the edge is replaced by a fresh random edge $(v,z)$. In models with edge regeneration, we prove that the network is, with high probability, a vertex expander at any given time, and flooding takes $mathcal{O}(log n)$ time. The above results hold both for a simple but artificial streaming model of node churn, in which at each time step one node is born and the oldest node dies, and in a more realistic continuous-time model in which the time between births is Poisson and the lifetime of each node follows an exponential distribution.
Spectral techniques have proved amongst the most effective approaches to graph clustering. However, in general they require explicit computation of the main eigenvectors of a suitable matrix (usually the Laplacian matrix of the graph). Recent work (e
.g., Becchetti et al., SODA 2017) suggests that observing the temporal evolution of the power method applied to an initial random vector may, at least in some cases, provide enough information on the space spanned by the first two eigenvectors, so as to allow recovery of a hidden partition without explicit eigenvector computations. While the results of Becchetti et al. apply to perfectly balanced partitions and/or graphs that exhibit very strong forms of regularity, we extend their approach to graphs containing a hidden $k$ partition and characterized by a milder form of volume-regularity. We show that the class of $k$-volume-regular graphs is the largest class of undirected (possibly weighted) graphs whose transition matrix admits $k$ stepwise eigenvectors (i.e., vectors that are constant over each set of the hidden partition). To obtain this result, we highlight a connection between volume regularity and lumpability of Markov chains. Moreover, we prove that if the stepwise eigenvectors are those associated to the first $k$ eigenvalues and the gap between the $k$-th and the ($k$+1)-th eigenvalues is sufficiently large, the averaging dynamics of Becchetti et al. recovers the underlying community structure of the graph in logarithmic time, with high probability.
