PHYSICAL REVIEW E 87, 022814 (2013)

State concentration exponent as a measure of quickness in Kauffman-type networks
Shun-ichi Amari,1 Hiroyasu Ando,1 Taro Toyoizumi,1 and Naoki Masuda2,3
2

1
RIKEN Brain Science Institute, Hirosawa 2-1, Wako, Saitama 351-0198, Japan
Department of Mathematical Informatics, The University of Tokyo, 7-3-1 Hongo, Bunkyo, Tokyo 113-8656, Japan
3
PRESTO, Japan Science and Technology Agency, 4-1-8 Honcho, Kawaguchi, Saitama 332-0012, Japan(Received 29 February 2012; revised manuscript received 24 October 2012; published 21 February 2013)

We study the dynamics of randomly connected networks composed of binary Boolean elements and thosecomposed of binary majority vote elements. We elucidate their differences in both sparsely and densely connectedcases. The quickness of large network dynamics is usually quantified by the length of transient paths, ananalytically intractable measure. For discrete-time dynamics of networks of binary elements, we address thisdilemma with an alternative unified framework by using a concept termed state concentration, defined as the
exponent of the average number of t-step ancestors in state transition graphs. The state transition graph is definedby nodes corresponding to network states and directed links corresponding to transitions. Using this exponent, weinterrogate the dynamics of random Boolean and majority vote networks. We find that extremely sparse Boolean
networks and majority vote networks with arbitrary density achieve quickness, owing in part to long-tailed
in-degree distributions. As a corollary, only relatively dense majority vote networks can achieve both quickness
and robustness.
DOI: 10.1103/PhysRevE.87.022814

PACS number(s): 89.75.Hc, 87.18.Sn, 05.45.−a

I. INTRODUCTION

Networks of binary elements are useful tools for investigating a plethora of dynamical behavior and information
processing in biological and social systems. For example,
various models of associative memory are used to study neural
information processing [1–3]. Random Boolean networks, also
known as Kauffman nets, show rich dynamics and are used tomodel gene regulation [4–7]. Random majority vote networks
are often used to understand mechanisms for ordering in neural
information processing [3,8–10], gene regulation [7], andcollective opinion formation in social systems [11]. We study
the dynamics of such networks by using a simple generativemodel of randomly connected Boolean and majority voteelements in the cases of sparse and dense connectivity.
Properties desirable for the dynamics of networks of suchbinary units include robustness and quickness. A system isdefined to be robust when the flipping of a small number ofunits’ states does not eventually alter the behavior of the entire
network. For random Boolean networks, the robustness has
been quantified in the context of damage spreading in cellular
automata [12–15].
Dynamics is usually called quick if an orbit starting froman arbitrary state reaches the corresponding attractor within asmall number of steps on average, i.e., with a short transient
length of the dynamics. However, even the average transient
length, which apparently seems to be the most basic quantity
to characterize the statistics of the transient length, may
be difficult to evaluate because the transient length of therandom Boolean networks seems analytically intractable andit obeys long-tailed distributions [16]. Therefore, in this paper,
we theoretically study the quickness of dynamics by use of

Published by the American Physical Society under the terms of theCreative Commons Attribution 3.0 License. Further distribution ofthis work must maintain attribution to the author(s) and the publishedarticle’s title, journal citation, and DOI.
1539-3755/2013/87(2)/022814(6)the concept of state concentration instead of examining thetransient length. To this end, we extend the previous statistical
dynamical framework [8–10]. In particular, the exponent ofconcentration, which we introduce later, is an analyticallytractable quantity for measuring the quickness of dynamics
in random Boolean and majority vote networks. Using thisexponent, we investigate the compatibility of the robustness
and quickness in these two types of networks in two cases ofconnectivity, i.e., sparse and dense connectivity.
For this purpose, we distinguish densely connected Boolean
networks (DBNs), sparsely connected Boolean networks(SBNs), densely connected majority vote networks (DMNs),
and sparsely connected majority vote networks (SMNs). We
elucidate the differences between the four dynamics. In particular, we show that strong state concentration, accompanied bya power law type of in-degree distribution with an exponential
cutoff, occurs in the majority vote networks (DMNs andSMNs) but not for the Boolean networks except for extremely
sparse cases. Then, we argue that DMNs are the only type
among the four types of network that realizes both robustness
and quickness.
II. MODELLet us consider a network of n binary units. We define thediscrete-time dynamics of the network by
xi (t + 1) = fi (x1 (t), . . . ,xn (t)) (1  i  n),(1)

