# Network Structure and Activity in Boolean Networks

Abhijin Adiga, Hilton Galyean, Chris J. Kuhlman, Michael Levet, Henning S. Mortveit, Sichao Wu

► To cite this version:

Abhijin Adiga, Hilton Galyean, Chris J. Kuhlman, Michael Levet, Henning S. Mortveit, et al.. Network Structure and Activity in Boolean Networks. 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2015, Turku, Finland. pp.210-223, 10.1007/978-3-662-47221-7_16. hal-01442474

HAL Id: hal-01442474

https://inria.hal.science/hal-01442474

Submitted on 20 Jan 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
Network Structure and
Activity in Boolean Networks

Abhijin Adiga¹, Hilton Galyean¹,³, Chris J. Kuhlman¹, Michael Levet¹,²,
Henning S. Mortveit¹,², and Sichao Wu¹

¹ Network Dynamics and Simulation Science Laboratory, VBI, Virginia Tech

² Department of Mathematics, Virginia Tech

³ Department of Physics, Virginia Tech

`{abhijin,ckuhlman,henning.mortveit,sichao}@vbi.vt.edu;`

`{hgalyean,mlevet}@vt.edu`

**Abstract.** In this paper we extend the notion of activity for Boolean networks introduced by Shmulevich and Kauffman (2004). Unlike the existing notion, we take into account the actual graph structure of the Boolean network. As illustrations, we determine the activity of all elementary cellular automata, and *d*-regular trees and square lattices where the vertex functions are bi-threshold and logical nor functions.

The notion of activity measures the probability that a perturbation in an initial state produces a different successor state than that of the original unperturbed state. Apart from capturing sensitive dependence on initial conditions, activity provides a possible measure for the significance or influence of a variable. Identifying the most active variables may offer insight into design of, for example, biological experiments of systems modeled by Boolean networks. We conclude with some open questions and thoughts on directions for future research related to activity.

*Keywords:* Boolean networks; finite dynamical system, activity; sensitivity; network; sensitive dependence on initial conditions;<fnref n="4" />

# 1 Introduction

A Boolean network (BN) is a map of the form

$$F = (f_1, \dots, f_n) : \{0, 1\}^n \to \{0, 1\}^n. \qquad (1)$$

BNs were originally proposed as a model for many biological phenomena [9, 10], but have now been used to capture and analyze a range of complex systems and their dynamics [2]. Associated to *F* we have the *dependency graph of F* whose vertex set is {1, 2, ..., *n*} and with edges all (*i*, *j*) for which the function *f*<sub>*i*</sub> depends non-trivially on the variable *x*<sub>*j*</sub>. See [8, 17, 14] for more general discussions of maps *F*.

<footnote n="4">⁴ Corresponding author: Henning S. Mortveit; email: henning.mortveit@vt.edu; Telephone: +1 540 231-5327; Fax: +1 540 231 2891</footnote>
The study of stability and the response to perturbations of Boolean networks is central to increased understanding of their dynamical properties. Perturbations may take many forms, with examples including perturbations of the dependency graph [1, 13, 15], the vertex states [19, 7, 18], the vertex functions [20, 21], or combinations of these.

This paper is concerned with noise applied to vertex states. Specifically, we want to know the following:

What is the probability that $F(x)$ and $F(x + e_i)$ are different?

Here $i$ is a vertex while $e_i$ is the $i^{th}$ unit vector with the usual addition modulo 2. In [19], Shmulevich and Kauffman considered Boolean networks over regular graphs with $f_j = f$ for all vertices $j$, that is, a common vertex function. They defined the notion of activity of $f$ with respect to its $i^{th}$ argument as the expected value of the Boolean derivative of $f$ with respect to its $i^{th}$ variable. Under their assumptions, this may give a reasonable indication of the expected impact of perturbations to the $i^{th}$ variable under the evolution of $F$. However, this approach does not consider the impact of the dependency graph structure. We remark that Layne et al. compute the activities of nested canalyzing functions given their canalyzing depth, extending results in [19] on canalyzing functions, see [12],

This question of sensitivity has also been studied when $x$ is restricted to attractors in order to assess stability of long-term dynamics under state noise. The notion of threshold ergodic sets (TESs) is introduced in [16] and studied further in [13, 11]. The structure of TESs capture long-term stability under state perturbations of periodic orbits and the resulting mixing between attractors that may happen as a result.

Other tools for analyzing sensitivity of vertex noise includes Lyapunov exponents, see for example [4, 3], although this is perhaps mostly relevant or suited for the infinite case such as cellular automata over (infinite) regular lattices. Also, the notion of *Derrida diagrams* have been used to quantify how *Hamming classes* of states separate on average [5, 6] after one or $k$ transitions under $F$. Derrida diagrams, however, are mainly analyzed through numerical experiments via sampling. Moreover, analyzing how Hamming classes of large distance separate under $F$ may not be so insightful – it seems more relevant to limit oneself to the case of nearby classes of vertex states.

Returning to the original question, we note that $F(x)$ and $F(x + e_i)$ may only differ in the coordinates $j$ for which $f_j$ depends on $x_i$. The answer to the question therefore depends on the vertex functions in the 1-neighborhood of $i$ in the dependency graph $X$, and therefore the structure of the induced subgraph of the 2-neighborhood of $i$ in $X$ with the omission of edges connecting pairs of vertices both of distance 2 from $i$. We denote this subgraph by $X(i; 2)$, see Figure 1.

