Effect of Adding Edges to Consensus Networks With Directed Acyclic Graphs

Consensus of a network with a directed acyclic graph, a directed graph with no directed cycles, is always guaranteed if it contains a spanning tree. This paper studies the effect of adding edges to a directed acyclic graph that may result in a directed cycle. It is shown that the effect on consensus performance of the whole network is only determined by a local subnetwork containing all the added edges. More specifically, both a one-dimensional (1-D) chain network and a 2-D grid network are investigated in this paper. It is proved that, when a reverse edge is added, the consensus performance is degraded by the amount only determined by the edge range, that is, independent of the network size or the location of the added edge.