Single-Chord Augmentation of Weighted Cycles for Algebraic Connectivity and Network Coherence
For multi-agent systems with ring topologies (e.g., UAV formations), this work provides a principled, efficient method to select a single chord that nearly optimally balances convergence speed and noise resilience.
This paper studies adding a single weighted chord to a weighted cycle graph to improve both algebraic connectivity (convergence rate) and network coherence (steady-state disagreement). It derives exact formulas for effective resistance and Kirchhoff index, proves near-optimality of near-antipodal resistance-balanced chords, and proposes screening rules (RBAPS, AW-RBAPS) that achieve a mean hypervolume ratio of 0.9987 while evaluating only about 10.1% of admissible chords.
Ring-like communication graphs appear in UAV formations, cyclic patrols, perimeter monitoring, and other multi-agent tasks in which agents exchange information mainly with neighboring vehicles along a closed route. When measurement and actuation noise are persistent, a useful augmentation should improve both the convergence rate of consensus and the steady-state disagreement level. This paper studies the addition of a single weighted chord to a connected weighted cycle. The central observation is that a chord is not just a generic rank-one edge update: it splits the cycle into two complementary resistance arcs, and this resistance split governs both the algebraic-connectivity gain and the Kirchhoff-index reduction. We first derive exact chord-induced effective-resistance and Kirchhoff-index update formulas, giving a closed-form coherence objective. We then prove that, under bounded conductances and small resistance discrepancy, near-antipodal resistance-balanced chords are near-optimal for algebraic-connectivity improvement; an i.i.d. bounded-conductance model yields the same conclusion with high probability. Finally, because the best convergence-rate chord and the best coherence chord need not coincide, we formulate the design as a finite Pareto problem and introduce RBAPS and AW-RBAPS, two resistance-balanced screening rules that retain only linear or near-linear candidate sets. Numerical experiments show that AW-RBAPS remains effective beyond the formal moderate-heterogeneity regime and approximates the exhaustive Pareto front with mean hypervolume ratio $0.9987$ while evaluating about $10.1\%$ of admissible chords.