To determine the activity of vertex $i$ one will in general have to evaluate $F$ over all possible states of $X(i; 2)$, a problem which, in the general case, is computationally intractable. We will address three cases in this paper: the first
case is when $X(i; 2)$ is a tree, the second case is that of elementary cellular automata (a special case of the former case), and the case where $X$ is a regular, square, 2-dimensional lattice. Work for other graph classes is in progress and we comment on some of the challenges in the Summary section. Here we remark that a major source of challenges for analytic computations is the introduction of *type-3* and *type-4* edges as illustrated in Figure 1. Lack of symmetry adds additional challenges. The activity of a vertex can be evaluated analytically using the inclusion-exclusion principle, and type-3 and type-4 edges impact the complexity of the combinatorics.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** The subgraph $X(i; 2)$ of $X$ induced by vertex $i$ and its distance $\le 2$ neighbors. Vertices belonging to the closed 1-neighborhood $n[i]$ of $i$ are marked red. Type-3 edges (relative to $i$) connect neighbors of $i$, while type-4 edges connect neighbors of $j \in n'[i]$ through a common neighbor different from $i$. Here $n'[i]$ is $n[i]$ with $i$ omitted. Edges connecting vertices of distance 2 from $i$ in $X$ do not belong to $X(i; 2)$. For terminology we refer to Section 2.</figcaption></figure>

A goal of the work on activity started here is as follows: when given a network $X$ and vertex functions $(f_i)_i$, we would like to rank the vertices by activity in decreasing order. Just being able to identify for example the ten (say) vertices of highest activity would also be very useful. This information would allow one to identify the vertices for which state perturbations are most likely to produce different outcomes, at least in the short term. In a biological experiment for which there is a BN model of the form (1), one may then be able to allocate more resources to the measurement of such states, or perhaps ensure that these states are carefully controlled and locked at their intended values.

**Paper organization.** After basic definitions and terminology in Section 2 we carefully define a new notion of activity denoted by $\bar{\alpha}_{F,i}$. Basic results to help in analytic evaluations of $\bar{\alpha}_{F,i}$ are given in Section 3 followed by specific results for the elementary cellular automata in Section 4, $d$-regular trees in Section 5, and then nor-BNs over square lattices in Section 6. A central goal is to relate
the structure of $X(i; 2)$ and the functions $(f_j)_j$ to $\bar{\alpha}_{F,i}$. We conclude with open questions and possible directions for followup work in Section 7.

## 2 Background, Definitions and Terminology

In this paper we consider the discrete dynamical systems of the form (1) where each map $f_i$ is of the form $f_i: \{0, 1\}^n \to \{0, 1\}$. However, $f_i$ will in general depend nontrivially only on some subset of the variables $x_1, x_2, \dots, x_n$, a fact that is captured by the dependency graph defined in the introduction and denoted by $X_F$ or simply $X$ when $F$ is implied. The graph $X$ is generally directed and will contain loops. We will, however, limit ourselves to undirected graphs.

Each vertex $i$ has a *vertex state* $x_i \in \{0, 1\}$ and a *vertex function* of the form $f_i: \{0, 1\}^{d(i)+1} \to \{0, 1\}$ taking as arguments the states of vertices in the 1-neighborhood of $i$ in $X$. Here $d(i)$ is the degree of vertex $i$. We write $n[i]$ for the ordered sequence of vertices contained in the 1-neighborhood of $i$ (with $i$ included) and $x[i]$ for the corresponding sequence of vertex states. We denote the *system state* by $x = (x_1, \dots, x_n) \in \{0, 1\}^n$.

We will write the evaluation of $F$ in (1) as

$$F(x) = (f_1(x[1]), f_2(x[2]), \dots, f_n(x[n])) .$$

The phase space of the map $F$ in (1) is the directed graph $\Gamma(F)$ with vertex set $\{0, 1\}^n$ and directed edges all pairs $(x, F(x))$. A state on a cycle in $\Gamma(F)$ is called a *periodic point* and a state on a cycle of length one is a *fixed point*. The sets of all such points are denoted by $\text{Per}(F)$ and $\text{Fix}(F)$ respectively. All other states are *transient states*. Since $\{0, 1\}^n$ is finite, the phase space of $F$ consists of a collection of oriented cycles (called periodic orbits), possibly with directed trees attached at states contained on cycles.

In this paper we analyze *short-term stability of dynamics* through the function $\alpha_{F,i}: K^n \to \{0, 1\}$ defined by

$$\alpha_{F,i}(x) = \mathbb{I}[F(x + e_i) \neq F(x)] \qquad (2)$$

where $\mathbb{I}$ is the indicator function and $e_i$ is the $i^{th}$ unit vector. In other words, $\alpha_{F,i}(x)$ measures if perturbing $x$ by $e_i$ results in a different successor state under $F$ than $F(x)$.

**Definition 1.** The activity of $F$ with respect to vertex $i$ is the expectation value of $\alpha_{F,i}$ using the uniform measure on $K^n$:

