Cover time of weighted graphs - MathOverflow

Cover time of weighted graphs

2010-07-23T06:45:17Z

Consider a connected graph $G$ with non-negative weights on each edge. The sum of edge weights is the same for each vertex, call this sum $W$. A random walk on the graph at vertex $u$ transitions an edge $(u,v)$ with probability w(u)/W.

The uniform weights imply a uniform staionary distribution. Can we say, that like unweighted regular graphs, the cover time is $O(n^2)$? If it helps, we can include that the maximum hitting time is known to be $O(n^2)$.

Answer by James Martin for Cover time of weighted graphs

2010-07-23T08:26:37Z

You'll need some further assumption beyond just the bound on the maximum expected hitting time.

for example, for $n$ even consider a graph on $n$ vertices arranged into $n/2$ pairs. If $u$ and $v$ are a pair of vertices, let the edge between them have weight $1$, otherwise let it have weight $n^{-2}$.

now the probability of jumping from one vertex to the other in the same pair is roughly $1-1/n$. Otherwise, the walk chooses between all other vertices uniformly at random.

so the process stays at some pair for time roughly exponential with mean $n$, before jumping to a new randomly chosen pair.

this is essentially coupon collector. the maximum expected hitting time has order $n^2$ but the cover time has order $n^2 \log n$.

Answer by Tracy Hall for Cover time of weighted graphs

2010-08-06T11:06:26Z

A search for "algebraic connectivity" of a graph may be helpful, as well as the extensive literature on rapid mixing.

The problems mainly occur when the graph is nearly disconnected because different component-like sets have too few edges between them, or edges with weights too close to zero (which is the weight of a non-edge). If you make certain edges exponentially small, the cover time also becomes exponential.

Your adjacency matrix has Perron root and spectral radius $W$, and the usual bounds on mixing or covering time are in terms of the eigenvalue of second-highest magnitude, as a fraction of $W$. (Bipartite graphs are a special case, where $-W$ is also an eigenvalue.) The limiting distribution, in this case uniform, is the $W$ eigenvector, and is the only all-positive eigenvector. Convergence to uniform is exponential, but with base the ratio of $W$ to other eigenvalues, by the spectral decomposition theorem. Sometimes you can actually get a clue to the worst component-like pieces from the positive and negative parts of large eigenvectors.