Understanding the controllability of complex networks from the microcosmic to the macrocosmic

Abstract

From a microcosmic perspective, nodes as meta-structures (or ‘smallest units’) for the constitution of a graph are of great importance for understanding complex network-based systems. In this paper, we develop a new framework, which first of all defines the meta-structures of a graph in different levels and tries to depict a graph from a low to a high level of abstraction. Further, based on this framework we study the meta-structure-driven control model and try to understand the controllability of complex networks from a microcosmic to a macrocosmic perspective. Finally, we analyze the impact of the community strength of networks on meta-structure-driven control. The results for artificial networks and real-world networks indicate that for meta-structure-driven control, the number of driver nodes is dependent on the networks’ degree distribution, and the dependence weakens as the level of the meta-structures increases. In addition, the networks are easier to control as the community strength increases, while this monotonicity is not preserved as the level of the meta-structures increases. We also find that it is harder to control sparse and inhomogeneous networks as the level of the meta-structures increases.

Keywords

• meta-structures
• meta-structure-driven control
• minimum dominating set