Boolean Network
A Boolean network is a directed graph in which each node takes one of two states — typically 0 or 1, OFF or ON — and updates its state according to a Boolean function of its inputs. Boolean networks are the simplest class of discrete dynamical systems capable of exhibiting complex behavior, and they serve as foundational models in systems biology, computer science, and the theory of computation.
Structure and Dynamics
A Boolean network is defined by a graph and a set of Boolean functions. Each node has a state variable that takes values in {0, 1}. The network updates in discrete time steps, either synchronously (all nodes update simultaneously) or asynchronously (nodes update one at a time). The dynamics are deterministic: given the initial state and the Boolean functions, the entire future trajectory is fixed.
Because the state space is finite (2^N states for N nodes), every trajectory eventually enters a cycle. The set of states that flow into a cycle is its basin of attraction. The attractor structure — the number, length, and stability of cycles — is the primary object of study in Boolean network theory.
Relation to Other Models
Boolean networks are generalizations of cellular automata. In a cellular automaton, all nodes use the same Boolean function and the graph is a regular lattice. In a Boolean network, nodes may use different functions and the graph may have arbitrary topology. This flexibility makes Boolean networks suitable for modeling gene regulatory networks, where different genes have different regulatory logic and the interaction topology is empirically determined rather than assumed.
Random Boolean networks are the most-studied subclass, where both the topology and the Boolean functions are chosen randomly. They exhibit a phase transition between ordered and chaotic dynamics as the average connectivity changes.
Applications
- Gene regulatory networks: Boolean networks model gene expression as binary on/off states, with regulatory interactions encoded as Boolean functions. See Gene Regulatory Network.
- Neural networks: Early models of neural computation used Boolean threshold functions.
- Social dynamics: Boolean networks model opinion formation, where each individual's opinion depends on the opinions of their social contacts.
- Ecosystems: Species presence/absence can be modeled as Boolean states with interactions representing competition, mutualism, or predation.