Consensus speed optimisation with finite leadership perturbation in k-nearest neighbour networks

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

3 Citations (Scopus)
19 Downloads (Pure)


Near-optimal convergence speeds are found for perturbed networked systems, with N interacting agents that conform to k-nearest neighbour (k-NNR) connection rules, by allocating a finite leadership resource amongst selected nodes. These nodes continue averaging their state with that of their neighbours while being provided with the resources to drive the network to a new state. Such systems are represented by a directed graph Laplacian with two newly presented semi-analytical approaches used to maximise the consensus speed. The two methods developed typically produce near-optimal results and are highly efficient when compared with conventional numerical optimisation, where the asymptotic computational complexity is O(n3) and O(n4) respectively. The upper limit for the convergence speed of a perturbed k-NNR network is identified as the largest element of the first left eigenvector (FLE) of a graph's adjacency matrix. The first semi-analytical method exploits this knowledge by distributing leadership resources amongst the most prominent nodes highlighted by this FLE. The second method relies on the FLEs of manipulated versions of the adjacency matrix to expose different communities of influential nodes. These are shown to correspond with the communities found by the Leicht-Newman detection algorithm, with this method enabling optimal leadership selection even in low outdegree (<; 12 connections) graphs, where the first semi-analytical method is less effective.
Original languageEnglish
Title of host publication2016 IEEE 55th Conference on Decision and Control (CDC)
Place of PublicationPiscataway, N.J.
Number of pages6
ISBN (Print)978-1-5090-1837-6
Publication statusPublished - 29 Dec 2016
Event2016 IEEE 55th Conference on Decision and Control - Las Vegas, NV, United States
Duration: 12 Dec 201614 Dec 2016
Conference number: 55th


Conference2016 IEEE 55th Conference on Decision and Control
Country/TerritoryUnited States
CityLas Vegas, NV
Internet address


  • laplace equations
  • convergence
  • network topology
  • computational complexity
  • matrix algebra
  • eigenvalues
  • eigenfunctions


Dive into the research topics of 'Consensus speed optimisation with finite leadership perturbation in k-nearest neighbour networks'. Together they form a unique fingerprint.

Cite this