Random Walks on Evolving Graphs with Recurring Topologies

In this paper we consider dynamic networks that can change over time. Often, such networks have a repetitive pattern despite constant and otherwise unpredictable changes. Based on this observation, we introduce the notion of a

ρ-recurring family

of a dynamic network, which has the property that the dynamic network frequently contains a graph in the family, where frequently means at a rate 0<

ρ

 ≤ 1. Using this concept, we reduce the analysis of max-degree random walks on dynamic networks to the case for static networks. Given a dynamic network with a

ρ

-recurring family

$\mathcal{F}$

, we prove an upper bound of

on the hitting and cover times, and an upper bound of

$O\left( \rho^{-1}(1- \hat\lambda(\mathcal{F}))^{-1} \log n \right) $

on the mixing time of random walks, where

n

is the number of nodes,

$\hat t_{hit}(\mathcal{F})$

is upper bound on the hitting time of graphs in

$\mathcal{F}$

, and

$\hat\lambda(\mathcal{F})$

is upper bound on the second largest eigenvalue of the transition matrices of graphs in

$\mathcal{F}$

. These results have two implications. First, they yield a general bound of

$O\left( \rho^{-1} n^3 \log n \right) $

on the hitting time and cover time of a dynamic network (

ρ

is the rate at which the network is connected); this result improves on the previous bound of

$O\left( \rho^{-1} n^5 \log^2 n \right) $

,[3]. Second, the results imply that dynamic networks with recurring families preserve the properties of random walks in their static counterparts. This result allows importing the extensive catalogue of results for static graphs (cliques, expanders, regular graphs, etc.) into the dynamic setting.