Fast Consensus over Almost Regular Directed Graphs

2025/07/17 by Susie Lu, Lu, Susie, Marco Gamarra +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #DNA and Biological Computing #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2507.12726

openalex publication_date 2025/07/17 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28

Abstract

This paper studies an open consensus network design problem: identifying the optimal simple directed graphs, given a fixed number of vertices and arcs, that maximize the second smallest real part of all Laplacian eigenvalues, referred to as algebraic connectivity. For sparse and dense graphs, the class of all optimal directed graphs that maximize algebraic connectivity is theoretically identified, leading to the fastest consensus. For general graphs, a computationally efficient sequence of almost regular directed graphs is proposed to achieve fast consensus, with algebraic connectivity close to the optimal value.

Citations

• Fast Consensus Topology Design via Minimizing Laplacian Energy
• Consensus and Cooperation in Networked Multi-Agent Systems
• On the spectra of nonsymmetric Laplacian matrices
• Consensus Problems in Networks of Agents With Switching Topology and Time-Delays

Related

• Fast Consensus Topology Design via Minimizing Laplacian Energy
• Graph diameter, eigenvalues, and minimum-time consensus
• Optimization of convergence rate via algebraic connectivity
• Graph-theoretic optimization for edge consensus
• Speeding up finite-time consensus via minimal polynomial of a weighted graph - a numerical approach