where xi (t) ∈ {1, − 1} is the binary state of the ith unit at time
t. For a random Boolean network, each fi is randomly andnindependently chosen from the 22 Boolean functions on then units. For a majority vote network,⎛⎞n
fi (x1 , . . . ,xn ) = sgn ⎝wij xj ⎠ (1  i  n),
(2)
j =1

where sgn indicates the sign function. We consider an ensemble of randomly generated majority vote networks where wij

022814-1

Published by the American Physical SocietyAMARI, ANDO, TOYOIZUMI, AND MASUDAPHYSICAL REVIEW E 87, 022814 (2013)

are independently and identically distributed Gaussian randomvariables. In general, a constant or random threshold could be
included in the above dynamical expression, which we omit
here for simplicity. If the value of fi (x1 , . . . ,xn ) depends only
on randomly chosen K units for each i, the model is called
the K-sparse network [5,6]. DBNs and DMNs correspond toK ∝ n, and SBNs and SMNs correspond to K  n. We study
typical dynamical behavior of random DBNs, SBNs, DMNs,
and SMNs.
The number of possible functions generated by a single
unit in the four types of network is compared as follows.
n
The number of all Boolean functions is equal to 22 , growing
doubly exponentially with n. This is equal to the variety of
the random mapping on n units. The number of functions
generated by a single unit in DBNs is large for large K andnequal to 22 when K = n. In contrast, SBNs, DMNs, andSMNs are limited in terms of the number of possible functions.
The number of all majority vote units is asymptotically equal2
to 2n /2 ; the growth rate is only exponential. For the sparse
Boolean and majority vote networks, the number of functions
generated by a single unit is equal to 2K log2 n , growing only
algebraically with n. The differences in the variety of functionsin the four cases may result in different dynamical behaviorsof the networks, as we will analyze in the following.
III. DISTANCE LAW IN STATE TRANSITIONSThe network state at time t is given in vector form asx(t) = (x1 (t), . . . ,xn (t)).

(3)

Let X = {x} be the set of the N ≡ 2n states. Given a network,
the state transition is a mapping from X to itself. We write it
briefly as x(t + 1) = f x(t).
The dynamics of the distance between two state trajectories
has been studied to characterize dynamics in these networks.
We define the normalized Hamming distance between two
states x and y in X by
1 
|xi − yi |.
2n i=1n

D(x, y) =(4)

It should be noted that the distance is restricted to the range
0  D(x, y)  1. We let d = D(x, y) and d  = D(f x,f y).
The mapping from d to d  is a random variable and depends
on x and y because wij is a random variable and many pairsof x and y realize d = D(x, y). However, we can prove thatd  = ϕ(d) for a function ϕ(d) for any x and y almost always as
n → ∞. We call ϕ(d) the distance law. For DBNs, ϕ(d) = 0(d = 0) and ϕ(d) = 1/2 (d = 0). For SBNs [17],ϕ(d) = (1/2)[1 − (1 − d)K ].

(5)

where

(6)

ϕ(d) =

j =0


gK,j

K
j


d j (1 − d)K−j ,

(7)

(8)

j/K.

The dynamics of the distance under the annealed approximation is given by dt+1 = ϕ(dt ) [8,17–19]. For all four types of
network, ϕ(0) = 0. For DBNs, ϕ(d) is discontinuous at d = 0,
and the dynamics is essentially the same as that of a random
mapping on the N states. Therefore, various properties of the
dynamics such as the number of attractors, transient length, andcycle period are well characterized [5,6,8]. For SBNs, DMNs,
and SMNs, ϕ(d) is continuous at d = 0. It is known that d = 0
is a stable fixed point of mapping ϕ [i.e., 0 < ϕ  (0) < 1] only
for SBNs and SMNs with K = 1 or 2. Otherwise, dt converges
to a positive value d satisfying d = ϕ(d). The convergenceof the distance is usually fast and happens after ∼10 steps
except for DBNs where one step is enough for the distance toconverge.
IV. EXPONENT OF THE STATE CONCENTRATION

