A New Notion of Effective Resistance for Directed Graphs—Part I: Definition and Properties
A New Notion of Effective Resistance for Directed Graphs—Part I: Definition and Properties
复制标题
有向图有效阻力的新概念——第一部分：定义和性质
DOI：
10.1109/tac.2015.2481978
复制
发表时间：
2013
影响因子：
6.8
通讯作者：
Naomi Ehrich Leonard
中科院分区：
文献类型：
--
作者：
G. F. Young;L. Scardovi;Naomi Ehrich Leonard
有效抗性的图形概念在许多纯数学，应用数学和控制理论的许多领域中发现了广泛的应用。根据其构造的性质，有效的阻力只能在无向图中计算出来，但在其应用的几个区域中，与无方向性的图形自然（或更自然）出现。在这项工作的第一部分中，我们提出了对有效图表的有效抗性的概括，该图形保留了其控制理论与共识型动力学有关的概括。我们开始分析代数定义对图的结构特性以及构造与图形距离之间的关系的依赖性。结果使得可以计算任何有向图中任意两个节点之间的有效电阻，并为对涉及有向图的问题的有效抗性提供了坚实的基础。
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.