Quasi-symmetries in complex networks: a dynamical model approach

Abstract

The existence of symmetries in complex networks has a significant effect on network dynamic behaviour. Nevertheless, beyond topological symmetry, one should consider the fact that real-world networks are exposed to fluctuations or errors, as well as mistaken insertions or removals. Therefore, the resulting approximate symmetries remain hidden to standard symmetry analysis¿fully accomplished by discrete algebra software. There have been a number of attempts to deal with approximate symmetries. In the present work we provide an alternative notion of these weaker symmetries, which we call 'quasi-symmetries'. Differently from other definitions, quasi-symmetries remain free to impose any invariance of a particular network property and they are obtained from the phase differences at the steady-state configuration of an oscillatory dynamical model: the Kuramoto-Sakaguchi model. The analysis of quasi-symmetries unveils otherwise hidden real-world networks attributes. On the one hand, we provide a benchmark to determine whether a network has a more complex pattern than that of a random network with regard to quasi-symmetries, namely, if it is structured into separate quasi-symmetric groups of nodes. On the other hand, we define the 'dual-network', a weighted network (and its corresponding binnarized counterpart) that effectively encodes all the information of quasi-symmetries in the original network. The latter is a powerful instrument for obtaining worthwhile insights about node centrality (obtaining the nodes that are unique from that act as imitators with respect to the others) and community detection (quasi-symmetric groups of nodes).