The average transient length before the orbit enters theattractor is analytically intractable. In addition, it may not
be a good measure of the quickness of the dynamics due tothe long-tailed nature of its distribution [16]. Therefore, we
introduce an alternative order parameter called the exponentof the state concentration. We use the so-called state transition
graph [5,6,20] defined as follows. A map f , either Boolean or
majority vote, induces a graph on N nodes. Each state x ∈ Xdefines a node and has exactly one outgoing link directed tonode f x.
Suppose that each of the N = 2n nodes (i.e., states) has atoken at t = 0. For each t (0), an application of f moves all
the tokens at each node x to node f x. Repeated applicationsof the mapping f elicit concentrations of tokens at specificnodes. We denote by f −t x the set of nodes whose tokens
move to x after t steps and by |f −t x| the number of tokens at
node x after t steps. Tokens are initially equally distributed,i.e., |f 0 x| = 1 for each x, and the total number of tokens isconserved throughout the dynamics, i.e.,|f −t x| = N(9)x∈Xfor t  0.
The in-degree of node x in the state transition graph is equal
to |f −1 x|. The nodes with f −1 x = ∅, where ∅ is the empty
set, do not have parent nodes. The set of such nodes is called
the Garden of Eden [5] and denoted by E1 . The nodes x ∈ E1
appear only as initial states. Only the nodes x ∈ X − E1 retain
tokens at t = 1. In general, we define Et ≡ {x|f −t x = ∅}, i.e.,the set of nodes that do not have tokens at time step t. Thereexists integer T such thatφ ⊂ E1 ⊂ E2 ⊂ · · · ⊂ ET = ET +1 = · · · ≡ E ∗ ,For SMNs [18],Kis the binomial coefficient andgK,j = (2/π ) sin−1

For DMNs [8–10],√
ϕ(d) = (2/π ) sin−1 d.

K
j

(10)

where T is the longest transient period and E ∗ is the set of
the transient states. The set of the attractors is given by A =X − E ∗ (Fig. 1).
To quantify the state concentration, we consider the numberof tokens that a token at x(0) and t = 0 meets after weapply f . We write the relationship f x(0) = x(1) succinctly

022814-2

STATE CONCENTRATION EXPONENT AS A MEASURE OF . . .

PHYSICAL REVIEW E 87, 022814 (2013)

x(0)

E1
E2

y(0)

d

E3
E*

f

f
A=X–E

d

*

as x(0) → x(1). Let S 1 be the conditional expectation
E[|f −1 x(1)| | x(0) → x(1)] of the in-degree of node x(1) [i.e.,
the number of parents of x(1)] given that x(0) → x(1) and thatx(0) is selected with equal probability (i.e., 1/N). In general,
we denote by S t the expected number of t-fold ancestor nodesof a node x(t) conditioned by a state transition path endingat x(t) through which a token has traveled, or equivalently,
conditioned by the uniformly distributed initial token x(0),i.e.,
S t ≡ E[|f −t x(t)| | x(0) → · · · → x(t − 1) → x(t)]. (11)Obviously S 0 = 1 and the sequence {S t } is monotonicallynondecreasing in t. If
S t = ect n , ct > 0,

(12)

holds true for large n, the tokens are exponentially concentrated
on nodes having at least a t-fold ancestor node. We refer toln S tn→∞ n

ct = lim(13)

