Average resistance of toroidal graphs

DOI10.1137/130936117zbMATH Open1327.93376arXiv1309.2172OpenAlexW1514420309MaRDI QIDQ2942289FDOQ2942289

Authors: Wilbert Samuel Rossi, Paolo Frasca, Fabio Fagnani 

Publication date: 20 August 2015

Published in: SIAM Journal on Control and Optimization (Search for Journal in Brave)

Abstract: The average effective resistance of a graph is a relevant performance index in many applications, including distributed estimation and control of network systems. In this paper, we study how the average resistance depends on the graph topology and specifically on the dimension of the graph. We concentrate on $d$-dimensional toroidal grids and we exploit the connection between resistance and Laplacian eigenvalues. Our analysis provides tight estimates of the average resistance, which are key to study its asymptotic behavior when the number of nodes grows to infinity. In dimension two, the average resistance diverges: in this case, we are able to capture its rate of growth when the sides of the grid grow at different rates. In higher dimensions, the average resistance is bounded uniformly in the number of nodes: in this case, we conjecture that its value is of order $1/d$ for large $d$. We prove this fact for hypercubes and when the side lengths go to infinity.

Full work available at URL: https://arxiv.org/abs/1309.2172

Recommendations

• Effective graph resistance
• Minimizing Effective Resistance of a Graph
• Sum rules for effective resistances in infinite graphs
• The Kirchhoff index of toroidal meshes and variant networks
• Random walks and the effective resistance of networks

zbMATH Keywords

consensuseffective resistancegraph dimensionlarge graphsrelative estimation

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Estimation and detection in stochastic control theory (93E10) Applications of graph theory to circuits and networks (94C15)

Cites Work

• Who's \#1? The science of rating and ranking
• Title not available (Why is that?)
• Estimation From Relative Measurements: Electrical Analogy and Large Graphs
• Coherence in Large-Scale Networks: Dimension-Dependent Limitations of Local Feedback
• Distributed average consensus with least-mean-square deviation
• Communication constraints in the average consensus problem
• A survey on distributed estimation and control applications using linear consensus algorithms
• The electrical resistance of a graph captures its commute and cover times
• LATIN 2004: Theoretical Informatics
• Minimizing Effective Resistance of a Graph
• Error Scaling Laws for Linear Optimal Estimation From Relative Measurements
• An Asynchronous Consensus-Based Algorithm for Estimation From Noisy Relative Measurements
• Ergodic Randomized Algorithms and Dynamics Over Networks
• Theory of resistor networks: the two-point resistance
• Optimal data collection for informative rankings expose well-connected graphs
• Resistance-based performance analysis of the consensus algorithm over geometric graphs
• Mean square performance of consensus-based distributed estimation over regular geometric graphs
• Notes on upper and lower bounds of two inequalities for the gamma function

This page was built for publication: Average resistance of toroidal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942289)