A New Notion of Effective Resistance for Directed Graphs - Part I: Definition and Properties

George Forrest Young, Luca Scardovi, Naomi Ehrich Leonard

Research output: Contribution to journalArticle

23 Scopus citations

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.

Original languageEnglish (US)
Article number7276998
Pages (from-to)1727-1736
Number of pages10
JournalIEEE Transactions on Automatic Control
Volume61
Issue number7
DOIs
StatePublished - Jul 2016

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Keywords

  • Graph theory
  • directed graphs
  • effective resistance
  • networked control systems
  • networks

Fingerprint Dive into the research topics of 'A New Notion of Effective Resistance for Directed Graphs - Part I: Definition and Properties'. Together they form a unique fingerprint.

  • Cite this