Approximate symmetries in complex networks: theory, validation and applications
The structure of complex networks and the collective dynamics that run on top of them is often described using adjacency matrix-based metrics, which usually only reflect a narrow part of the actual structure of a graph. Graph symmetries, on the contrary, reflect on a property that is not tied up to a particular graph labelling. However, it restrictive definition --in terms of a graph's automorphism group-- make this quantity less expressive in empirical networks.
In this Master's Thesis we present a new mathematical framework to characterize approximate symmetries in complex networks. Departing from the (rigid) notion of strict graph symmetries, we propose a new theory which relaxes the condition under which a label permutation is admitted as a graph automorphism. We explore, with theory and computational analysis, how this more flexible notion allows us to capture the nuanced emergence of approximate symmetries, both in synthetic and in empirical networks. Our results show that our metric is able to unveil a rich approximate symmetry structure in networks that, a priori, were just classified as purely asymmetric. In addition, we explore the impact that such approximate symmetries have in dynamics running on top of the network, revealing a crucial role in a phenomenon called cluster synchronization.
Thesis advisor: Lucas Lacasa
Jury:
- Victor M. Eguíluz
- Juan Fernández-Gracia
- Lucas Lacasa
Detalles de contacto:
Lucas Lacasa Contact form