Improving the efficiency of attractor cycle identification in Boolean networks

Boolean network models provide a computationally efficient way of studying dynamical processes on networks and are most frequently used to study the dynamical properties of genetic regulatory networks. Presented here is a new and more efficient method for finding every attractor cycle (stable state) in a Boolean network. The critical part of this new method can be executed in polynomial time (O(v3))(O(v3)), as opposed to the exponential time taken for the standard exhaustive search (O(v2v))(O(v2v)).The efficiency of this new method is dependent on the topology of the underlying network. In particular, efficiency significantly improves when the out-degree distribution is skewed, such as with a power law distribution. The findings also provide added insight into the dynamics on power law networks and make the method more applicable to biological networks, which are believed to have this property.This method can also be extended to some non-Boolean discrete models (e.g. cellular automata).