Exploiting symmetry in complex network analysis
Virtually all network analyses involve structural measures or metrics between pairs of vertices, or of the vertices themselves. The large amount of redundancy present in real-world complex networks is inherited by such measures, and this has practical consequences which have not yet been explored in full generality, nor systematically exploited by network practitioners. Here we present a complete theory for the study of symmetry in empirical networks and their effects on arbitrary network measures, and show how this can be exploited in practice in a number of ways, from redundancy compression, to computational reduction. We also uncover the spectral signatures of symmetry for an arbitrary network measure such as the graph Laplacian. Computing and decomposing network symmetries is very efficient in practice, and we test real-world examples up to several million nodes. We illustrate our methods with some popular network measures. Our results are widely applicable, and place previous work on network symmetry in a common framework.