A New Notion of Effective Resistance for Directed Graphs—Part I: Definition and Properties
Authors:
- 25 September 2015
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 61 (7) , 1727-1736
Abstract
The graphical notion of effective resistance has found wide-ranging applications in many areas of pure mathematics, applied mathematics and control theory. By the nature of its construction, effective resistance can only be computed in undirected graphs and yet in several areas of its application, directed graphs arise as naturally (or more naturally) than undirected ones. In Part I of this work, we propose a generalization of effective resistance to directed graphs that preserves its control-theoretic properties in relation to consensus-type dynamics. We proceed to analyze the dependence of our algebraic definition on the structural properties of the graph and the relationship between our construction and a graphical distance. The results make possible the calculation of effective resistance between any two nodes in any directed graph and provide a solid foundation for the application of effective resistance to problems involving directed graphs.Keywords
Funding Information
- AFOSR (FA9550-07-1-0-0528)
- ONR (N00014-09-1-1074, N00014-14-1-0635)
- ARO (W911NG-11-1-0385, W911NF-14-1-0431)
- Natural Sciences and Engineering Research Council of Canada
This publication has 31 references indexed in Scilit:
- Minimizing Effective Resistance of a GraphSIAM Review, 2008
- On the spectra of nonsymmetric Laplacian matricesLinear Algebra and its Applications, 2005
- Consensus Problems in Networks of Agents With Switching Topology and Time-DelaysIEEE Transactions on Automatic Control, 2004
- The electrical resistance of a graph captures its commute and cover timescomputational complexity, 1996
- Extensions of the Wiener NumberJournal of Chemical Information and Computer Sciences, 1996
- The Quasi-Wiener and the Kirchhoff Indices CoincideJournal of Chemical Information and Computer Sciences, 1996
- Molecular cyclicity and centricity of polycyclic graphs. I. Cyclicity based on resistance distances or reciprocal distancesInternational Journal of Quantum Chemistry, 1994
- Resistance distanceJournal of Mathematical Chemistry, 1993
- Random walks and the effective resistance of networksJournal of Theoretical Probability, 1991
- An Electrical LemmaMathematics Magazine, 1987