Hitting time analysis on smoothed dynamic graphs

The random walk can be a very useful tool in distributed algorithms. This is because it is lightweight, simple and local in the sense that no global information is needed. Additionally, since the process is random, it seems likely that it will intuitively be robust to dynamic changes in the graph. We explore to what extent this is true.

Theorem 1: There exists a dynamic graph $\mathcal{G}=(V, \mathcal{E})$ for which the maximum hitting time is $2^{\Omega(n)}$.

proof idea. We construct a dynamic graph $\mathcal{G}$ which is a star over $n$ vertices. Vertex $n$ remains a leaf and all others move clockwise around the center taking turns being the center vertex. Thus after exiting the center, a vertex will be a leaf for $n-2$ rounds. If we start the random walk from a leaf we have two options, move to center or stay at the same leaf. If we move to the center, the center then becomes a leaf, getting us nowhere. Thus we need to stay at the leaf until it is the vertex's turn to become the center. This means staying at the leaf for $n-2$ rounds, which occurs with probability $1/2^{n-2}$. Then we expect this sequence of moves to occur once every $2^{n-2}$ moves, giving the theorem.

This is quite discouraging since it seems as though random walks are no longer feasible as graph exploration methods in dynamic graphs. However, we can analyse hitting time under $k$-smoothing and see if this improves the hitting time.

We can show that this exponential lower bound on hitting time (and hence cover time) is fragile in the sense that if we add a small number of random edges to our worst-case graph, the resulting graph has polynomial hitting time.

Theorem 2: The maximum hitting time $H(u,v)$ of a random walk on any $k$-smoothed dynamic graph is $O(n^3/k)$.

proof. Suppose the random walk is at vertex $w$. If there is an edge $\{w,v\}$, then with probability at least $1-k/n^2$ it will remain an edge under smoothing. If there is no such edge, then an edge $\{w,v\}$ will be added by smoothing with probability at least $k/n^2$. Then if the edge $\{w,v\}$ is actually in the smoothed graph, we have at least $1/n$ probability of the random walk moving to $v$. Therefore, we have at least $k/n^3$ probability of moving to $v$ at each step. Therefore, we expect to reach $v$ in $O(n^3/k)$ steps.

We can also give a lower bound on the maximum hitting time.

Theorem 3: The maximum hitting time $H(u,v)$ of a random walk on a $k$-smoothed dynamic graph is $\Omega(n^{5/2}(\sqrt{k}\ln{n}))$.

The proof is omitted.