$$\bar{\alpha}_{F,i} = \mathbb{E}[\alpha_{F,i}] . \qquad (3)$$

The activity of $F$ is the vector

$$\bar{\alpha}_F = (\bar{\alpha}_{F,1}, \bar{\alpha}_{F,2}, \dots, \bar{\alpha}_{F,n}), \qquad (4)$$

while the sensitivity of $F$ is the average activity $\bar{\alpha} = \sum_{i=1}^n \bar{\alpha}_{F,i}/n$.
For a randomly chosen state $x \in K^n$, the value $\bar{\alpha}_{F,i}$ may be interpreted as the probability that perturbing $x_i$ will cause $F(x+e_i) \neq F(x)$ to hold. This activity notion may naturally be regarded as a measure of sensitivity with respect to initial conditions.

From (2) it is clear that $\bar{\alpha}_{F,i}$ depends on the functions $f_j$ with $j \in n[i]$ and the structure of the distance-2 subgraph $X(i; 2)$, see Figure 1. The literature (see, e.g. [19, 12]) has focused on a very special case when considering activity. Rather than considering the general case and Equation (2), they have focused on the case where $X$ is a regular graph where each vertex has degree $d$ and all vertices share a common vertex function $f: K^d \to K$. In this setting, activity is defined with respect to $f$ and its $i^{th}$ argument, that is, as the expectation value of the function $\mathbb{I}[f(x + e_i) \neq f(x)]$ where $x \in K^{d+1}$. Clearly, this measure of activity is always less than or equal to $\mathbb{E}[\alpha_{F,i}]$. Again, we note that this simpler notion of activity does not account for the network structure of $X(i; 2)$.

## 3 Preliminary Results

For the evaluation of $\bar{\alpha}_{F,i}$ we introduce some notation. In the following we set $K = \{0, 1\}$, write $N_i$ for the size of $X(i; 2)$, and $K(i) = K^{N_i}$ for the projection of $K^n$ onto the set of vertex states associated to $X(i; 2)$. For $j \in n[i]$, define the sets $A_j(i) \subset K(i)$ by

$$A_j(i) = \{x \in K(i) \mid F(x + e_i)_j \neq F(x)_j\}.$$

These sets appear in the evaluation of $\bar{\alpha}_{F,i}$, see Proposition 2. For convenience, we also set

$$A_j^m(i) = \{x \in A_j(i) \mid x_i = m\},$$

for $m = 0, 1$. We write $\bar{A}_j(i) = A_j^0(i)$ and $\binom{n}{k}$ for binomial coefficients using the convention that it evaluates to zero if either $k < 0$ or $n - k < 0$.

The following proposition provides a somewhat simplified approach for evaluating $\bar{\alpha}_{F,i}$ in the general case.

**Proposition 2.** Let $X$ be a graph and $F$ a map over $X$ as in (1). The activity of $F$ with respect to vertex $i$ is

$$\bar{\alpha}_{F,i} = \Pr\left(\bigcup_{j \in n[i]} A_j \mid x_i = 0\right) = \Pr\left(\bigcup_{j \in n[i]} \bar{A}_j\right). \qquad (5)$$

*Proof.* As stated earlier, we can write

$$\bar{\alpha}_{F,i} = \mathbb{E}[\alpha_{F,i}] = \sum_{x \in K^n} \alpha_{F,i}(x) \Pr(x) = \sum_{x \in K(i)} \alpha_{F,i}(x) \Pr(x) = \Pr\left[\bigcup_{j \in n[i]} A_j\right],$$

where probabilities in the first and second sum are in $K^n$ and $K(i)$, respectively. This follows by considering the relevant cylinder sets. Equation (5) follows by conditioning on the possible states for $x_i$. Since we are in the Boolean case, we have a bijection between each pair of sets $A_j^0$ and $A_j^1$ for $j \in n[i]$ which immediately allows us to deduce Equation (5).
As an example, consider the complete graph $X = K_n$ with threshold functions at every vertex. Recall that the standard Boolean threshold function, denoted by $\tau_{k,n}: K^n \rightarrow K$, is defined by

$$ \tau_{k,n}(x_1, \dots, x_n) = \begin{cases} 1, & \text{if } \sum_{j=1}^{n} x_j \ge k, \\ 0, & \text{otherwise.} \end{cases} \qquad (6) $$

Here we have

$$ \bar{\alpha}_{F,i} = \binom{n-1}{k-1} / 2^{n-1}. $$

To see this, note first that all the sets $\bar{A}_j(i)$ are identical. For a state $x$ with $x_i = 0$ to satisfy $\tau_k(x) \ne \tau_k(x+e_i)$ it is necessary and sufficient that $x$ belong to Hamming class $k-1$. Since $x_i = 0$, it follows from Proposition 2 that $\text{Pr}(\bar{A}_j(i)) = \frac{1}{2^{n-1}}|A_j| = \binom{n-1}{k-1}/2^{n-1}$ as stated.

Next, consider the Boolean nor-function $\text{nor}_m: K^m \rightarrow K$ defined by

$$ \text{nor}_m(x_1, \dots, x_m) = (1+x_1) \dots (1+x_m), \qquad (7) $$

with arithmetic operations modulo 2. If we use the nor-function over $K_n$ we obtain

