Distributed strategies for balancing a weighted digraph

A weighted digraph is balanced if, for each node, the sum of the weights of the edges outgoing from that node is equal to the sum of the weights of the edges incoming to that node. Weight-balanced digraphs play a key role in a number of applications, including cooperative control, distributed optimization, and distributed averaging problems. We address the weight-balance problem for a distributed system whose components (nodes) can exchange information via interconnection links (edges) that form an arbitrary, possibly directed, communication topology (digraph). We develop two iterative algorithms, a centralized one and a distributed one, both of which can be used to reach weight-balance, as long as the underlying communication topology forms a strongly connected digraph (or is a collection of strongly connected digraphs). The centralized algorithm is shown to reach weight-balance after a finite number of iterations (bounded by the number of nodes in the graph). The distributed algorithm operates by having each node adapt the weights on its outgoing edges and is shown to asymptotically lead to weight-balance. We also analyze the rate of convergence of the proposed distributed algorithm and obtain a (graph-dependent) worst-case bound for it. Finally, we provide examples to illustrate the operation, performance, and potential advantages of the proposed algorithms.