as the t-step exponent of the concentration. The exponent ct
quantifies the degree of state concentration and is a measure ofquickness. It should be noted that we do not need to explicitly
evaluate the statistics of the transient to calculate ct .
The stochastic symmetry of units makes the calculationof S t tractable. To explain the symmetry, we consider the
majority vote network; similar arguments hold true for the
Boolean network. Because the weights wij are independently
and identically distributed, the probability distribution of the
mapping f is invariant under permutation of x1 , . . . ,xn , which
are passed as the arguments to fi (1  i  n). In addition,
the probability is invariant under flip of the sign of each xi .
Therefore, the following gauge invariance holds. First, theprobability distribution of x(t) is invariant under permutationof the unit indices. Second, the probability distribution isinvariant under a sign flip of any xi (t). Because any stateis mapped in a single step to a given x by permutation andsign flip, all the states are stochastically equivalent. Therefore,
Prob{|f −1 x| = k}, for example, is the same for all x, andProb{x(0) → x(1)} = 1/N for any x(0) and x(1).
We define a conditional probability distribution
rk = Prob{|f −1 x(1)| = k | x(0) → x(1)},(14)

which is the in-degree distribution of node x(1) conditioned by
x(0) → x(1). The symmetry guarantees that rk is independent

y(1)

x(1)

FIG. 1. Schematic of the dynamics of state concentration. E1
indicates the Garden of Eden, E2 indicates the nodes that do not have
grandparents, and A indicates the set of attractors.

FIG. 2. Schematic of one-step dynamics of the distance.

of x(0) and x(1). Let us compute
S1 =

N


krk .

(15)

k=1

We denote by y(0) a node such that D(x(0), y(0)) = d for agiven x(0). The number of nodes with distance d away fromx(0) is given by n≈ enH (d) ,
(16)
nd
where
H (d) ≡ −d ln d − (1 − d) ln(1 − d)(17)is the entropy. Because ϕ(d) is the probability that the ith components of f x(0) and f y(0) differ for any i, the probability thatD(f x(0),f y(0)) = d  (see Fig. 2 for a schematic illustration ofthis situation) is given by the binomial distribution as follows:




n

ϕ(d)nd [1 − ϕ(d)]n(1−d ) .
ψ(d |d) ≡(18)
nd In particular,
ψ(0|d) = [1 − ϕ(d)]n= Prob{f y(0) = x(1) | x(0) → x(1)}.

(19)

By using the saddle-point approximation, we obtain

n 

n
ψ(0|d)
S1 =
nd
nd=0

≈

exp n{H (z) + ln[1 − ϕ(z)]}dz ∝ enc1 ,(20)

c1 = H (d ∗ ) + ln[1 − ϕ(d ∗ )](21)

d ∗ = arg max{H (d) + ln[1 − ϕ(d)]}.

(22)

where

and
d

To evaluate ct in general, we consider a t-step state transition path Xt = {x(0) → x(1) → · · · → x(t) = x ∗ } ending
at x ∗ and calculate the conditional probability that another
path Yt = { y(0) → · · · → y(t)} ends at the same x ∗ . S t is the
expectation of the number of such t-step paths. Let us denotethe distance D(x(t  ), y(t  )) by dt  , where 0  t   t and dt = 0.
Then, under the Markov assumption, the probability of path Yt

022814-3

AMARI, ANDO, TOYOIZUMI, AND MASUDA

0.6

PHYSICAL REVIEW E 87, 022814 (2013)8

t =1:SMNt =2:SMNt =3:SMNt =4:SMNt =1:SBNt =2:SBNt =3:SBNt =4:SBN

0.4(a) DBN

6
St

105

t =1
t =2
t =3
t =4

4

ct

10

0
0

5

10

15
K

20

25

St

30

FIG. 3. (Color online) c1 , c2 , c3 , and c4 for SMNs and SBNs.

(23)t  =1The Markov assumption is valid for large n and a finite t.
Because there are ( ndn0 ) states y(0) possessing distance d0
from x(0), the expected number of paths is given by the
integration of ( ndn0 ) Prob {Yt |Xt } over all the possible distancesequences {d0 , . . . ,dt−1 ,dt = 0}. By using the saddle-point
approximation, we havetS t = exp nH (d0∗ ) +ln ψ(dt∗ |dt∗ −1 )(24)t  =1for large n, where dt∗ are the maximizers of the integrand in
the path integration. Equation (24) implies
ct =

t

{H (dt∗ −1 ) + dt∗ ln ϕ(dt∗ −1 )t  =1+ (1 − dt∗ ) ln[1 − ϕ(dt∗ −1 )]}.

