Symmetries are a convenient way to describe redundancies in data. This article presents two novel classes of graphs which can be represented in a compressed format using symmetries. We denote the first class as symmetry-compressible graphs where global automorphisms are used to create the representation. Since automorphisms are scarce in real graphs, we extend this notion by defining near symmetry-compressible graphs, which contain a much larger class of graphs, including many graphs arising in practice. In order to demonstrate the practical potential of the presented classes, we design two compression algorithms and evaluate them on a set of realistic networks.
展开▼
