From Signed Networks to Group Graphs

Abstract

I define a group graph which encodes the symmetry in a dynamical process on a network. Group graphs extend signed networks, where links are labelled with plus or minus one, by allowing link labels from any group and generalising the standard notion of balance. I show that for processes on a balanced group graph the time evolution is completely determined by the network topology, not by the group structure. This unifies and extends recent findings on signed networks (Tian and Lambiotte, 2024a) and complex networks (Tian and Lambiotte, 2024b). I will also relate the results discussed here to existing work such as the ``group labelling'' of Edelman and Saks (1979), the ``group graph'' of Harary, Lindström and Zetterström (1982), a ``voltage graph'' (Gross, 1974), a ``gain graph'' (Zaslavsky 1989), and ``group synchronisation'' (Karp et al, 2003). I will work with a more general case where edges need not be reciprocated and the labels of reciprocated edges need not be inverses of each other. Finally, I will review some promising applications for network dynamics and symmetry-driven modelling including status, clusterability, edges with a zero label, weak balance, unbalanced group graphs and using monoids.

55 pages including 16 in the appendices. Version 3 has has added references to group labelling, voltage graphs, gain graphs and group synchronisation