The electrical resistance of a graph captures its commute and cover times
The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Specifically, Doyle & Snell (1984) demonstrated that resistance distances from circuit theory are directly proportional to the movements of Markovian random walkers on graphs, and Chandra et al. (1996) related resistance distances to “commute times,” or the time it takes a random walker to travel from one point to another and back again.”
From Circuit‐theory applications to connectivity science and conservation (2019) · cites this paper as Chandra et al. (1996)
Citations
Cites
A treatise on electricity and magnetism
(1954) · Journal of the Franklin Institute · doi:10.1016/0016-0032(54)90053-8 · Cited by 9,077
Introduction to Probability Models.
Jolliffe, F., & Ross, S. M. (1995) · Journal of the Royal Statistical Society. Series A (Statistics in Society) · doi:10.2307/2983433 · Cited by 4,525
Franklin, J. (1968) · Cited by 1,807
Alon, N. (1986) · Combinatorica · doi:10.1007/bf02579166 · Cited by 1,137
Random Walks and Electric Networks
Doyle, P., & Snell, J. (1984) · Carus Mathematical Monographs · doi:10.5948/upo9781614440222 · Cited by 1,061
Reversible Markov Chains and Random Walks on Graphs
Aldous, D., & Fill, J. A. (2014) · Cited by 973
Jerrum, M., & Sinclair, A. (1989) · SIAM Journal on Computing · doi:10.1137/0218077 · Cited by 768
A random polynomial-time algorithm for approximating the volume of convex bodies
Dyer, M., Frieze, A., & Kannan, R. (1991) · Journal of the ACM · doi:10.1145/102782.102783 · Cited by 693
Random walks, universal traversal sequences, and the complexity of maze problems
Aleliunas, R., Karp, R. M., Lipton, R. J., Lovasz, L., & Rackoff, C. (1979) · 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) · doi:10.1109/sfcs.1979.34 · Cited by 692
Treatise on Natural Philosophy
Thomson, W., Baron, K., & Tait, P. G. (2009) · Cambridge University Press eBooks · doi:10.1017/cbo9780511703928 · Cited by 451
Cited by
Items 201–300 of 316
Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time
David, R., & Feige, U. (2018) · SIAM Journal on Computing · doi:10.1137/17m1119901 · Cited by 10
Topology-Based Spectral Sparsification
Meidiana, A., Hong, S., Huang, J., Eades, P., & Ma, K. (2019) · IEEE Symposium on Large Data Analysis and Visualization · doi:10.1109/ldav48142.2019.8944358 · Cited by 6
Concentration of the Kirchhoff index for Erdős–Rényi graphs
Boumal, N., & Cheng, X. (2014) · Systems & Control Letters · doi:10.1016/j.sysconle.2014.10.006 · Cited by 8
Deterministic approximation for the cover time of treesPreprint
Feige, U., & Zeitouni, O. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0909.2005 · Cited by 6
Unifying Constraints Linking Protein Folding and Native Dynamics Decoded from AlphaFold
Zhang, Z., Ren, W., Xie, L., Zheng, Y., Guan, X., Wang, J., Li, W., & Tang, Q.-Y. (2026) · Physical Review Letters · doi:10.1103/7j2j-f8f7 · Cited by 5
Zhang, Z., & Wu, B. (2021) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2021.3128361 · Cited by 5
Beyond GNNs: An Efficient Architecture for Graph Problems
Awasthi, P., Das, A., & Gollapudi, S. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i6.20548 · Cited by 5
Testing the (s,t) -disconnectivity of graphs and digraphs
Yoshida, Y., & Kobayashi, Y. (2012) · Theoretical Computer Science · doi:10.1016/j.tcs.2012.01.045 · Cited by 5
Distributed Network Design for Laplacian Eigenvalue Placement
Preciado, V. M., & Zavlanos, M. M. (2016) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2016.2544249 · Cited by 5
On planar graphs of uniform polynomial growth
Ebrahimnejad, F., & Lee, J. R. (2021) · Probability Theory and Related Fields · doi:10.1007/s00440-021-01045-5 · Cited by 5
Anomalous scaling regime for one-dimensional Mott variable-range hopping
Croydon, D. A., Fukushima, R., & Junk, S. (2023) · The Annals of Applied Probability · doi:10.1214/22-aap1915 · Cited by 5
Guo, Z., Li, S., Liu, X., & Mei, X. (2019) · Linear and Multilinear Algebra · doi:10.1080/03081087.2019.1643822 · Cited by 5
The power of two choices for random walks
Georgakopoulos, A., Haslegrave, J., Sauerwald, T., & Sylvester, J. (2021) · Combinatorics Probability Computing · doi:10.1017/s0963548321000183 · Cited by 5
Relations between scaling exponents in unimodular random graphs
Lee, J. R. (2023) · Geometric and Functional Analysis · doi:10.1007/s00039-023-00654-7 · Cited by 5
The Cover Time of Cartesian Product Graphs
Abdullah, M., Cooper, C., & Radzik, T. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-19222-7_37 · Cited by 5
Unifying constraints linking protein folding and native dynamics decoded from AlphaFold
Zhang, Z., Ren, W., Xie, L., Zheng, Y., Guan, X., Wang, J., Li, W., & Tang, Q.-Y. (2026) · doi:10.64898/2026.01.08.698426 · Cited by 5
Community Detection in Dense Networks using Effective Resistance and Link Pruning
Socievole, A., & Pizzuti, C. (2023) · International Conference on Information and Communication Technologies for Disaster Management (ICT-DM) · doi:10.1109/ict-dm58371.2023.10286913 · Cited by 5
Forest formulas of discrete Green's functions
Chung, F., & Zeng, J. (2022) · Journal of Graph Theory · doi:10.1002/jgt.22887 · Cited by 4
Ch. 10. Fractals and the modelling of self-similarity
Hambly, B. M. (2003) · Handbook of statistics · doi:10.1016/s0169-7161(03)21012-9 · Cited by 4
Does adding more agents make a difference? A case study of cover time for the rotor-router
Kosowski, A., & Pająk, D. (2019) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2019.07.001 · Cited by 4
Simple random walk on distance-regular graphsPreprint
Markowsky, G. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.6394 · Cited by 4
SPADE: A Spectral Method for Black-Box Adversarial Robustness EvaluationPreprint
Cheng, W., Deng, C., Zhao, Z., Cai, Y., Zhang, Z., & Feng, Z. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.03716 · Cited by 11
Liu, C., Zhan, M., Zhao, X., Wei, J., Hu, Y., Li, C., Chu, Y., & Sun, F. (2026) · Buildings · doi:10.3390/buildings16020329 · Cited by 3
On the Hitting Time Index of Broom Graphs
Palacios, J. L. (2026) · Mathematics · doi:10.3390/math14091508 · Cited by 3
How slow, or fast, are standard random walks? - Analysis of hitting and cover times on trees
Nonaka, Y., Ono, H., Kijima, S., & Yamashita, M. (2011) · Computing: The Australasian Theory Symposium · Cited by 3
On the Structure and Computation of Random Walk Times in Finite Graphs
Clark, A., Alomair, B., Bushnell, L. G., & Poovendran, R. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2895299 · Cited by 5
Random spanning trees for expanders, sparsifiers, and virtual network security
Dolev, S., & Khankin, D. (2023) · Computer Communications · doi:10.1016/j.comcom.2023.09.028 · Cited by 3
Ambrose, L., Hanson, J. O., Riginos, C., Xu, W., Fordyce, S. L., Cooper, R. D., & Beebe, N. W. (2019) · Ecology and Evolution · doi:10.1002/ece3.5792 · Cited by 3
EXPANSION CONSTANTS AND HYPERBOLIC EMBEDDINGS OF FINITE GRAPHS
Hattori, T., & Kasue, A. (2014) · Mathematika · doi:10.1112/s0025579314000254 · Cited by 3
Devulapalli, P., Dilkina, B., & Xue, Y. (2020) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2020/598 · Cited by 3
Learning Networks from Random Walk-Based Node SimilaritiesPreprint
Hoskins, J. G., Musco, C., Musco, C., & Tsourakakis, C. E. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1801.07386 · Cited by 5
dyGRASS: Dynamic Spectral Graph Sparsification via Localized Random Walks on GPUs
Yuan, Y., Aghdaei, A., & Feng, Z. (2025) · doi:10.1109/iccad66269.2025.11240980 · Cited by 2
Resistance distances and Kirchhoff indices in graph joins
Sedlák, J., & Slavík, A. (2025) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8121/ae2997 · Cited by 2
A Characterization of Effective Resistance Metrics
Weihrauch, T. (2018) · Potential Analysis · doi:10.1007/s11118-018-9718-2 · Cited by 2
Random walk on barely supercritical branching random walk
van der Hofstad, R., Hulshof, T., & Nagel, J. (2019) · Probability Theory and Related Fields · doi:10.1007/s00440-019-00942-0 · Cited by 2
Kernels on Attributed Networks for Community Detection
Pizzuti, C., & Socievole, A. (2022) · International Conference on Information, Intelligence, Systems & Applications (IISA) · doi:10.1109/iisa56318.2022.9904348 · Cited by 2
Effective Resistance Based Weight Thresholding for Community Detection
Pizzuti, C., & Socievole, A. (2022) · Communications in computer and information science · doi:10.1007/978-3-031-23929-8_2 · Cited by 2
Iwama, K., & Yoshida, Y. (2014) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2554797.2554843 · Cited by 2
Averaging with Exogenous Inputs and Electrical Networks
Fagnani, F., & Frasca, P. (2017) · Lecture notes in control and information sciences · doi:10.1007/978-3-319-68022-4_5 · Cited by 2
Novel Resistive Distance Descriptors on Complex Network
Li, M., Zhou, S., Chen, G., Lin, W., & Zhou, Q. (2022) · IEEE Access · doi:10.1109/access.2022.3147817 · Cited by 2
Spectral analysis of weighted neighborhood networks
Muthuraman, S., & Rajkumar, R. (2022) · Discrete Mathematics Algorithms and Applications · doi:10.1142/s1793830922501415 · Cited by 2
Dumbbell Graphs with Extremal (Reverse) Cover Cost
Jin, Z., Shi, Y., Wang, S., & Gui, X. (2022) · Bulletin of the Malaysian Mathematical Sciences Society · doi:10.1007/s40840-022-01433-7 · Cited by 2
Mamode, M. (2023) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8121/accfd5 · Cited by 2
Pseudoinverses of Signed Laplacian Matrices
Fontan, A., & Altafini, C. (2023) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/22m1493392 · Cited by 7
Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation
Becchetti, L., Bonifaci, V., & Natale, E. (2018) · Adaptive Agents and Multi-Agents Systems · doi:10.65109/woif2954 · Cited by 2
Symmetric Walks on Paths and Cycles
Maiti, S. I., & Sarkar, J. (2019) · Mathematics Magazine · doi:10.1080/0025570x.2019.1611166 · Cited by 2
Graph Learning for Inverse Landscape Genetics
Dharangutte, P., & Musco, C. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i17.17731 · Cited by 2
Bernard, T., & BUI, A. (2006) · OpenGrey (Institut de l'Information Scientifique et Technique) · Cited by 2
Local ergodicity in the exclusion process on an infinite weighted graphPreprint
Chen, J. P. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.10290 · Cited by 2
Consensus-Building on Citations in Peer-to-Peer SystemsPreprint
Ito, K. (2021) · SSRN Electronic Journal · doi:10.2139/ssrn.3936833 · Cited by 3
Algorithms for deterministic parallel graph exploration
Pająk, D. (2014) · theses.fr (ABES) · doi:10.70675/58e2747az6a79z40dezb604zbcda2fb26d19 · Cited by 2
Vaskouski, M. M., & Zadarazhniuk, H. A. (2024) · Journal of Algebraic Combinatorics · doi:10.1007/s10801-024-01302-5 · Cited by 1
Effective Resistance Based Community Detection in Complex Networks
Socievole, A., & Pizzuti, C. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-81241-5_14 · Cited by 1
Accessibility and Runtime Between Convex Neutral Networks
Lehre, P. K., & Haddow, P. C. (2006) · Lecture notes in computer science · doi:10.1007/11903697_92 · Cited by 1
Solving the Tower of Hanoi with Random Moves
Alekseyev, M. A., & Berger, T. (2015) · Princeton University Press eBooks · doi:10.23943/princeton/9780691164038.003.0005 · Cited by 1
Time and Space-Efficient Algorithms for Mobile Agents in an Anonymous Network
Kosowski, A. (2013) · Cited by 1
Guiding Random Walks by Effective Resistance for Effective Node Embedding
Gacem, A., Haddad, M., Seba, H., Berthe, G., & Habib, M. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-09037-0_54 · Cited by 1
Effective resistance of finite grids
Bairamkulov, R., & Friedman, E. G. (2022) · Springer eBooks · doi:10.1007/978-3-031-11047-4_7 · Cited by 1
Hitting Times of Random Walks on Edge Corona Product Graphs
Zhu, M., Xu, W., Li, W., Zhang, Z., & Kan, H. (2023) · The Computer Journal · doi:10.1093/comjnl/bxac189 · Cited by 1
Mamode, M. (2024) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8121/ad79cc · Cited by 1
Potential induced random teleportation on finite graphs
Chow, S.-N., Ye, X., & Zhou, H. (2015) · Computational Optimization and Applications · doi:10.1007/s10589-015-9727-7 · Cited by 1
A Spectral Approach to Network Design
Lau, L. C., & Zhou, H. M. (2022) · SIAM Journal on Computing · doi:10.1137/20m1330762 · Cited by 1
Chen, T., Dai, M., Huang, F., & Feng, S. (2020) · Fractals · doi:10.1142/s0218348x20500784 · Cited by 1
Sketch-based Community Detection via Representative Node Sampling
Sedghi, M., Beckus, A., & Atia, G. (2021) · Proceedings - International Conference on Pattern Recognition/Proceedings/International Conference on Pattern Recognition · doi:10.1109/icpr48806.2021.9413202 · Cited by 1
5. Solving the Tower of Hanoi with Random Moves
Alekseyev, M. A., & Berger, T. (2016) · Princeton University Press eBooks · doi:10.1515/9781400881338-007 · Cited by 1
On state estimation for nonlinear systems under random access wireless protocols
Maass, A. I., Nešić, D., Postoyan, R., & Tan, Y. (2022) · Mathematics of Control Signals and Systems · doi:10.1007/s00498-022-00337-y · Cited by 1
Reduction of Potential-Based Flow Networks
Klimm, M., Pfetsch, M. E., Raber, R., & Skutella, M. (2023) · Mathematics of Operations Research · doi:10.1287/moor.2022.1338 · Cited by 1
Modeling spatial networks by contact graphs of disk packings
Zhu, M., Sun, H., Li, W., & Zhang, Z. (2023) · Theoretical Computer Science · doi:10.1016/j.tcs.2023.114066 · Cited by 1
Extremal regime for one-dimensional Mott variable-range hopping
Croydon, D. A., Fukushima, R., & Junk, S. (2023) · Annales Henri Lebesgue · doi:10.5802/ahl.186 · Cited by 1
The Mean Time to Absorption on Horizontal Partitioned Sierpinski Gasket Networks
Zhang, Z., Wu, B., & Yu, Z. (2023) · Analysis in Theory and Applications · doi:10.4208/ata.oa-2021-0014 · Cited by 1
A flexible and interpretable spatial covariance model for data on graphs
Christensen, M. F., & Hoff, P. D. (2024) · Environmetrics · doi:10.1002/env.2879 · Cited by 2
Variational Convergence of Finite Networks
Kasue, A. (2006) · Interdisciplinary Information Sciences · doi:10.4036/iis.2006.57 · Cited by 1
Kannan, S. (2014) · doi:10.31979/etd.mw4t-bz9x · Cited by 1
On the Connectivity of Key-Distribution Strategies in Wireless Sensor Networks
Shafiei, H., Khonsari, A., Talebi, M. S., Ould‐Khaoua, M., & Dehghani, N. (2009) · Globecom · doi:10.1109/glocom.2009.5425590 · Cited by 1
Analysis of the Harmonic Algorithm for Three Servers
Chrobák, M., & Sgall, J. (2003) · Lecture notes in computer science · doi:10.1007/3-540-36494-3_23 · Cited by 1
Logarithmic proximity measures outperform plain ones in graph nodes clustering.Preprint
Ivashkin, V., & Chebotarev, P. (2016) · arXiv (Cornell University) · Cited by 1
Discovering the Network Backbone from Traffic Activity DataPreprint
Chawla, S., Garimella, K., Gionis, A., & Tsang, D. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.6138 · Cited by 1
Several consequences of adding or removing an edge from an electric networkPreprint
Markowsky, G., & Palacios, J. L. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2104.09706 · Cited by 1
Critical Phenomena on Large Graphs with Regular Subgraphs
Blanchard, P., & Volchenkov, D. (2011) · Springer series in synergetics · doi:10.1007/978-3-642-19592-1_10
Circuit Theory and Other Discrete Physical Models
Grady, L. J., & Polimeni, J. R. (2010) · Springer eBooks · doi:10.1007/978-1-84996-290-2_3
When Feedbacks Matter: Epidemics, Synchronization, and Self-regulation in Complex Networks
Blanchard, P., & Volchenkov, D. (2011) · Springer series in synergetics · doi:10.1007/978-3-642-19592-1_9
A credible property of resistance distance on real-world networks
Xiong, Y., Han, D., & Mao, Y. (2014) · International Conference on Machine Learning and Cybernetics · doi:10.1109/icmlc.2014.7009098
Bui, A., & Sohier, D. (2007) · RIVF International Conference on Computing and Communication Technologies (RIVF) · doi:10.1109/rivf.2007.369144
Jiang, L. (2013)
Span Programs, Electrical Flows, and Beyond: New Approaches to Quantum Algorithms
Wang, G. (2014) · UC Berkeley
The modulus and epidemic processes on graphs
Goering, M. (2015) · K-State Research Exchange (Kansas State University)
Input Selection for Robustness to Noise
Clark, A., Alomair, B., Bushnell, L. G., & Poovendran, R. (2015) · Communications and control engineering/Communications and control engineering series · doi:10.1007/978-3-319-26977-1_7
Coherence analysis of a class of small-world networks
He, J., Dai, M., Zong, Y., & Zou, J. (2017) · Annual Conference of the IEEE Industrial Electronics Society (IECON) · doi:10.1109/iecon.2017.8216886
On the equivalence of cylinder tilings and planar electric networks
Amiet, B., Markowsky, G., & Palacios, J. L. (2020) · Discrete Applied Mathematics · doi:10.1016/j.dam.2020.03.006
The normalized Laplacians and random walks of the parallel subdivision graphsPreprint
Zhao, J., Liu, J., Tan, Y.-Y., & Hayat, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.02549
Exploring Low-degree nodes first accelerates Network Exploration
Costantini, S., Meo, P. D., Giorgianni, A., Migliorato, V., Provetti, A., & Salvia, F. (2020) · ACM Web Science Conference (WebSci) · doi:10.1145/3394231.3397914
Structural and Algorithmic Properties of Static and Mobile Random Geometric Graphs
Stauffer, A. O. (2011) · eScholarship (California Digital Library)
Dynamic minimisation of the commute time for a one-dimensional diffusion
Hernández-Hernández, M. E., & Jacka, S. (2024) · Annals of Operations Research · doi:10.1007/s10479-024-06067-5
Cover and hitting times of hyperbolic random graphs
Kiwi, M. A., Schepers, M., & Sylvester, J. (2024) · Random Structures and Algorithms · doi:10.1002/rsa.21249 · Cited by 6
Metadata
- Authors
- Chandra, A. K., Raghavan, P., Ruzzo, W. L., Smolensky, R., & Tiwari, P.
- Affiliations
- IBM Research - Almaden (US)
- University of Washington (US)
- IBM (United States) (US)
- Corresponding author
- Chandra, Ashok K.
- Raghavan, Prabhakar
- Ruzzo, Walter L.
- Tiwari, Prasoon
- Venue
- Computational Complexity
- Published
- 1996-12
- Volume
- 6
- Issue
- 4
- Pages
- 312-340
- ISSN
- 1016-3328 (ISSN-L)
- 1420-8954
- OpenAlex
- W2048572907
- Cited by
- 328
- References
- 30
- Citations by year
- 2026: 8 · 2025: 9 · 2024: 15 · 2023: 17 · 2022: 27 · 2021: 21 · 2020: 19 · 2019: 20 · 2018: 24 · 2017: 25 · 2016: 10 · 2015: 16 · 2014: 16 · 2013: 18 · 2012: 15
- FWCI
- 1.54
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Computational Complexity (publishedVersion)
- Funders
- National Science Foundation
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Mathematics › Mathematical Physics › Stochastic processes and statistical mechanics
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Graph theory and applications
- Keywords
- graph resistance, effective resistance, commuting time, cover time, random walks, electrical networks, expander graphs
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.