Quasifibrations of graphs to find symmetries and reconstruct biological networks

A fibration of graphs is a homomorphism that is a local isomorphism of in-neighborhoods. Recently, it has been shown that graph fibrations are useful tools to uncover symmetries and cluster synchronization in biological networks ranging from gene, protein, and metabolic networks to the brain. However, the inherent incompleteness and disordered nature of biological data preclude the application of the definition of fibration as it is. As a consequence, also the currently known algorithms to identify fibrations fail in these domains. In this paper, we introduce and develop systematically the theory of quasifibrations which attempts to capture more realistic patterns of quasi-symmetry in such networks. We provide an algorithmic solution to the problem of finding quasifibrations in networks where the existence of missing links and variability across samples preclude the identification of perfect fibration symmetries. We test our algorithm against other strategies to repair missing links in incomplete networks using real connectome data and synthetic networks. Quasifibrations can be applied to reconstruct any incomplete network structure characterized by underlying symmetrical and almost symmetrical clusters. The most direct application of our algorithms is that of helping researchers to find hidden symmetries in unknown (or partially unknown) networks, especially (but not exclusively) of biological nature.

Automated summary

Graph fibrations are useful tools to uncover symmetries and cluster synchronization in biological networks, but the incompleteness and disordered nature of biological data make it challenging to apply the traditional definition and algorithms. This paper introduces the theory of quasifibrations to capture quasi-symmetry in such networks and provides an algorithmic solution for finding quasifibrations in networks with missing links and variability across samples. The algorithm is tested using real connectome data and synthetic networks, and it can help researchers find hidden symmetries in unknown or partially known networks, particularly in biological networks.