A Necessary and Sufficient Condition of an Interfering Reverse Edge for a Directed Acyclic Graph

• 成果类型: Article
• 署名作者: Zhang, Hai-Tao; Cao, Haosen; Chen, Zhiyong
• 署名单位: Huazhong University of Science & Technology; University of Newcastle
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3162548
• 发表日期: 2022
• 页码: 4885-4891
• 关键词: convergence; Network topology; Laplace equations; Eigenvalues and eigenfunctions; TOPOLOGY; biology; Synchronization; Agents and autonomous systems; Cooperative control; directed acyclic graphs (DAGs); network analysis and control

摘要

A directed acyclic graph (DAG) is a common topology in biological, engineering, and social networks. A network topology is critical in determining a collective behavior of a network dynamic system. For example, the convergence rate of a consensus behavior in a multiagent system relies on the eigenvalues of the Laplacian associated with the network topology. This article aims to analyze the influence of adding a reverse edge into a DAG on convergence rate. It reveals the existence of the so-called interfering reverse edges; adding one single edge in this category can reduce the so-called dominant convergence rate even for a large network. More specifically, a necessary and sufficient condition of an interfering reverse edge is explicitly constructed. According to the condition, a computationally efficient method is proposed to assess an interfering reverse edge.