TY - JOUR
T1 - A New Notion of Effective Resistance for Directed Graphs - Part I
T2 - Definition and Properties
AU - Young, George Forrest
AU - Scardovi, Luca
AU - Leonard, Naomi Ehrich
N1 - Funding Information:
This work was supported in part by AFOSR Grant FA9550-07-1-0-0528, ONR Grants N00014-09-1-1074, N00014-14-1-0635, ARO Grants W911NG-11-1-0385, W911NF-14-1-0431, and by the Natural Sciences and Engineering Research Council (NSERC) of Canada.
Publisher Copyright:
© 2015 IEEE.
PY - 2016/7
Y1 - 2016/7
N2 - 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.
AB - 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.
KW - Graph theory
KW - directed graphs
KW - effective resistance
KW - networked control systems
KW - networks
UR - http://www.scopus.com/inward/record.url?scp=84977073936&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84977073936&partnerID=8YFLogxK
U2 - 10.1109/TAC.2015.2481978
DO - 10.1109/TAC.2015.2481978
M3 - Article
AN - SCOPUS:84977073936
SN - 0018-9286
VL - 61
SP - 1727
EP - 1736
JO - IRE Transactions on Automatic Control
JF - IRE Transactions on Automatic Control
IS - 7
M1 - 7276998
ER -