Distributed Strategies for Generating Weight-Balanced and Doubly Stochastic Digraphs

This paper deals with the design and analysis of dynamical systems on directed graphs (digraphs) that achieve weight-balanced and doubly stochastic assignments. Weight-balanced and doubly stochastic digraphs are two classes of digraphs that play an essential role in a variety of coordination problems, including formation control, agreement, and distributed optimization. We refer to a digraph as doubly stochasticable (weight-balanceable) if it admits a doubly stochastic (weight-balanced) adjacency matrix. This paper studies the characterization of both classes of digraphs, and introduces distributed dynamical systems to compute the appropriate set of weights in each case. It is known that semiconnectedness is a necessary and sufficient condition for a digraph to be weight-balanceable. The first main contribution is a characterization of doubly-stochasticable digraphs. As a by-product, we unveil the connection of this class of digraphs with weight-balanceable digraphs. The second main contribution is the synthesis of a distributed strategy running synchronously on a directed communication network that allows individual agents to balance their in- and out-degrees. We show that a variation of our distributed procedure over the mirror graph has a much smaller time complexity than the currently available centralized algorithm based on the computation of the graph cycles. The final main contribution is the design of two cooperative strategies for finding a doubly stochastic weight assignment. One algorithm works under the assumption that individual agents are allowed to add self-loops. For the case when this assumption does not hold, we introduce an algorithm distributed over the mirror digraph which allows the agents to compute a doubly stochastic weight assignment if the digraph is doubly stochasticable and announce otherwise if it is not. Various examples illustrate the results.