Most literature on measuring the symmetry of networks uses graph automorphism algorithms to find the automorphism group, and defines either the number of elements in the automorphism group or the number of nodes involved in the automorphism group as a measure of the level of symmetry of networks. However, this type of measure has two problems: first, it is a measure for exact symmetry, meaning that it fails to capture a large group of approximate symmetries of networks (for example, a lattice with one missing edge still has a high level of symmetry, intuitively speaking, but according to the present symmetry measure it may have zero symmetry); second, in real-world networks, most of the automorphism transformations found are composed of local permutations, for example two degree-one nodes attached to the same node are symmetric to each other. Therefore if a network has many automorphism transformations it could mean that the network has a lot of local symmetries, instead of global symmetries. For example, a lattice has translational and reflectional symmetries, both of which are global. To overcome these problems, we introduce a new measure of the level of symmetry of a given network. Our method is able to capture approximate symmetries of any given network, and we find that the distance between the best approximate symmetry and an exact symmetry is a good measure for the level of symmetry of the network.
