Dominant vertices and attractors' landscape for Boolean networks
Abstract
In previous works, we introduced the notion of dominant vertices. This is a set of nodes in the underlying network whose evolution determines the whole network's dynamics after a transient time. In this paper, we focus on the case of Boolean networks. We define a reduced graph on the dominant vertices and an induced automata network on this graph, which we prove is asymptotically equivalent to the original Boolean dynamics. Asymptotic conjugacy ensures that the systems, restricted to their respective attractors, are dynamically equivalent. For a significant class of networks, the induced automata network is indeed a reduction of the original system. In these cases, the reduction, which is obtained from the structure of dominant vertices, supplies a more tractable system with the same structure of attractors as the original one. Furthermore, the structure of the induced system allows us to establish bounds on the number and period of the attractors, as well as on the reduction of the basin's sizes and transient lengths. We illustrate this reduction by considering a class of networks, which we call clover networks, whose dominant set is a singleton. To get insight into the structure of the basins of attraction of Boolean networks with a single dominant vertex, we complement this work with a numerical exploration of the behavior of a parametrized ensemble of systems of this kind.