Graph automorphic approaches to the robustness of complex networks

© 2020 Elsevier Ltd Leveraging on graph automorphic properties of complex networks (CNs), this study investigates three robustness aspects of CNs including the robustness of controllability, disturbance decoupling, and fault tolerance against failure in a network element. All these aspects are investigated using a quantified notion of graph symmetry, namely the automorphism group, which has been found implications for the network controllability during the last few years. The typical size of automorphism group is very big. The study raises a computational issue related to determining the whole set of automorphism group and proposes an alternative approach which can attain the emergent symmetry characteristics from the significantly smaller groups called generators of automorphisms. Novel necessary conditions for network robust controllability following a failure in a network element are attributed to the properties of the underlying graph symmetry. Using a symmetry related concept called determining set and a geometric control property called controlled invariant, the new necessary and sufficient conditions for disturbance decoupling are proposed. In addition, the critical nodes/edges of the network are identified by determining their role in automorphism groups. We verify that nodes with more repetition in symmetry groups of the network are more critical in characterizing the network robustness. Further, the impact of elimination of critical network elements on its robustness is analyzed by calculating a new improved index of symmetry which considers the orbital impacts of automorphisms. The importance of all symmetry inspired findings of this paper is highlighted via simulation on various networks.