Dimension-reduction of dynamics on real-world networks with symmetry

We derive explicit formulae to quantify the Markov chain state-space compression, or lumping, that can be achieved in a broad range of dynamical processes on real-world networks, including models of epidemics and voting behaviour, by exploiting redundancies due to symmetries. These formulae are applied in a large-scale study of such symmetry-induced lumping in real-world networks, from which we identify specific networks for which lumping enables exact analysis that could not have been done on the full state-space. For most networks, lumping gives a state-space compression ratio of up to 107, but the largest compression ratio identified is nearly 1012. Many of the highest compression ratios occur in animal social networks. We also present examples of types of symmetry found in real-world networks that have not been previously reported.

Automated summary

The study derived explicit formulas to quantify the Markov chain state-space compression achieved in real-world networks by exploiting redundancies due to symmetries. It found that for most networks, lumping can lead to a state-space compression ratio of up to 107, with the largest compression ratio identified being nearly 1012, many of which are found in animal social networks. The study also presented examples of symmetry types in real-world networks that had not been previously reported.