Distributed control and optimisation of complex networks via their Laplacian spectra
Louis Kempton · Bristol Research (University of Bristol) · 2018
I n complex networked systems, the structure of the underlying communication between individual agents can have profound impacts on the performance and dynamics of the system as a whole.For example, processes such as consensus can occur at faster or slower rates depending on the structure of the communication graph, and the synchronisation of coupled chaotic oscillators may be unachievable in one configuration, when it is achievable in another.As such, it is vital for agents within a complex networked system to be able to make estimates of the properties of the network as a whole, and be able to direct their own actions to modify these properties in a desirable way, even when they are only able to communicate with their direct neighbours, and have no global knowledge of the structure of the network.In this thesis we explore decentralised strategies by which individual agents in a network can make estimates of several functions of the graph Laplacian matrix eigenvalues, and control or optimise these functions in a desired manner, subject to constraints.We focus on the following spectral functions of the graph Laplacian matrix, which determine or bound many interesting properties of graphs and dynamics on networks: the algebraic connectivity (the smallest non-zero eigenvalue), the spectral radius (the largest eigenvalue), the ratio between these extremal eigenvalues (also known as the synchronisability ratio), the total effective graph resistance (proportional to the sum of the reciprocals of non-zero eigenvalues), and the reduced determinant (the product of the non-zero eigenvalues).i x LIST OF FIGURES 4.4 Increasing values of algebraic connectivity at the steady state as the severity of the logarithmic barriers is increased. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.5 Effect of changing the control parameter c 1 . . . . . . . . . . . . . . . . . . . . . . . . . .4.6 Edge weights changing in time using the adaptive logarithmic barrier algorithm. . .4.7 Increasing algebraic connectivity over time towards the optimal value. . . . . . . . . .4.8 The state of the weighted graph at t = 1000 (near optimal). . . . . . . . . . . . . . . . .4.9 Effect of changing the control parameter k b . . . . . . . . . . . . . . . . . . . . . . . . . .4.10 Effect of changing the control parameter c 2 . . . . . . . . . . . . . . . . . . . . . . . . . .4.11 Maximisation of the algebraic connectivity in an entirely distributed manner on a network of 20 nodes. . . . . . . . . . . . . . . . . . .