Single-Chord Augmentation of Weighted Cycles for Algebraic Connectivity and Network Coherence

Abstract

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.