110t  =tψ(dt  |dt  −1 ).

10

(25)

For example, for t = 2, we obtain

10

4

5

10

N

10

6

7

3

10

10

8

(c) DMN

3

conditioned by path Xt is represented in terms of the distancesof the two sequences, i.e., dt  , 0  t   t, byProb{Yt |Xt } =

10

2

St 10

10
3

103

4

102

2

0.2

10

(b) SBN

10

4

1

103
105

5

10

N

10

6

7

10

10

8

10

4

St 10

3

10

2

10

1

104

105

N

106

107

108

6

10

7

10

(d) SMN

3

10

10

4

5

10

N

10

8

FIG. 4. (Color online) S t exponentially increases with n except
in DBNs, (a) DBNs, (b) SBNs with K = 3, (c) DMNs, and (d) SMNs
with K = 3. The lines in (b), (c), and (d) indicate the theoreticalestimates (see Table I). Each point in the figure represents the averageof S t over 103 realizations of the network.

We verified Eq. (13) by comparing S t obtained from direct
numerical simulations [i.e., Eq. (11)] and ct generally given
by Eq. (25). The results shown in Fig. 4 indicate that thetheory (lines) seems to agree with numerical results at least
for large n; although the largest n value shown in the figure
is only n = 25. Therefore, the Markov assumption [Eq. (23)]implicitly assumed for t = 2, 3, and 4 in drawing Fig. 3 roughly
holds true at least up to t ≈ 4 for large n.
Theoretically, most sequences Yt that meet Xt after t stepsof state transition own the sequence of distance given by d ∗t =∗{d0∗ ,d1∗ , . . . ,dt−1,dt∗ = 0}. In particular, a majority of the initialstates Y0 is initially separated from X0 by d0∗ (t). Figure 4
suggests that this is the case at least up to t ≈ 4 for large
n. The sequence of distances d ∗t is shown for 1  t  4 inFig. 5.

c2 = H (d0∗ ) + H (d1∗ ) + ln[1 − ϕ(d1∗ )] + d1∗ ln ϕ(d0∗ )+ (1 − d1∗ ) ln[1 − ϕ(d0∗ )],(26)

V. IN-DEGREE DISTRIBUTION OF THE STATE
TRANSITION GRAPH

where

We calculate the incoming degree distribution{d0∗ ,d1∗ } = arg max{H (d0 ) + H (d1 ) + ln[1 − ϕ(d1 )]pk = Prob{|f −1 x| = k},

d0 ,d1+ d1 ln ϕ(d0 ) + (1 − d1 ) ln[1 − ϕ(d0 )]}.

(27)

On the basis of the expression of ϕ for SBNs and SMNs
shown before, the dependence of c1 , c2 , c3 , and c4 on K
is plotted in Fig. 3. For SBNs, ct (1  t  4) converges to
0 quickly as K increases. For DBNs, which is the case for
K = n, we trivially obtain ct = 0 at least for small t because
f is equivalent to the random mapping. Figure 3 indicates thatstate concentration occurs only for very small K in the random
Boolean network. In contrast, state concentration occurs evenfor large K in majority vote networks. In particular, for
DMNs with K → n, we obtain c1 ≈ 0.157 [10]. Figure 3 also
indicates that the state concentration quickly proceeds as tincreases, except in DBNs.

(28)


where k is the in-degree of a state and N
k=0 pk = 1. Because
each node in the state transition graph has exactly one outgoing
TABLE I. Theoretical estimates of ct = ln S t /n.
t

SBNs

DMNs

SMNs

1
2
3
4

0.223
0.323
0.380
0.416

0.157
0.205
0.225
0.232

0.256
0.363
0.421
0.460

022814-4

STATE CONCENTRATION EXPONENT AS A MEASURE OF . . .

PHYSICAL REVIEW E 87, 022814 (2013)

0.5

100

10

10-2

0.4

Pk 10

d∗t

(a) DBN

Pk 10

0

10-8

10
10

0.1

d∗1
0

d∗2
1

d∗3
2

d∗4
3

4

