The characterization of the structure of complex networks and the collective dynamics that run on top of them is often made with respect to metrics retrieved from the adjacency matrix which, somehow, 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 labelling –i.e. of a particular adjacency matrix–. However, the rather restrictive definition of graph symmetries –in terms of a graph’s automorphism group– make this important quantity less expressive in empirical networks: most of the real-world complex networks lack exact symmetries. In this Master’s Thesis we present a new mathematical framework to characterize approximate symmetries in complex networks. Starting
from the fact that the traditional notion of symmetry is too rigid for being applied to empirical networks, 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 ap-
proximate 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. All in all, our thesis contributes to the understanding of the relation between structure and dynam-
ics in complex networks when the characterization of a graph goes beyond a purely matrix-based description.