Title :
Graph topology optimization for fast consensus based on the influence of new links to a quadratic criterion
Author :
Charalampidis, Alexandros C.
Author_Institution :
Nat. Tech. Univ. of Athens, Athens, Greece
Abstract :
This paper studies the problem of graph choice in order to maximize consensus convergence speed. Instead of algebraic connectivity, a quadratic criterion is used which is shown to depend on the whole spectrum of the consensus dynamics matrix. The influence of new links to this cost is investigated and a first-order approximation is given. This approximation can be used to compare the effect that different links will have and this is exploited to propose a simple algorithm that starts from a regular lattice and adds links until all nodes have a specific number of neighbours. The resulting graph is compared with random graphs known to have high connectivity because of the small-world effect. Numerical experimentation showed that, for specific parameters, this algorithm provides a graph outperforming a large number of realizations of random graphs both in terms of algebraic connectivity and of the proposed quadratic criterion; for these random graphs it was also shown that this quadratic criterion correlates better with the characteristic path length than algebraic connectivity does.
Keywords :
convergence; graph theory; matrix algebra; multi-agent systems; optimisation; algebraic connectivity; characteristic path length; consensus convergence speed; consensus dynamics matrix; first-order approximation; graph choice; graph topology optimization; multiagent systems; quadratic criterion; random graphs; regular lattice; Algorithm design and analysis; Approximation methods; Convergence; Eigenvalues and eigenfunctions; Lattices; Optimization; Topology;
Conference_Titel :
Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on
Conference_Location :
Los Angeles, CA
Print_ISBN :
978-1-4799-7746-8
DOI :
10.1109/CDC.2014.7039605