$$ \bar{\alpha}_{F,i} = 1/2^{n-1}. $$

Again, $\bar{A}_j = \bar{A}_k$ for all $j, k \in n[i]$ and we have $F(x+e_i)_i \ne F(x)_i$ precisely when $x_j = 0$ for all $j \in n(i)$ leading to $\text{Pr}(\bar{A}_j) = \frac{1}{2^{n-1}}$. We record the previous two results as a proposition:

**Proposition 3.** If $F$ is the GDS map induced by the nor-function over $K_n$, then

$$ \bar{\alpha}_{F,i} = \frac{1}{2^{n-1}}, $$

and if $F$ is induced by the $k$-threshold function over $K_n$, then

$$ \bar{\alpha}_{F,i} = \binom{n-1}{k-1} / 2^{n-1}. $$

In the computations to follow, we will frequently need to evaluate the probability of the union of the $A_j$'s. For this, let $B$ denote the union of $A_j$'s for all $j \ne i$. We then have

$$ \text{Pr}\left[\bigcup_{j \in n[i]} A_j\right] = \text{Pr}(A_i \cup B) = \text{Pr}(B) + \text{Pr}(A_i \cap B^c) = 1 - \text{Pr}(B^c) + \text{Pr}(A_i \cap B^c), \qquad (8) $$

where $B^c$ denotes the complement of $B$.
## 4 Activity of Elementary Cellular Automata

The evaluation of Equation (5) can often be done through the inclusion-exclusion principle. We demonstrate this in the context of elementary cellular automata (ECA). This also makes it clear how the structure of X comes into play for the evaluation of $\bar{\alpha}_{F,i}$.

Let $F$ be the ECA map over $X = \text{Circle}_n$ with vertex functions given by $f: \{0,1\}^3 \to \{0,1\}$. We will assume that $n \ge 5$; the case $n = 3$ corresponds to the complete graph $K_3$ and the case $n = 4$ can be done quite easily. Here we have

$$ \bar{\alpha}_{F,i} = \Pr(\bar{A}_{i-1}(i) \cup \bar{A}_i(i) \cup \bar{A}_{i+1}(i)). $$

Applying the definitions,

$$ \bar{A}_j(i) = \{x = (x_{i-1}, x_{i-1}, x_i = 0, x_{i+1}, x_{i+2}) \mid \text{and } f(x[j]) \neq f((x+e_i)[j])\} \quad (9) $$

for $j \in n[i] = \{i-1, i, i+1\}$ with indices modulo $n$.

**Proposition 4.** *The activity for k-threshold ECA is*

$$ \bar{\alpha}_{F,i} = \begin{cases} 0, & \text{if } k = 0 \text{ or } k > 3, \\ 1/2, & \text{if } k = 1 \text{ or } k = 3, \\ 7/8, & \text{if } k = 2. \end{cases} $$

*Proof.* Clearly, for $k = 0$ and $k > 3$ we always have $F(x+e_i) = F(x)$ so in these cases it follows that $\bar{\alpha}_{F,i} = 0$. The cases $k = 1$ and $k = 3$ are symmetric, and, using $k = 1$, we have

$$ \begin{aligned} \bar{A}_{i-1} &= \{(0,0,0, x_{i+1}, x_{i+2})\}, \\ \bar{A}_{i} &= \{(x_{i-2}, 0, 0, 0, x_{i+2})\}, \text{ and} \\ \bar{A}_{i+1} &= \{(x_{i-1}, x_{i-1}, 0, 0, 0)\}. \end{aligned} $$

By the inclusion-exclusion principle, it follows that

$$ \begin{aligned} |\bar{A}_{i-1} \cup \bar{A}_i \cup \bar{A}_{i+1}| &= |\bar{A}_{i-1}| + |\bar{A}_i| + |\bar{A}_{i+1}| \\ &\quad - |\bar{A}_{i-1} \cap \bar{A}_i| - |\bar{A}_{i-1} \cap \bar{A}_{i+1}| - |\bar{A}_i \cap \bar{A}_{i+1}| \\ &\quad + |\bar{A}_{i-1} \cap \bar{A}_i \cap \bar{A}_{i+1}| \\ &= 3 \times 4 - 2 - 1 - 2 + 1 = 8. \end{aligned} $$

This yields $\bar{\alpha}_{F,i} = 8/2^4 = 1/2$. The proof for the case $k = 2$ is similar to that of $k = 1$ so we leave this to the reader.

**Remark 5.** If we instead use the nor-function, then $\bar{\alpha}_{F,i} = 1/2$ when $n \ge 5$.

