Cover time of weighted graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T14:34:23Z http://mathoverflow.net/feeds/question/33057 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/33057/cover-time-of-weighted-graphs Cover time of weighted graphs MAKCL 2010-07-23T06:45:17Z 2010-08-06T11:06:26Z <p>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. </p> <p>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)\$.</p> http://mathoverflow.net/questions/33057/cover-time-of-weighted-graphs/33065#33065 Answer by James Martin for Cover time of weighted graphs James Martin 2010-07-23T08:26:37Z 2010-07-23T08:26:37Z <p>You'll need some further assumption beyond just the bound on the maximum expected hitting time.</p> <p>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}\$. </p> <p>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.</p> <p>so the process stays at some pair for time roughly exponential with mean \$n\$, before jumping to a new randomly chosen pair. </p> <p>this is essentially coupon collector. the maximum expected hitting time has order \$n^2\$ but the cover time has order \$n^2 \log n\$. </p> http://mathoverflow.net/questions/33057/cover-time-of-weighted-graphs/34752#34752 Answer by Tracy Hall for Cover time of weighted graphs Tracy Hall 2010-08-06T11:06:26Z 2010-08-06T11:06:26Z <p>A search for "algebraic connectivity" of a graph may be helpful, as well as the extensive literature on rapid mixing.</p> <p>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.</p> <p>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.</p>