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

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.