**Remark 6.** In [19], activity is defined with respect to $f$ instead of $F$ and its $i^{th}$ argument. With this context, $\bar{\alpha}_{f,i}(x) = \mathbb{E}[\mathbb{I}[f(x+e_i) \neq f(x)]$. Clearly, we always have $\bar{\alpha}_{f,i} \le \bar{\alpha}_{F,i}$. As an example, for circle graph of girth $\ge 5$ and threshold-1 functions it can be verified that $\bar{\alpha}_{f,i} = 0.25$ and we have already shown that $\bar{\alpha}_{F,i} = 0.5$ in this case.
<figure><img src="image_3.png" /><figcaption>Fig. 2. Activity of ECA by rule number. With the exception of the constant rules of activity 0, all rules have activity $\ge 1/2$ with most rules exceeding 3/4.</figcaption></figure>

## 5 Activity over d-Regular Trees

The case of d-regular trees is natural as a starting point. Here the sets $A_j$ (or more precisely, the sets $n[j]$) with $j \ne i$ only overlap at vertex $i$. As a result, when we condition on $x_i = m$, the resulting sets are independent. More generally, this will hold if the girth of the graph is at least 5.

The Boolean bi-threshold function $\tau_{i,k_{01},k_{10},n}: K^n \to K$ generalizes standard threshold functions and is defined by

$$ \tau_{i,k_{01},k_{10},n}(x_1, \dots, x_n) = \begin{cases} 1, & \text{if } x_i = 0 \text{ and } \sum_{j=1}^n x_j \ge k_{01} \\ 0, & \text{if } x_i = 1 \text{ and } \sum_{j=1}^n x_j < k_{10} \\ x_i, & \text{otherwise,} \end{cases} \quad (10) $$

where the integers $k_{01}$ and $k_{10}$ are the up- and down-thresholds, respectively. Here $i$ is a designated vertex – it will be the index of a vertex function. If the up- and down-thresholds are the same we get standard threshold systems.

**Proposition 7.** Let $X$ be a d-regular graph of girth $\ge 5$, and $F$ the GDS map over $X$ with the bi-threshold vertex functions as in Equation (10). Then the activity of $F$ with respect to vertex $i$ is given by

$$ \bar{\alpha}_{F,i} = 1 - \left[ \frac{2^d - \binom{d-1}{k_{01}-1} - \binom{d-1}{k_{10}-2}}{2^d} \right]^d + \frac{1}{2} \sum_{k=k_{01},k_{10}} \frac{\binom{d}{k-1}}{2^d} \left[ \frac{2^{d-1} - \binom{d-1}{k_{10}-2}}{2^{d-1}} \right]^{k-1} \left[ \frac{2^{d-1} - \binom{d-1}{k_{01}-1}}{2^{d-1}} \right]^{d-(k-1)}. \quad (11) $$
Proof. Let B denote the union of $A_j$'s for all $j \neq i$ as in (8) and note that $B^c$ is the event that none of the $A_j$'s occur for $j \neq i$. Using girth $\ge 5$ and the resulting independence from conditioning on $x_i$ we can write

$$ 
\begin{aligned}
\Pr(B^c) &= \frac{1}{2}\Pr(B^c | x_i = 0) + \frac{1}{2}\Pr(B^c | x_i = 1) \\
&= \frac{1}{2}\left( \bigcap_{\substack{j \in n[i] \\ j \neq i}} A_j^c | x_i = 0 \right) + \frac{1}{2}\left( \bigcap_{\substack{j \in n[i] \\ j \neq i}} A_j^c | x_i = 1 \right) = \left( \bigcap_{\substack{j \in n[i] \\ j \neq i}} A_j^c | x_i = 0 \right) \\
&= \prod_{\substack{j \in n[i] \\ j \neq i}} \Pr(A_j^c | x_i = 0).
\end{aligned} 
\quad (12) $$

Next we have

$$ 
\begin{aligned}
\Pr(A_j^c | x_i = 0) &= \frac{1}{2}\Pr(A_j^c | x_i = 0 \text{ and } x_j = 0) + \frac{1}{2}\Pr(A_j^c | x_i = 0 \text{ and } x_j = 1) \\
&= \frac{1}{2} \cdot \frac{2^{d-1} - \binom{d-1}{k_{01}-1}}{2^{d-1}} + \frac{1}{2} \cdot \frac{2^{d-1} - \binom{d-1}{k_{10}-2}}{2^{d-1}} \\
&= \left[ 2^d - \binom{d-1}{k_{01}-1} - \binom{d-1}{k_{10}-2} \right] / 2^d,
\end{aligned} 
$$

which substituted into Equation (12) yields

$$ \Pr(B^c) = \left[ \frac{2^d - \binom{d-1}{k_{01}-1} - \binom{d-1}{k_{10}-2}}{2^d} \right]^d. \quad (13) $$

Next, we compute the probability of $A_i \cap B^c$ as

$$ 
\begin{aligned}
\Pr(A_i \cap B^c) &= \frac{1}{2}\Pr(A_i \cap B^c | x_i = 0) + \frac{1}{2}\Pr(A_i \cap B^c | x_i = 1) \\
&= \frac{1}{2}\Pr(A_i | x_i = 0) \cdot \Pr(B^c | A_i \text{ and } x_i = 0) \\
&\quad + \frac{1}{2}\Pr(A_i | x_i = 1) \cdot \Pr(B^c | A_i \text{ and } x_i = 1) \\
&= \frac{\binom{d}{k_{01}-1}}{2^{d+1}} \left[ \frac{2^{d-1} - \binom{d-1}{k_{10}-2}}{2^{d-1}} \right]^{k_{01}-1} \left[ \frac{2^{d-1} - \binom{d-1}{k_{01}-1}}{2^{d-1}} \right]^{d-(k_{01}-1)} \\
&\quad + \frac{\binom{d}{k_{10}-1}}{2^{d+1}} \left[ \frac{2^{d-1} - \binom{d-1}{k_{10}-2}}{2^{d-1}} \right]^{k_{10}-1} \left[ \frac{2^{d-1} - \binom{d-1}{k_{01}-1}}{2^{d-1}} \right]^{d-(k_{10}-1)} \\
&= \frac{1}{2} \sum_{k=k_{01}, k_{10}} \frac{\binom{d}{k-1}}{2^d} \left[ \frac{2^{d-1} - \binom{d-1}{k_{10}-2}}{2^{d-1}} \right]^{k-1} \left[ \frac{2^{d-1} - \binom{d-1}{k_{01}-1}}{2^{d-1}} \right]^{d-(k-1)}.
\end{aligned} 
\quad (14) $$

Substituting Equation (13) and (14) into Equation (8) leads to Equation (11), which ends the proof.

Since the standard threshold function is a special case of the bi-threshold function when $k_{01}$ and $k_{10}$ coincide, it is straightforward to obtain following corollary.
**Corollary 8.** If F is the GDS map with k-threshold vertex functions over a d-regular graph of girth $\ge 5$, then the activity of F with respect to vertex i is

$$ \bar{\alpha}_{F,i} = 1 - \left[ \frac{2^d - \binom{d}{k-1}}{2^d} \right]^d + \frac{\binom{d}{k-1}}{2^d} \left[ \frac{2^{d-1} - \binom{d-1}{k-2}}{2^{d-1}} \right]^{k-1} \left[ \frac{2^{d-1} - \binom{d-1}{k-1}}{2^{d-1}} \right]^{d-(k-1)}. \quad (15) $$

We next consider the nor-function.

**Proposition 9.** Let X be a d-regular graph of girth $\ge 5$ and F the GDS map over X induced by the nor-function. Then the activity of F with respect to i is given by

$$ \bar{\alpha}_{F,i} = 1 - \left(1 - \frac{1}{2^d}\right)^d + \left(\frac{1}{2} - \frac{1}{2^d}\right)^d. \quad (16) $$

*Proof.* Conditioning on $x_i = 0$ and using independence we have

$$ \mathrm{Pr}(B^c) = \mathrm{Pr} \left( \bigcap_{j \in n(i)} A_j^c \right) = \prod_{j \in n(i)} \mathrm{Pr}(A_j). \quad (17) $$

For a state $x$ with $x_i = 0$ to be in $\bar{A}_j$ all remaining $d$ states of $\bar{A}_j$ must be zero leading to $\mathrm{Pr}(\bar{A}_j^c) = 1 - \frac{1}{2^d}$ and

$$ \mathrm{Pr}(\bar{B}^c) = \left(1 - \frac{1}{2^d}\right)^d. \quad (18) $$

In order to calculate $\mathrm{Pr}(A_i \cap B^c)$ we note that $\mathrm{Pr}(A_i \cap B^c) = \mathrm{Pr}(A_i) \mathrm{Pr}(B^c|A_i)$ and again use independence to obtain

$$ \mathrm{Pr}(\bar{B}^c|\bar{A}_i) = \prod_{j \in n(i)} \mathrm{Pr}(\bar{A}_j^c|\bar{A}_i). \quad (19) $$

Note that $\mathrm{Pr}(\bar{A}_j|\bar{A}_i) = 1/2^{d-1}$ so that $\mathrm{Pr}(\bar{A}_j^c|\bar{A}_i) = 1 - \mathrm{Pr}(\bar{A}_j|\bar{A}_i) = 1 - 1/2^{d-1}$ which substituted into (19) gives

$$ \mathrm{Pr}(\bar{B}^c|\bar{A}_i) = \left(1 - \frac{1}{2^{d-1}}\right)^d. $$

Noting that $\mathrm{Pr}(\bar{A}_i) = 1/2^d$ we obtain the third term in (15), finishing the proof.

# 6 Square Lattices

In this section we consider graphs with type-4 edges or girth 4. Here the 1-neighborhoods $n[j]$ (with $j \ne i$) may intersect, the key aspect we want to address here. As an example, the reader may verify that for threshold-2 functions
and Circle$_4$, the activity of any vertex is 3/4 and not 7/8 as when $n \ge 5$ in Proposition 4.

As a specific case, take as graph $X$ a regular, square 2-dimensional lattice. It may be either infinite or with periodic boundary conditions. In the latter case, we assume for simplicity that its two dimensions are at least 5. This graph differs from the 4-regular tree by introduction of type-4 edges: sets $A_j$ and $A_{j+1}$ of $A_i$, when conditioned on the state of vertex $i$, are no longer independent. The graph has cycles of size 4 containing $i$. We illustrate this case using nor-functions as these allow for a somewhat simplified evaluation. We discuss more general cases and girth-3 graphs in the Summary section.

<figure><img src="image_4.png" /><figcaption>**Fig. 3.** The subgraph of a torus that includes $X(i; 2)$ at center. The subgraphs $S_l$, each containing the vertices associated to an $A_l$, $l \in \{1, 2, 3, 4\}$, are also shown separated from the center torus, with “center” vertex $j_\ell$. The overlapping or common vertices, $\beta_\ell$, are also denoted. We have vectors $\beta = (\beta_1, \beta_2, \beta_3, \beta_4)$ and $\hat{x}_j = (x_{j_1}, x_{j_2}, x_{j_3}, x_{j_4})$, where $x_{j_\ell}$ is the state of the “center” vertex $j_\ell$ of $A_\ell$, and where $\beta_\ell$ is a common vertex in $A_\ell$ and $A_{\ell+1}$ ($\ell$ is always modulo 4).</figcaption></figure>

**Proposition 10.** Let $X$ be the 2-dimensional lattice as above where every vertex has degree 4, and let $F$ be the GDS map over $X$ induced by nor-functions. Then the activity of $F$ for any vertex $i$ is $\bar{\alpha}_{F,i} = 1040/2^{12}$.

*Proof.* The neighborhoods of $i$ involved are illustrated in Figure 3. We rewrite (8) as follows

$$ \mathrm{Pr} \left( \bigcup_{j \in n[i]} A_j \right) = \mathrm{Pr}(B) + \mathrm{Pr}(A_i) (1 - \mathrm{Pr}(B|A_i)) . \quad (20) $$
To determine $|B|$, refer to Figure 3. With indices $p, q, r, s \in \{1, 2, 3, 4\}$ we have

$$|A_1 \cup A_2 \cup A_3 \cup A_4| = \sum_{p=1}^{4} A_p - \sum_{p<q} |A_p \cap A_q| + \sum_{p<q<r} |A_p \cap A_q \cap A_r| \\ - \sum_{p<q<r<s} |A_p \cap A_q \cap A_r \cap A_s|, \qquad (21)$$

which, along with Equation (20), is also valid if we condition on $x_i = 0$ in every set. We take $i \neq j_\ell$ with $\ell \in \{1, 2, 3, 4\}$ and let $j_\ell$ denote the vertex at the center of $n[j_\ell]$ and $i$ the vertex at the center of $n[i]$. Here $|X(i; 2)| = 13$. Using the symmetry of the sets $\bar{A}_{j_\ell}$ and the fact that a state $x$ is in the set $\bar{A}_{j_\ell}$ precisely when $x[j_\ell] = 0$ leads to

$$\sum_{\ell=1}^{4} |\bar{A}_{j_\ell}| = 4 \cdot 2^8.$$

For the second term on the right in (21) we have two cases for intersections: (i) two adjacent vertices $j_\ell, j_{\ell+1} \in n'[i]$ with all indices modulo 4, of which there are four instances, and (ii) two non-adjacent vertices $j_\ell, j_{\ell+2} \in n'[i]$, of which there are two instances. In the first case we obtain $|\bar{A}_{j_\ell} \cap \bar{A}_{j_{\ell+1}}| = 2^5$, while in the second case we have $|\bar{A}_{j_\ell} \cap \bar{A}_{j_{\ell+2}}| = 2^4$, making the second term on the right in (21)

$$\sum_{p<q} |\bar{A}_{j_p} \cap \bar{A}_{j_q}| = 4 \cdot 2^5 + 2 \cdot 2^4. \qquad (22)$$

The third sum appearing on the right in (21) contains four terms all corresponding to an intersection of three sets $A_{j_\ell}$, and we obtain

$$\sum_{p<q<r} |\bar{A}_{j_p} \cap \bar{A}_{j_q} \cap \bar{A}_{j_r}| = 4 \cdot 2^2. \qquad (23)$$

Finally, the intersection of all four sets $\bar{A}_{j_\ell}$ has size 1, and we get

$$\mathrm{Pr}(\bar{B}) = |\bar{B}|/2^{12} = [4 \cdot 2^8 - (4 \cdot 2^5 + 2 \cdot 2^4) + 4 \cdot 2^2 - 1]/2^{12}. \qquad (24)$$

We next determine $\mathrm{Pr}(B|A_i)$. For a state $x$ to be in $A_i$ we must have $x[i] = 0$ so that $|A_i| = 2^8$. Conditioning on this, we can calculate $|\bigcup_{\ell=1}^4 A'_{j_\ell}|$ as above. The reader can verify that

$$\sum_{\ell=1}^{4} |A'_{j_\ell}| = 4 \cdot 2^5, \\ \sum_{p<q} |A'_{j_p} \cap A'_{j_q}| = 4 \cdot 2^3 + 2 \cdot 2^2, \qquad (25)$$

$$\sum_{p<q<r} |A'_{j_p} \cap A'_{j_q} \cap A'_{j_r}| = 4 \cdot 2, \\ |A'_{j_1} \cap A'_{j_2} \cap A'_{j_3} \cap A'_{j_4}| = 1,$$
leading to the expression

$$ \mathrm{Pr}(\bar{A}_i \cap \bar{B}^c) = \mathrm{Pr}(\bar{A}_i) (1 - \mathrm{Pr}(\bar{B}|\bar{A}_i)) = \frac{1}{2^4} \left(1 - \frac{1}{2^8} [2^7 - 2^5 - 2^3 + 2^3 - 1]\right), $$

which, together with (24) in (20) gives the stated result of $\bar{\alpha}_{F,i} = 1040/2^{12}$.

# 7 Summary and Research Directions

We have introduced an extension of the notion of activity proposed by Shmulevich and Kauffman [19]. This extension takes into account the impact of the network structure when studying $E[\mathbb{I}[F(x) \neq F(x + e_i)]]$, which estimates how likely the perturbation $e_i$ will cause successor states to diverge. Naturally, orbits that initially separate may later converge. Nonetheless, this notion of activity provides a measure for sensitivity with respect to initial conditions.

Possibly interesting avenues for further work includes studying asynchronous systems. If the vertex functions are applied sequentially according to for example a permutation update sequence, are there effective ways of relating activity and the permutation? If so, are there principles connecting network structure and update sequence that allows one to minimize or maximize the activity of one or more vertices?

Square grids have type-4 edges and cycles of length 4 involving the vertex $i$. If we permit more general graphs with type-3 edges we naturally obtain cycles of length 3 containing $i$. The notion of cluster coefficient quantifies the number of triangles incident to $i$. Is it possible to relate activity and cluster coefficient? Of course, cluster coefficient is solely a graph property and includes nothing about vertex functions. Can one still find such a relation for a specific choice of vertex functions?

Finally, we considered arbitrary initial states $x \in K^n$. What can be said about activity if we restrict $x$ to be a periodic point? We invite the reader to explore this – some initial results on attractor activity are given in [11].

# Acknowledgments

We thank our external collaborators and members of the Network Dynamics and Simulation Science Laboratory (NDSSL) for their suggestions and comments. This work has been partially supported by DTRA Grant HDTRA1-11-1-0016.

# References

1. Adiga, A., Kuhlman, C., Mortveit, H.S., Vullikanti, A.K.S.: Sensitivity of diffusion dynamics to network uncertainty. In: Twenty-Seventh AAAI Conference on Artificial Intelligence (2013)
2. Aldana, M., Coppersmith, S., Kadanoff, L.P.: Boolean dynamics with random couplings. In: Perspectives and Problems in Nolinear Science, pp. 23–89. Springer (2003)

3. Baetens, J.M., Van der Weeën, P., De Baets, B.: Effect of asynchronous updating on the stability of cellular automata. Chaos, Solitons & Fractals 45, 383–394 (2012)

4. Baetens, J.M., De Baets, B.: Phenomenological study of irregular cellular automata based on lyapunov exponents and jacobians. Chaos 20, 1–15 (2010)

5. Derrida, B., Pomeau, Y.: Random networks of automata: A simple annealed approximation. Europhysics Letters 1, 45–49 (1986)

6. Fretter, C., Szejka, A., Drossel, B.: Perturbation propagation in random and evolved boolean networks. New Journal of Physics 11, 1–13 (2009)

7. Ghanbarnejad, F., Klemm, K.: Impact of individual nodes in boolean network dynamics. EPL (Europhysics Letters) 99(5), 58006 (2012)

8. Goles, E., Martinez, S.: Neural and Automata Networks: Dynamical Behaviour and Applications. Kluwer Academic Publishers (1990)

9. Kauffman, S.A.: Metabolic stability and epigenesis in randomly constructed genetic nets. Journal of Theoretical Biology 22, 437–467 (1969)

10. Kauffman, S.A.: The origins of order: Self-organization and selection in evolution. Oxford university press (1993)

11. Kuhlman, C.J., Mortveit, H.S.: Attractor stability in nonuniform boolean networks (2014), in press. Published online 23 August, 2014. Special volume of TCS: Non-uniform Cellular Automata

12. Layne, L., Dimitrova, E., Matthew, M.: Nested canalyzing depth and network stability. Bulletin of Mathematical Biology 74 (2012)

13. Luo, J.X., Turner, M.S.: Evolving sensitivity balances boolean networks. PLoS One 7, e36010 (2012)

14. Mortveit, H.S., Reidys, C.M.: An Introduction to Sequential Dynamical Systems. Universitext, Springer Verlag (2007)

15. Pomerance, A., Ott, E., Girvan, M., Losert, W.: The effect of network topology on the stability of discrete state models of genetic control. Proceedings of the National Academy of Sciences 106(20), 8209–8214 (2009)

16. Ribeiro, A.S., Kauffman, S.A.: Noisy attractors and ergodic sets in models of gene regulatory networks. Journal of Theoretical Biology 247, 743–755 (2007)

17. Robert, F.: Discrete Iterations. A Metric Study. No. 6 in Springer Series in Computational Mathematics, Springer-Verlag (1986)

18. Serra, R., Villani, M., Barbieri, A., Kauffman, S., Colacci, A.: On the dynamics of random boolean networks subject to noise: attractors, ergodic sets and cell types. Journal of theoretical biology 265(2), 185–193 (2010)

19. Shmulevich, I., Kauffman, S.A.: Activities and sensitivities in Boolean network models. Physical Review Letters 93(4), 048701:1–4 (2004)

20. Shmulevich, I., Lähdesmäki, H., Dougherty, E.R., Astola, J., Zhang, W.: The role of certain post classes in boolean network models of genetic networks. Proceedings of the National Academy of Sciences 100(19), 10734–10739 (2003)

21. Xiao, Y., Dougherty, E.R.: The impact of function perturbations in boolean networks. Bioinformatics 23(10), 1265–1273 (2007)