Source-linked AI summary
Distributed strategies for generating weight-balanced and doubly stochastic digraphs
Bahman Gharesifard, Jorge Cortes
TL;DR
The paper asks when directed graphs admit weight-balanced or doubly stochastic edge assignments, motivated by distributed algorithms that rely on these structures. It characterizes doubly stochasticability and develops distributed discrete-time strategies for constructing the required weights. The resulting algorithms achieve finite-time weight balancing, with the mirror method having O(n^4) time complexity and load-pushing supporting doubly stochasticability testing and weight construction.
Problem
The paper addresses when a digraph can receive a nonzero weight assignment that makes it weight-balanced or doubly stochastic, an issue relevant to distributed control, averaging, and optimization algorithms.
Method
The paper combines graph characterizations with discrete-time distributed algorithms, including imbalance-correcting, mirror imbalance-correcting, self-loop addition, and load-pushing strategies.
Results
The algorithms converge in finite time to weight-balanced adjacency matrices, while the mirror imbalance-correcting algorithm has time complexity O(n^4).
Takeaways & Limitations
The results enlarge the domain of systems for which distributed formation and optimization algorithms can be executed over appropriate directed interaction topologies.
Takeaways & Limitations
The time complexity of the imbalance-correcting algorithm remains an open problem, and doubly stochasticability with zero entries while preserving connectivity remains an open research question.
Abstract
from arXiv · showhide
Weight-balanced and doubly stochastic digraphs are two classes of digraphs that play an essential role in a variety of cooperative control problems, including formation control, distributed averaging, and 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 algorithms to compute the appropriate set of weights in each case.
1. Introduction.
The paper addresses the technical challenges of directed interaction topologies by characterizing weight-balanced and doubly stochastic digraphs and developing distributed strategies to construct suitable edge weights. Its contributions include finite-time weight balancing and methods for constructing or identifying doubly stochastic assignments.
- Directed interaction topologies pose greater technical challenges because interactions among agents are unidirectional.
- Weight-balanced digraphs equalize incoming and outgoing edge-weight sums, while doubly stochastic digraphs additionally make those sums equal to one.
- Distributed weight-assignment strategies are needed so agents can balance in- and out-degrees for algorithms using these interaction topologies.
- The paper characterizes doubly stochasticable digraphs and connects them to a special subset of weight-balanced digraphs.
- Two discrete-time set-valued systems converge to weight-balanced digraphs in finite time, including a mirror strategy with lower time complexity than an existing centralized cycle-based strategy.
- The paper constructs doubly stochastic adjacency matrices with self-loop addition or, without self-loops, uses load-pushing to identify doubly stochasticability and find suitable weights.
2. Mathematical preliminaries.
The preliminaries define weighted digraphs, connectivity, cycles, stochastic matrices, and set-valued dynamics used throughout the paper. They also establish cycle-based characterizations and constructions for weight-balanceability, including principal cycle sets and their associated positive integer weights.
- A weighted digraph assigns a nonnegative adjacency matrix whose positive entries correspond exactly to the graph's edges.
- Strong connectivity requires a directed path between every pair of distinct vertices, whereas strong semiconnectedness requires reciprocal path existence whenever one direction exists.
- A doubly stochastic matrix is both row-stochastic and column-stochastic, with each row and column summing to one.
- A union of disjoint cycles has a permutation-matrix adjacency representation exactly when it contains all vertices.
- A digraph is weight-balanceable exactly when its edges can be decomposed into weight-balanceable subsets, equivalently when every edge lies in a cycle or the digraph is strongly semiconnected.
- A principal cycle set is a minimum-cardinality collection of isolated vertices, cycles, or disjoint-cycle unions that generates the digraph.
- For a strongly semiconnected digraph, the union of a principal cycle set yields positive integer edge weights that make the digraph weight-balanced.
- Discrete-time set-valued dynamics are analyzed using fixed points, closed maps, invariant sets, bounded evolutions, and a LaSalle invariance principle.
3. When does a digraph admit a doubly stochastic weight assignment?.
The paper characterizes when strongly connected digraphs admit doubly stochastic adjacency assignments, relating this property to weight-balanced assignments and cycle structure. It also establishes construction results, including self-loop augmentation and assignments with zero entries under specific conditions.
- Relationship to weight-balanceability: Weight-balanceability alone is insufficient: Figure 3.1 depicts a weight-balanceable digraph whose only doubly stochastic solution requires α3 = 0.Because positive weights are required, the digraph is not doubly stochasticable.
- Necessary and sufficient conditions: A strongly semiconnected digraph is doubly stochasticable exactly when all of its strongly connected components are doubly stochasticable.This permits the characterization to focus on strongly connected digraphs.
- Relationship to weight-balanceability: For a strongly connected weight-balanced adjacency matrix, the transformation φ(A) is doubly stochastic exactly when all row sums equal a common positive constant C.The result provides a criterion for when a weight-balanced assignment can be converted into a doubly stochastic one.
- Construction results: Adding sufficiently many self-loops makes any strongly connected digraph doubly stochasticable.The construction adds appropriate self-loop weights to a weight-balanced matrix.
- Construction results: Any undirected regular graph is doubly stochasticable.Regular undirected graphs satisfy the characterization conditions directly.
- Necessary and sufficient conditions: Necessary and sufficient conditions characterize doubly stochasticability for strongly connected digraphs through collections of cycles that generate the graph.Propositions 3.6 and 3.7 are combined in Corollary 3.8 to give the full characterization.
- Construction results: A strongly connected digraph admits a strongly connected doubly stochastic weighting with possible zero entries if it contains a cycle through all vertices.Such assignments may reduce algebraic connectivity and thereby negatively affect convergence rates; the general characterization with zero entries remains open.
- Additional properties: If a real doubly stochastic assignment exists, a rational doubly stochastic assignment also exists.The result ensures that doubly stochasticability can be witnessed with rational weights.
4. Strategies for making a digraph weight-balanced.
The paper presents distributed algorithms that adjust edge weights so strongly connected digraphs become weight-balanced in finite time. It also introduces a mirror-digraph variant with a provable O(n^4) time complexity.
- Imbalance-correcting algorithm: Each agent computes its in-degree and updates at most one minimum-weight out-edge when its in-degree exceeds its out-degree.Agents communicate weight changes to out-neighbors and synchronously repeat the process.
- Convergence analysis: The imbalance-correcting algorithm is represented as a closed set-valued dynamical system whose fixed points are exactly the weight-balanced adjacency matrices.Its correctness analysis uses closedness, fixed-point characterization, token propagation, and a Lyapunov function that vanishes precisely at weight balance.
- Convergence analysis: For every strongly connected digraph, every evolution of the imbalance-correcting algorithm reaches a weight-balanced adjacency matrix in finite time.The proof relies on finite-time propagation of positive imbalance through minimum-weight out-edges and strict decreases of the Lyapunov function.
- Complexity: The algorithm’s time complexity remains an open problem, although one example converges to a weight-balanced digraph in 6 rounds.The six-round execution is illustrated for the digraph in Figure 3.2(a).
- Mirror imbalance-correcting algorithm: The mirror imbalance-correcting algorithm operates over the mirror digraph, avoids computing cycles, and converges in finite time to a weight-balanced adjacency matrix.Its evolutions obey a fair-decision rule, and its time complexity is O(n^4).
5. Strategies for making a digraph doubly stochastic.
The paper combines distributed weight-balancing with self-loop addition or load-pushing to construct doubly stochastic assignments. The load-pushing strategy is distributed over the mirror digraph, detects non-regularity, and terminates in O(|V|^2 × |E|) steps.
- 5.1. The imbalance-correcting algorithm with self-loop addition.: Any strongly connected communication network can be made doubly stochastic by imbalance correction, self-loop addition, and normalization.Agents balance weights, equalize out-degrees using appropriately weighted self-loops, then divide out-edge weights by the maximum out-degree.
- 5.1. The imbalance-correcting algorithm with self-loop addition.: The self-loop construction first executes imbalance correction, computes the maximum out-degree, adds self-loops when needed, and normalizes the resulting out-edge weights.The procedure yields equal out-degree sums before the final division step.
- 5.2. The load-pushing algorithm.: The mirror-digraph strategy lets nodes determine whether G is C-regular and, when it is, find weights that make it C-regular.Dividing all resulting entries by C produces a doubly stochastic weight assignment.
- 5.2. The load-pushing algorithm.: The load-pushing algorithm initializes source and target loads from out- and in-degrees, then routes loads through eligible edges using height comparisons.Its operations are push forward, increase target height, push backward, and push forward; nodes announce non-C-regularity when no eligible forward edge exists.
- 5.2. The load-pushing algorithm.: The algorithm finds a C-regular assignment exactly when the digraph is doubly stochasticable, under the stated C conditions.If G is doubly stochasticable and C ≥ ds(G), it converges to a C-regular digraph; if it announces failure with C ≥ |E| − |V| + 1, G is not doubly stochasticable.
- 5.2. The load-pushing algorithm.: The load-pushing execution corresponds to a distributed preflow-push algorithm for a maximum-flow problem with positive lower bounds.The resulting termination complexity is O(|V|^2 × |E|) steps.
6. Conclusions.
The paper characterizes weight-balanced and doubly stochastic digraphs and develops finite-time distributed strategies for constructing them. It also identifies remaining gaps involving ds(G), zero edge weights, and communication restricted to the original digraph.
- 6. Conclusions.: The paper gives a necessary and sufficient condition for doubly stochasticability and connects these digraphs to a special subset of weight-balanced digraphs.It also characterizes weight-balanced digraph properties.
- 6. Conclusions.: Two discrete-time algorithms construct weight-balanced digraphs from strongly connected digraphs with finite-time convergence.The imbalance-correcting algorithm runs synchronously, while the mirror imbalance-correcting algorithm operates over the mirror digraph and has substantially better time complexity than the existing centralized algorithm.
- 6. Conclusions.: The paper leaves the gap between ds(G) and p(G) for doubly stochasticable digraphs as future work.It also proposes studying cases allowing zero edge weights.
- 6. Conclusions.: A distributed dynamical system for computing doubly stochastic weights using only the original digraph, rather than its mirror, remains an open problem.The paper also seeks procedures for identifying a doubly stochasticable strongly connected spanning subdigraph.