t
FIG. 5. (Color online) Sequence of the most likely distances d ∗t =∗ ∗∗,dt∗ = 0} for 1  t  4.
{d0 ,d1 , . . . ,dt−1link, we have
k =

N


kpk = 1,

(29)

k=0

where · indicates the expectation. Because rk = kpk [8] (alsosee [21] for an example), we obtaink 2  =N

k 2 pk =N

krk = S 1 = enc1 .

0

10

-2

Pk 10

-4

-4

10-6

10-8

0.2

0

1

10

10

2

3

k

10

4

10

10

5

(c) DMN

10
10

0

Pk 10

1

10

10

2

k

10

3

10

4

10

5

103

104

105

(d) SMN

-4

10-6

-8

10-8

100

0

10-2

10-6
10

(b) SBN

10-2

-4

10-6

0.3

0

101

102

k

103

104

105

100

101

102

k

FIG. 6. (Color online) Complementary in-degree distribution of
pk (i.e., Pk ≡ N
k  =k pk  ) of the state transition graph. (a) DBNs,(n = 30 and K = 30). The numerical results are shown by squares,
and the Poisson distribution with mean 1 is indicated by theline. (b) SBNs, (n = 30 and K = 3). (c) DMNs, (n = 30 and
K = 30). (d) SMNs, (n = 30 and K = 3). The fitting curves,
Pk ∝ k −1.48 exp{−0.000 298k}, Pk ∝ k −1.72 exp{−0.000 985k}, andPk ∝ k −0.936 exp{−0.000 786k}, for (b), (c), and (d), respectively,
obtained from the least square error method, are shown by the lines
as guides to the eyes.

(30)

k=0

VI. DISCUSSION AND CONCLUSIONS

Therefore, c1 > 0 indicates that k 2  diverges in the limit of
N = 2n → ∞, reminiscent of the scale-free property of thestate transition graph [21–23].
For DBNs, the state transition graph is the directed randomgraph in which pk obeys the Poisson distribution (i.e., pk =1/ek!) with mean and variance 1 [5,6]. Therefore, k 2  = 2,
proving that c1 = 0 for DBNs (i.e., there is no exponential
state concentration). This is consistent with Fig. 4(a) (circles).
Figure 3 suggests that c1 ≈ 0 when K is larger than ∼=10.
Therefore, the in-degree distribution of the state transition
graph is also narrow for SBNs with K  10. We verified thatthe numerically obtained in-degree distribution for the random
Boolean network with n = 30 and K = 20 approximately
obeys the Poisson distribution [Fig. 6(a)].
In contrast, the positive value of c1 found for SBNs withsmall K, DMNs, and SMNs (Fig. 3) indicates that k 2 (=S 1 )diverges exponentially in n. This is actually the case, as shownin Figs. 4(b)–4(d). For scale-free networks with pk ≈ k −γ ,the extremal criterion would lead to γ ≈ (c1 + 3 ln 2)/(c1 +ln 2) [22,23]. However, the in-degree distribution numericallyobtained for majority vote networks, shown in Figs. 6(c)and 6(d), deviates from a power law. The in-degree distribution
numerically obtained for SBNs [Fig. 6(b)] is also different
from a power law [20]. To guide the eyes, fitting curves on
the basis of a power law with an exponential cutoff are shownby the lines in Figs. 6(b)–6(d). In fact, the power law is not
the only distribution that yields the divergence of k 2 . In thepresent case, the position of the exponential cutoff may mildly
diverge as n becomes large.

In summary, we provided a unified framework for analyzing
the state concentration. We found that exponential state
concentration occurs in SBNs with small K and the majority
vote networks with arbitrary K (i.e., DMNs and SMNs), but
not in DBNs. We also revealed the long-tailed distributions of
the in-degree of the state transition graph in SBNs, DMNs, andSMNs, but not in DBNs.
We briefly discuss the relationship between the quickness,measured by the exponent of the state concentration in thisstudy, and the robustness of the dynamics. The robustness ofthe dynamics is often measured in terms of damage spreading.
It is a long-term property concerning the stability of d = 0
for mapping ϕ. As we mentioned, d = 0 is an unstable fixed
point of ϕ unless K = 1 or 2. Although SMNs with K = 1
or 2 satisfies quickness and robustness, we do not discussthese cases because the dynamics in these cases is just frozen[18,19]. Here we consider a simpler measure of robustness
based on a one-step property, i.e., how a difference by a single
bit evolves after a single application of f . This is essentiallythe same as the Boolean derivative, a measure of the robustness
used for analyzing random Boolean networks [12–15]. In
SMNs, the probability that a single bit flip in input results
in a bit flip after the application of f is given by

k=0

gK,1 = (2/π ) sin−1

1/K.

(31)

Because gK,1
√ is equal to 0.5 for K = 2 and decreases accordingto ≈2/(π K) as K increases, the random majority votenetwork is robust except for very small K. However, in the
random Boolean network, the same flip probability is equal to022814-5

AMARI, ANDO, TOYOIZUMI, AND MASUDAPHYSICAL REVIEW E 87, 022814 (2013)

K

1/2 − 1/22 , which quickly approaches 1/2 as K increases.
In particular, the flip probability for the Boolean network
at K = 2 is equal to 7/16 = 0.4375, which is close to thevalues for the majority vote network with K = 2 (i.e., 0.5)
and K = 3 (i.e., 0.392). Although the Boolean network with
K = 1 has sufficient robustness, the dynamics in this case isfrozen [24]. Therefore, we consider that the robustness of the
one-step dynamics holds true in DMNs, but not in DBNs,
SBNs, and SMNs. By combining this observation with our
main results, we conclude that quickness and robustness are
suitably balanced in DMNs, but not in DBNs, SBNs, and
SMNs.

[1] S.-I. Amari, IEEE Trans. Comput. 11, 1197 (1972).
[2] J. J. Hopfield, Proc. Natl. Acad. Sci. USA 79, 2554
(1982).
[3] J. Hertz, A. Krogh, and R. G. Palmer, Introduction to the Theory
of Neural Computation (Westview Press, Boulder, CO, 1991).
[4] S. A. Kauffman, J. Theor. Biol. 22, 437 (1969).
[5] S. A. Kauffman, Physica D 10, 145 (1984).
[6] S. A. Kauffman, The Origin of Orders: Self-Organization and
Selection in Evolution (Oxford University Press, Oxford, 1993).
[7] S. Bornholdt, J. R. Soc. Interface 5, 85 (2008).
[8] S. Amari, Kybernetik 14, 201 (1974).
[9] S. Amari, K. Yoshida, and K. Kanatani, SIAM J. Appl. Math.
33, 95 (1977).
[10] S. Amari, Proc. IEEE 78, 1443 (1990).
[11] C. Castellano, S. Fortunato, and V. Loreto, Rev. Mod. Phys. 81,
591 (2009).
[12] B. Luque and R. V. Solé, Phys. Rev. E 55, 257 (1997).
[13] B. Luque and R. V. Solé, Physica A 284, 33 (2000).

[14] S. Kauffman, C. Peterson, B. Samuelsson, and C. Troein, Proc.
Natl. Acad. Sci. USA 101, 17102 (2004).
[15] I. Shmulevich and S. A. Kauffman, Phys. Rev. Lett. 93, 048701(2004).
[16] A. Bhattacharjya and S. Liang, Phys. Rev. Lett. 77, 1644 (1996).
[17] B. Derrida and Y. Pomeau, Europhys. Lett. 1, 45 (1986);
B. Derrida and G. Weisbuch, J. Phys. (Paris) 47, 1297 (1986).
[18] B. Derrida, J. Phys. A 20, L721 (1987).
[19] K. E. Kürten, Phys. Lett. A 129, 157 (1988); J. Phys. A 21, L615
(1988).
[20] A. Shreim, A. Berdahl, V. Sood, P. Grassberger, and M. Paczuski,
New J. Phys. 10, 013028 (2008).
[21] M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. E
64, 026118 (2001).
[22] M. E. J. Newman, Contemp. Phys. 46, 323 (2005).
[23] S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Rev. Mod.
Phys. 80, 1275 (2008).
[24] H. Flyvbjerg and N. J. Kjaer, J. Phys. A 21, 1695 (1988).

022814-6