Computing Approximate Global Symmetry of Complex Networks with Application to Brain Lateral Symmetry

Abstract The symmetry of complex networks is a global property that has recently gained attention since MacArthur et al. 2008 showed that many real-world networks contain a considerable number of symmetries. These authors work with a very strict symmetry definition based on the network’s automorphism detecting mostly local symmetries in complex networks. The potential problem with this approach is that even a slight change in the graph’s structure can remove or create some symmetry. Recently, Liu (2020) proposed to use an approximate automorphism instead of strict automorphism. This method can discover symmetries in the network while accepting some minor imperfections in their structure. The proposed numerical method, however, exhibits some performance problems and has some limitations while it assumes the absence of fixed points and thus concentrates only on global symmetries. In this work, we exploit alternative approaches recently developed for treating the Graph Matching Problem and propose a method, which we will refer to as Quadratic Symmetry Approximator (QSA), to address the aforementioned shortcomings. To test our method, we propose a set of random graph models suitable for assessing a wide family of approximate symmetry algorithms. Although our modified method can potentially be applied to all types of symmetries, in the current work we perform optimization and testing oriented towards more global symmetries motivated by testing on the human brain.