IRUS Total

Node dynamics on graphs: dynamical heterogeneity in consensus, synchronisation and final value approximation for complex networks

File Description SizeFormat 
OClery-N-2013-PhD-Thesis.pdfThesis4.32 MBAdobe PDFView/Open
Title: Node dynamics on graphs: dynamical heterogeneity in consensus, synchronisation and final value approximation for complex networks
Authors: O'Clery, Neave
Item Type: Thesis or dissertation
Abstract: Here we consider a range of Laplacian-based dynamics on graphs such as dynamical invariance and coarse-graining, and node-specific properties such as convergence, observability and consensus-value prediction. Firstly, using the intrinsic relationship between the external equitable partition (EEP) and the spectral properties of the graph Laplacian, we characterise convergence and observability properties of consensus dynamics on networks. In particular, we establish the relationship between the original consensus dynamics and the associated consensus of the quotient graph under varied initial conditions. We show that the EEP with respect to a node can reveal nodes in the graph with increased rate of asymptotic convergence to the consensus value as characterised by the second smallest eigenvalue of the quotient Laplacian. Secondly, we extend this characterisation of the relationship between the EEP and Laplacian based dynamics to study the synchronisation of coupled oscillator dynamics on networks. We show that the existence of a non-trivial EEP describes partial synchronisation dynamics for nodes within cells of the partition. Considering linearised stability analysis, the existence of a nontrivial EEP with respect to an individual node can imply an increased rate of asymptotic convergence to the synchronisation manifold, or a decreased rate of de-synchronisation, analogous to the linear consensus case. We show that high degree 'hub' nodes in large complex networks such as Erdős-Rényi, scale free and entangled graphs are more likely to exhibit such dynamical heterogeneity under both linear consensus and non-linear coupled oscillator dynamics. Finally, we consider a separate but related problem concerning the ability of a node to compute the final value for discrete consensus dynamics given only a finite number of its own state values. We develop an algorithm to compute an approximation to the consensus value by individual nodes that is ϵ close to the true consensus value, and show that in most cases this is possible for substantially less steps than required for true convergence of the system dynamics. Again considering a variety of complex networks we show that, on average, high degree nodes, and nodes belonging to graphs with fast asymptotic convergence, approximate the consensus value employing fewer steps.
Content Version: Open Access
Issue Date: Jul-2013
Date Awarded: Oct-2013
URI: http://hdl.handle.net/10044/1/40130
DOI: https://doi.org/10.25560/40130
Supervisor: Barahona, Mauricio
Stan, Guy-Bart
Sponsor/Funder: Wellcome Trust (London, England)
Department: Mathematics
Publisher: Imperial College London
Qualification Level: Doctoral
Qualification Name: Doctor of Philosophy (PhD)
Appears in Collections:Mathematics PhD theses

Unless otherwise indicated, items in Spiral are protected by copyright and are licensed under a Creative Commons Attribution NonCommercial NoDerivatives License.

Creative Commons