A. K. Chandra
ABSTRACT
View an n-vertex, m-edge undirected graph as an electrical network with unit resistors as edges. We extend known relations between random walks and electrical networks by showing that resistance in this network is intimately connected with the lengths of random walks on the graph. For example, the commute time between two vertices s and t (the expected length of a random walk from s to t and back) is precisely characterized by the effective resistance Rst between s and t: commute time = 2mRst. Additionally, the cover time (the expected length of a random walk visiting all vertices) is characterized by the maximum resistance R in the graph to within a factor of log n: mR ≤ cover time ≤ O (mR log n). For many graphs, the bounds on cover time obtained in this manner are better than those obtained from previous techniques such as the eigenvalues of the adjacency matrix. In particular, using this approach, we improve known bounds on cover times for various classes of graphs, including high-degree graphs, expanders, and multi-dimensional meshes. Moreover, resistance seems to provide an intuitively appealing and tractable approach to these problems.
- 1.David J. Aldous. Random walks on large graphs, 1988. Unpublished Monograph, Berkeley.Google Scholar
- 2.R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovgsz, and C. Rackoff. Random walks, universM traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science, p~ges 218-223, San Juan, Puerto Rico, October 1979.Google ScholarDigital Library
- 3.N oga Alon. Eigenvalues and expanders. Com. binatorica, 6(2):83-96, 1986. Google ScholarDigital Library
- 4.A. Borodin, W. L. Ruzzo, and M. Tompa. Lower bounds on the length of universaZ{ traversal sequences. In P'roceedings of the 21s ! Annual A CM Symposium on Theory of Com. puting, Seattle, WA, May 1989. ACM. Google ScholarDigital Library
- 5.A. Z. Broder and A. R. Karlin. Bounds oIt covering times. In 29th Annual Symposium o~ Foundations of Computer Science, pages 479-- 487, White Plains, NY, October 1988.Google Scholar
- 6.J.T. Cox. Coalescing random walks and vote:r model consensus times on the torus, 1987. unpublished manuscript, CorneU.Google Scholar
- 7.Peter G. Doyle and J. Laurie Snell. Rando~ Walks and Electrical Networks. The Mathematical Association of America, 1984.Google Scholar
- 8.J. N. Franklin. Matrix Theory. Prentice-Hall, 1968.Google Scholar
- 9.J. Friedman and N. Pippenger. Expandin~g graphs contain all small trees. Combinatorico, pages 71-76, 1987. Google ScholarDigital Library
- 10.F. GSbel and A. A. Jagers. Random walks oll graphs. Stochastic Proces,~es and their Applications, 2:311-336, 1974.Google Scholar
- 11.Mark Jerrum and Alista.ir Sinclair. Conductance and the rapid raixing property for Markov chains: the appro~dmation of the peimanent resolved. In Proceedings of the 20ta Annual ACM Symposium on Theory of Computing, pages 235-244, May 1988. Google ScholarDigital Library
- 12.Jeff D. Kahn, Nathan Linial, Noam Nisan, and Michael E. Saks. On the cover time of randoIn walks in graphs. Journal of Theoretical Probability, 1, 1989. To Appear.Google Scholar
- 13.J.G. Kemeny, J. L. Snell. and A.W. KnapI~. Denumerable Markov Chains. The Universily Series in Higher Mathematics. Van Nostran(l, Princeton, NJ, 1966.Google Scholar
- 14.H. J. Landau and A. M. Odlyzko. Bounc.s for eigenvalues of certain stochastic matrices. Linear Algebra and Its A2plications, 38:5-1~, 1981.Google Scholar
- 15.Peter Mathews. Covering problems for random walks on spheres and finite groups. Technical Report TR 234, Stanford, Department of Statistics, 1985.Google Scholar
- 16.J. C. Maxwell. A Treatise on Electricity and Magnetism. Clarendon, 1918.Google Scholar
- 17.David Peleg and Eli UpfM. Constructing disjoint paths on expander graphs. In Proceedings of the 19th Annual A CM Symposium on Theory of Computing, pages 264-273, May 1987. Google ScholarDigital Library
- 18.Ronitt Rubinfeld. Personal communication. 1989.Google Scholar
- 19.J.L. Synge. The fundamental theorem of electrical networks. Quarterly of Applied Math., 9:113-127, 1951.Google ScholarCross Ref
- 20.W. Thomson and P.G. TaR. Treatise on Natural Philosophy. Cambridge, 1879.Google Scholar
- 21.David I. Zuckerman. A technique for lower bounding the cover time, 1989. Llnpublished manuscript, Berkeley.Google Scholar
Index Terms
- The electrical resistance of a graph captures its commute and cover times
Recommendations
Commute times for graph spectral clustering
CAIP'05: Proceedings of the 11th international conference on Computer Analysis of Images and PatternsThis paper exploits the properties of the commute time to develop a graph-spectral method for image segmentation. Our starting point is the lazy random walk on the graph, which is determined by the heat-kernel of the graph and can be computed from the ...
Comparability Graphs Among Cover-Incomparability Graphs
Algorithms and Discrete Applied MathematicsAbstractComparability graphs and cover-incomparability graphs (C-I graphs) are two interesting classes of graphs from posets. Comparability graph of a poset is a graph with vertex set V and two vertices u and v are adjacent in V if u and v are ...
Three ways to cover a graph
We consider the problem of covering an input graph H with graphs from a fixed covering class G . The classical covering number of H with respect to G is the minimum number of graphs from G needed to cover the edges of H without covering non-edges of H . ...
Comments