Abstract. Since their introduction, Boolean networks have been traditionally studied in view of their rich dynamical behaviour under different update protocols and for their qualitative analogy with cell regulatory networks. More recently, tools borrowed from the statistical physics of disordered systems and from computer science have provided a more complete characterization of their equilibrium behaviour. However, the largest number of results have been obtained in the thermodynamic limit, which is often far from being reached when dealing with realistic instances of the problem. The numerical analysis presented here aims at comparing—for a specific family of models—the outcomes given by the heuristic belief propagation algorithm with those given by exhaustive enumeration. In the second part of the paper some analytical considerations on the validity of the annealed approximation are discussed.

Key words: message-passing algorithms; random graphs, networks

Received 31 October 2006, accepted for publication 27 November 2006
Published 18 December 2006