# Boolean network

Boolean network

A Boolean network consists of a set of Boolean variables whose state is determined by other variables in the network. They are a particular case of discrete dynamical networks, where time and states are discrete, i.e. they have a bijection onto an integer series. Boolean and elementary cellular automata are particular cases of Boolean networks, where the state of a variable is determined by its spatial neighbors.

Classical model

The first Boolean networks were proposed by Stuart A. Kauffman in 1969, as random models of genetic regulatory networks (Kauffman 1969, 1993).

A Random Boolean network (RBN) is a system of "N" binary-state nodes (representing genes) with "K" inputs to each node representing regulatory mechanisms. The two states (on/off) represent respectively, the status of a gene being active or inactive. The variable "K" is typically held constant, but it can also be varied across all genes, making it a set of integers instead of a single integer. In the simplest case each gene is assigned, at random, K regulatory inputs from among the N genes, and one of the possible Boolean functions of K inputs. This gives a random sample of the possible ensembles of "NK" networks. The state of a network at any point in time is given by the current states of all "N" genes. Thus the state space of any such network is 2"N".

Simulation of RBNs is done in discrete time steps. The state of a node at time "t+1" is a function of the state of its input nodes and the boolean function associated with it. The behavior of specific RBNs and generalized classes of them has been the subject of much of Kauffman's (and others) research.

Such models are also known as "NK" models, or Kauffman networks.

Attractors

A Boolean network has 2"N" possible states. Sooner or later it will reach a previously visited state, and thus, since the dynamics are deterministic, fall into an attractor.

Dynamics

Order, chaos, and the edge

Topologies

*homogeneous
*normal
*scale-free (Aldana, 2003)

Updating Schemes

*synchronous
*asynchronous (Harvey and Bossomaier, 1997)
*semi-synchronous (Gershenson, 2002)
*deterministic asynchronous
*deterministic semi-synchronous

Applications

* genetic regulatory networks

References

* Aldana, M. (2003). * [http://www.fis.unam.mx/~max/physicad.pdf Boolean dynamics of networks with scale-free topology] . "Physica D" 185:45–66
* Aldana , M., Coppersmith, S., and Kadanoff, L. P. (2003). Boolean dynamics with random couplings. In Kaplan, E., Marsden, J. E., and Sreenivasan, K. R., editors, "Perspectives and Problems in Nonlinear Science. A Celebratory Volume in Honor of Lawrence Sirovich". Springer Applied Mathematical Sciences Series.
* Kauffman, S. A. (1969). Metabolic stability and epigenesis in randomly constructed genetic nets. "Journal of Theoretical Biology", 22:437-467.
* Kauffman, S. A. (1993). "Origins of Order: Self-Organization and Selection in Evolution". Oxford University Press. Technical monograph. ISBN 0-19-507951-5
* Gershenson, C. (2002). * [http://alife.org/alife8/proceedings/sub67.pdf Classification of random Boolean networks] . In Standish, R. K., Bedau, M. A., and Abbass, H. A., editors, "Artificial Life VIII:Proceedings of the Eight International Conference on Artificial Life", pages 1-8. MIT Press.
* Harvey, I. and Bossomaier, T. (1997). Time out of joint: Attractors in asynchronous random Boolean networks. In Husbands, P. and Harvey, I., editors, "Proceedings of the Fourth European Conference on Artificial Life (ECAL97)", pages 67-75. MIT Press.
* Wuensche, A. (1998). * [http://www.complexity.org.au/ci/vol06/wuensche/wuensche.html Discrete dynamical networks and their attractor basins] . In Standish, R., Henry, B., Watt, S., Marks, R., Stocker, R., Green, D., Keen, S., and Bossomaier, T., editors, "Complex Systems'98", University of New South Wales, Sydney, Australia.

* [http://www.ddlab.com/ DDLab]
* [http://homepages.vub.ac.be/~cgershen/rbn/tut/index.html Introduction to Random Boolean Networks]

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Boolean — (after George Boole), as a noun or an adjective, may refer to: * Boolean algebra (logic), a logical calculus of truth values or set membership * Boolean algebra (structure), a set with operations resembling logical ones * Boolean datatype, a… …   Wikipedia

• Network analysis (electrical circuits) — Linear Network Analysis Elements …   Wikipedia

• Boolean satisfiability problem — For the concept in mathematical logic, see Satisfiability. 3SAT redirects here. For the Central European television network, see 3sat. In computer science, satisfiability (often written in all capitals or abbreviated SAT) is the problem of… …   Wikipedia

• Gene regulatory network — A gene regulatory network (also called a GRN or genetic regulatory network ) is a collection of DNA segments in a cell which interact with each other (indirectly through their RNA and protein expression products) and with other substances in the… …   Wikipedia

• Cellular neural network — Cellular neural networks (CNN) are a parallel computing paradigm similar to neural networks, with the difference that communication is allowed between neighbouring units only. Typical applications include image processing, analyzing 3D surfaces,… …   Wikipedia

• Bayesian network — A Bayesian network, Bayes network, belief network or directed acyclic graphical model is a probabilistic graphical model that represents a set of random variables and their conditional dependencies via a directed acyclic graph (DAG). For example …   Wikipedia

• EDonkey network — The eDonkey network (also known as the eDonkey2000 network or eD2k) is a decentralized, mostly server based, peer to peer file sharing network best suited to share big files among users, and to provide long term availability of said files. In… …   Wikipedia

• Anonymous veto network — In cryptography, the Anonymous Veto Network (or AV net) is a multi party secure computation protocol to compute the boolean OR function [F. Hao, P. Zieliński. [http://www.cl.cam.ac.uk/ fh240/pdf/avnet.pdf A 2 round anonymous veto protocol] .… …   Wikipedia

• Sequential dynamical system — Sequential dynamical systems (SDSs) are a class of discrete dynamical systems which generalize many aspects of systems such as cellular automata, and provide a framework for studying dynamical processes over graphs. SDSs are used in the analysis… …   Wikipedia

• Logic synthesis — is a process by which an abstract form of desired circuit behavior (typically register transfer level (RTL) or behavioral) is turned into a design implementation in terms of logic gates. Common examples of this process include synthesis of HDLs,… …   Wikipedia