Average resistance of toroidal graphs

DOI10.1137/130936117MaRDI QIDQ2942289zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

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)