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

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

2 Citations (Scopus)
11 Downloads (Pure)

Abstract

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.
PublisherIEEE
Number of pages6
ISBN (Print)978-1-5090-1837-6
DOIs
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
http://cdc2016.ieeecss.org/

Conference

Conference2016 IEEE 55th Conference on Decision and Control
CountryUnited States
CityLas Vegas, NV
Period12/12/1614/12/16
Internet address

Fingerprint

Eigenvalues and eigenfunctions
Directed graphs
Computational complexity

Keywords

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

Cite this

Clark, Ruaridh ; Punzo, Giuliano ; Macdonald, Malcolm. / Consensus speed optimisation with finite leadership perturbation in k-nearest neighbour networks. 2016 IEEE 55th Conference on Decision and Control (CDC). Piscataway, N.J. : IEEE, 2016.
@inproceedings{ab1e53384e9e4b7e811ca8d74a8d43e1,
title = "Consensus speed optimisation with finite leadership perturbation in k-nearest neighbour networks",
abstract = "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.",
keywords = "laplace equations , convergence, network topology, computational complexity, matrix algebra, eigenvalues, eigenfunctions",
author = "Ruaridh Clark and Giuliano Punzo and Malcolm Macdonald",
note = "{\circledC} 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting /republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.",
year = "2016",
month = "12",
day = "29",
doi = "10.1109/CDC.2016.7798378",
language = "English",
isbn = "978-1-5090-1837-6",
booktitle = "2016 IEEE 55th Conference on Decision and Control (CDC)",
publisher = "IEEE",

}

Clark, R, Punzo, G & Macdonald, M 2016, Consensus speed optimisation with finite leadership perturbation in k-nearest neighbour networks. in 2016 IEEE 55th Conference on Decision and Control (CDC). IEEE, Piscataway, N.J., 2016 IEEE 55th Conference on Decision and Control, Las Vegas, NV, United States, 12/12/16. https://doi.org/10.1109/CDC.2016.7798378

Consensus speed optimisation with finite leadership perturbation in k-nearest neighbour networks. / Clark, Ruaridh; Punzo, Giuliano; Macdonald, Malcolm.

2016 IEEE 55th Conference on Decision and Control (CDC). Piscataway, N.J. : IEEE, 2016.

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

TY - GEN

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

AU - Clark, Ruaridh

AU - Punzo, Giuliano

AU - Macdonald, Malcolm

N1 - © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting /republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

PY - 2016/12/29

Y1 - 2016/12/29

N2 - 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.

AB - 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.

KW - laplace equations

KW - convergence

KW - network topology

KW - computational complexity

KW - matrix algebra

KW - eigenvalues

KW - eigenfunctions

UR - http://cdc2016.ieeecss.org/

U2 - 10.1109/CDC.2016.7798378

DO - 10.1109/CDC.2016.7798378

M3 - Conference contribution book

SN - 978-1-5090-1837-6

BT - 2016 IEEE 55th Conference on Decision and Control (CDC)

PB - IEEE

CY - Piscataway, N.J.

ER -