Boolean Networks with Reliable Dynamics

This was an experience. I've tried to understand a physics paper in order to compare research in physics and computer science. In general, I think physics is more well-defined and beautiful as a science than computer science. If you take theoretical physics as an example, they are much more aware of what are their "big questions" then us. They know how to describe these questions and their relevance in a more intuitive way. On the other hand, experimental physics has more statistical rigor than experimental computer science (e.g., the 5-sigma). Moreover, they are much better at defining a theoretical framework to study their problems. As a consequence, the progress of the research in physics is more clear than in computer science to me. Putting it in a few words, physics is a harder science than computer science.

After three days of reading, I decided to give up on this paper. It is not that I haven't understand anything, but I certainly did not understand everything. Actually, it is hardest paper I've read so far this year. In part, this is due to my unfamiliarity with the concepts involved, which are not very well described in the paper. Moreover, the authors usually go too deep and formally into small details that are not easy to follow.

The paper is authored by two researchers from the Technical University of Darmstadt, Germany. It studies several property of boolean networks (BNs) that have reliable trajectories. A boolean network has a boolean variable associated to each of its nodes. These variables are set according to input data from other nodes and boolean functions. A trajectory of a BN is a set of consecutive states of the network and it is said to be reliable if it does not depend on the order in which nodes are updated. BNs attract the interest of biologists, as a model for gene regulatory networks, and statistical physicists, as a complex system with several interesting properties. 

The state of a node is subject to a function as follows:

sigma_i(t+1) = f_i(sigma(t))u_i(t) + sigma_i(t)(1-u_i(t))

Where t is time, f_i is a function that can be represented as true table of the inputs of the vertex i, and u_i defines whether the state of i is updated at a given time t. States can be updated according to different schemes (synchronous, asynchronous and deterministic, asynchronous and stochastic).

An attractor is state or a set of states in which the network stabilizes (loop). An attractor of size one is called a fixed point. The authors enforce the reliability of the trajectory by guaranteeing that two consecutive states differ always by one value and that the state of only one node is changed at time. They generate random trajectories and then apply an algorithm that produces the simplest networks and functions that generate the given trajectory. This algorithm generates the update function of each node v independently, based on the states of the nodes that changed their state right before v. More nodes may be necessary as inputs to a given vertex (different combinations are tested). A trajectory is characterized by the number of nodes involved and the average number of flips per node (Poisson distribution). 

The first part of the results are about the topology of the networks generated. They show that the average degree of vertices is l (average number of flips/node) and it follows a Poisson distribution. The clustering coefficient of reliable networks is higher than the one of random (shuffled edges) networks. The number of loops in the network increases with l and decreases with N (number of nodes). In general, denser subgraphs have a higher z-score, and the abundance of these subgraphs increases with l.

Regarding the update functions, the authors show that there are classes of functions that present similar probability. The authors show how these classes are related to restrictions on the local trajectory of nodes (e.g., functions that are insensitive to one or more inputs can not be generated).  Moreover, homogeneous functions (i.e., functions with small number of minority outputs) are more likely. This property is proved  in the paper.

The final part of the results are about the state space structure. Using a stochastic update scheme, the authors evaluated the probability of attractors of different sizes. Small networks produce short attractors. Almost always the attractor has size one (fixed point) but in some cases the attractors are longer than the defined trajectories.

I think reading this paper was worthy. It remembered me of my high school times when I tried to read about relativity, particle physics and cosmology. Reading about complex subjects make other subjects look easier. Moreover, I got curious about other related systems such as Bayesian networks and cellular automata. Finally, I still believe computer science, as a young science, can learn a lot from physics.

Link: http://arxiv.org/abs/arXiv:0905.0925