Core percolation and onset of complexity in Boolean networks

Abstract

The determination and classification of fixed points of large Boolean networks is addressed in terms of constraint satisfaction problem. We develop a general simplification scheme that, removing all those variables and functions belonging to trivial logical cascades, returns the computational core of the network. The onset of an easy-to-complex regulatory phase is introduced as a function of the parameters of the model, identifying both theoretically and algorithmically the relevant regulatory variables.

major revisions, extended results, version accepted for publication in PRL