Article

Free access

The electrical resistance of a graph captures its commute and cover times

Authors:

R. SmolenskyAuthors Info & Claims

STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing

Pages 574 - 586

https://doi.org/10.1145/73007.73062

Published: 01 February 1989 Publication History

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 R_st between s and t: commute time = 2mR_st. 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.

References

[1]

David J. Aldous. Random walks on large graphs, 1988. Unpublished Monograph, Berkeley.

[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.

Digital Library

[3]

N oga Alon. Eigenvalues and expanders. Com. binatorica, 6(2):83-96, 1986.

Digital 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.

Digital 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.

[6]

J.T. Cox. Coalescing random walks and vote:r model consensus times on the torus, 1987. unpublished manuscript, CorneU.

[7]

Peter G. Doyle and J. Laurie Snell. Rando~ Walks and Electrical Networks. The Mathematical Association of America, 1984.

[8]

J. N. Franklin. Matrix Theory. Prentice-Hall, 1968.

[9]

J. Friedman and N. Pippenger. Expandin~g graphs contain all small trees. Combinatorico, pages 71-76, 1987.

Digital Library

[10]

F. GSbel and A. A. Jagers. Random walks oll graphs. Stochastic Proces,~es and their Applications, 2:311-336, 1974.

[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.

Digital 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.

[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.

[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.

[15]

Peter Mathews. Covering problems for random walks on spheres and finite groups. Technical Report TR 234, Stanford, Department of Statistics, 1985.

[16]

J. C. Maxwell. A Treatise on Electricity and Magnetism. Clarendon, 1918.

[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.

Digital Library

[18]

Ronitt Rubinfeld. Personal communication. 1989.

[19]

J.L. Synge. The fundamental theorem of electrical networks. Quarterly of Applied Math., 9:113-127, 1951.

[20]

W. Thomson and P.G. TaR. Treatise on Natural Philosophy. Cambridge, 1879.

[21]

David I. Zuckerman. A technique for lower bounding the cover time, 1989. Llnpublished manuscript, Berkeley.

Cited By

Ahmad YAli UOtera DPan X(2024)Study of Random Walk Invariants for Spiro-Ring Network Based on Laplacian MatricesMathematics10.3390/math1209130912:9(1309)Online publication date: 25-Apr-2024
https://doi.org/10.3390/math12091309
Ma FWang P(2024)Determining Mean First-Passage Time for Random Walks on Stochastic Uniform Growth Tree NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.339278636:11(5940-5953)Online publication date: Nov-2024
https://doi.org/10.1109/TKDE.2024.3392786
Zhu MZhu LLi HLi WZhang Z(2024)Resistance Distances in Directed Graphs: Definitions, Properties, and ApplicationsTheoretical Computer Science10.1016/j.tcs.2024.114700(114700)Online publication date: Jun-2024
https://doi.org/10.1016/j.tcs.2024.114700
Show More Cited By

Index Terms

The electrical resistance of a graph captures its commute and cover times
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Enumeration
    2. Graph theory
      1. Network flows
  2. Mathematical analysis
    1. Functional analysis
      1. Approximation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Graph algorithms analysis
      1. Network flows

Recommendations

Commute times for graph spectral clustering
CAIP'05: Proceedings of the 11th international conference on Computer Analysis of Images and Patterns

This 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 Mathematics
Abstract
Comparability graphs and cover-incomparability graphs (C-I graphs) are two interesting classes of graphs from posets. Comparability graph of a poset $P = (V, \leq)$ is a graph with vertex set V and two vertices u and v are adjacent in V if u and v are ...
Hitting and commute times in large random neighborhood graphs

In machine learning, a popular tool to analyze the structure of graphs is the hitting time and the commute distance (resistance distance). For two vertices u and v, the hitting time H_uv is the expected time it takes a random walk to travel from u to v. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing

February 1989

600 pages

ISBN:0897913078

DOI:10.1145/73007

Editor:
D. S. Johnson

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC89

Sponsor:

SIGACT

STOC89: 21st Annual ACM Symposium on the Theory of Computing

May 14 - 17, 1989

Washington, Seattle, USA

Acceptance Rates

STOC '89 Paper Acceptance Rate 56 of 196 submissions, 29%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

166
Total Citations
View Citations
1,578
Total Downloads

Downloads (Last 12 months)249
Downloads (Last 6 weeks)36

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ahmad YAli UOtera DPan X(2024)Study of Random Walk Invariants for Spiro-Ring Network Based on Laplacian MatricesMathematics10.3390/math1209130912:9(1309)Online publication date: 25-Apr-2024
https://doi.org/10.3390/math12091309
Ma FWang P(2024)Determining Mean First-Passage Time for Random Walks on Stochastic Uniform Growth Tree NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.339278636:11(5940-5953)Online publication date: Nov-2024
https://doi.org/10.1109/TKDE.2024.3392786
Zhu MZhu LLi HLi WZhang Z(2024)Resistance Distances in Directed Graphs: Definitions, Properties, and ApplicationsTheoretical Computer Science10.1016/j.tcs.2024.114700(114700)Online publication date: Jun-2024
https://doi.org/10.1016/j.tcs.2024.114700
Sajjad WSardar MPan X(2024)Computation of resistance distance and Kirchhoff index of chain of triangular bipyramid hexahedronApplied Mathematics and Computation10.1016/j.amc.2023.128313461:COnline publication date: 15-Jan-2024
https://dl.acm.org/doi/10.1016/j.amc.2023.128313
Hernández-Hernández MJacka S(2024)Dynamic minimisation of the commute time for a one-dimensional diffusionAnnals of Operations Research10.1007/s10479-024-06067-5Online publication date: 18-Jun-2024
https://doi.org/10.1007/s10479-024-06067-5
Salkhi Khasraghi GVolchenkov DNejat AHernandez R(2023)University Campus as a Complex Pedestrian Dynamic Network: A Case Study of Walkability Patterns at Texas Tech UniversityMathematics10.3390/math1201014012:1(140)Online publication date: 31-Dec-2023
https://doi.org/10.3390/math12010140
Xu WZhang Z(2023)Optimal Scale-Free Small-World Graphs with Minimum Scaling of Cover TimeACM Transactions on Knowledge Discovery from Data10.1145/358369117:7(1-19)Online publication date: 6-Apr-2023
https://dl.acm.org/doi/10.1145/3583691
Liu HYang XXu C(2023)Counterfactual Scenario-relevant Knowledge-enriched Multi-modal Emotion ReasoningACM Transactions on Multimedia Computing, Communications, and Applications10.1145/358369019:5s(1-25)Online publication date: 7-Jun-2023
https://dl.acm.org/doi/10.1145/3583690
Lakhotia KKannan RPrasanna V(2023)Parallel Peeling of Bipartite Networks for Hierarchical Dense Subgraph DiscoveryACM Transactions on Parallel Computing10.1145/358308410:2(1-35)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3583084
Li XWei WZhang RShi ZZheng ZFeng X(2023)Representation Learning of Enhanced Graphs Using Random Walk Graph Convolutional NetworkACM Transactions on Intelligent Systems and Technology10.1145/358284114:3(1-21)Online publication date: 24-Mar-2023
https://dl.acm.org/doi/10.1145/3582841
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents