Tang paper

The point of this paper was to characterize a model for structural and dynamic properties of networks based on functional constraints. Evidently most previous research has looked at structural constraints on models instead, so this sort of approached the problem of signaling networks from a different perspective. So, the first thing they did was develop an algorithm for sampling from a maximum entropy probability distribution of functionally constrained networks (a 'functional ensemble,' for short). The point of using a maximum entropy distribution, as I understand it, is just to minimize the amount of information built into the system: i.e., not making any unnecessary assumptions about the nature of the network. So the idea is that they want to use these functional ensembles to test whether or not some dynamic/structural property of a network can be adequately explained by its function, or whether there is some additional selection at work.

Since everybody loves linear algebra so much, the authors decided that the most efficient way to store information about the state of the network is to encode each node as a boolean-value coefficient for a state vector. They're defining these as column vectors, so this looks like:

S(t) = [s1(t) s2(t) ... sN(t)]^T

Where T just means transpose (not an exponent) and the sj(t)'s are elements of {0, 1}. Then they define a connectivity matrix that describes how the nodes interact with one another, so its components are elements of the set {-1, 0} along the diagonal and {-1, 0, 1} elsewhere. So for a given initial state vector, you have a progression through a trajectory of state vectors, each transformed into the next by the same connectivity matrix. That is:

C*S(0) = S(1),
C*S(1) = S(2),

etc. So the general recursion formula would be C*S(t) = S(t+1). Also, since each row only affects its corresponding component of the new state vector for each transition (row 1 only affect component 1, for example), each row of C can be checked to satisfy the constraints imposed by the state vector trajectory independently of the other rows. This is important, because it makes iterating through all of the incoming arrow combinations for each node computationally feasible. Their sampling procedure for this model is simply: let alpha be an index for the rows of C between 1 and Z (where Z is the number of allowed incoming arrow combinations that satisfy the trajectory constraints). Pick alpha randomly, but use the same alpha for every node: this gives you a C that satisfies all required trajectory constraints.