Large-Scale Structure of Multi-Optimised Networks

  • Sebastian Morel-Balbi

Student thesis: Doctoral ThesisPhD

Abstract

Generative network models (i.e. models that aim to uncover the underlying mechanisms that drive network formation) have played a prominent role in the literature of networked systems, and many hypotheses on how networks grow and evolve have been proposed. Recently, structural optimisation has been suggested as one of the main drivers underlying network formation processes. Indeed, many networks are designed or required to perform one or more specific tasks as efficiently as possible. How optimally a network will perform a set of pre-specified tasks will depend, at least partially, on its large-scale structure. Consequently, these optimality requirements should result in selective pressures driving the network toward particular large-scale topologies. The general prescription behind this family of models is to define a cost function over a network ensemble; by minimising the cost function, one can evaluate whether particular topologies characterise the ensemble and compare these topologies with those observed in real-world networks. However, real-world networks rarely emerge as the result of a single generating mechanism but are more likely to be the end product of several co-existing processes and limitations, such as dynamical rules, exogenous constraints, and optimality requirements. This conflation of generating processes makes it difficult to assess and quantify to what extent optimality might have played a role in the formation of any given network. In this thesis, we develop a framework to construct null models of optimised networks that allow us to isolate the effects of optimisation on network structure from other external artefacts. Furthermore, our framework can accommodate an arbitrary number of optimisation criteria, allowing us to study more realistic scenarios in which a network is simultaneously subject to multiple selective pressures. We apply the proposed framework to study networks driven to optimise for modularity and robustness against random failures. We first analyse the case in which the criteria are imposed separately and uncover the topologies most likely to emerge as a result of optimisation. We then combine the two criteria and study the effects of joint optimisation on the network structure. We uncover a rich phase diagram of optimised networks, characterised by a series of phase transitions at which the optimal topologies change according to the desired degree of optimality. We also identify regions of the parameter space where synergistic and antagonistic effects are present, such that optimising for one criterion can help or hinder optimising for the other.
Date of Award2 Nov 2022
Original languageEnglish
Awarding Institution
  • University of Bath
SupervisorTiago De Paula Peixoto (Supervisor) & Kit Yates (Supervisor)

Cite this

'