1. Introduction

Biological networks such as gene regulatory networks, neural networks, and metabolic networks are generally complex even from the network topology point of view ^[17,18]. However, the understanding of the dynamics of such network systems is crucial to identify mechanisms behind many kinds of biological processes and diseases, and to decode the mysteries of life. Statistical studies on the topology of real world networks revealed some very intriguing features ^[17] including power-law degree distributions ^[3,25,35], local community structures ^[4,11,13] and network motifs ^[6,14]. A community is defined to be a subnetwork within which the number of edges is much larger than the expected number in an equivalent network with edges placed at random ^[17]. On the other hand, a network motif is defined as a subnetwork that occurs more often in a complex network than in random networks. The discoveries of community structures and network motifs lead us to wonder about the possibility of using modular idea to study dynamics of network systems: the dynamics of a complex network can be understood by studying its subnetwork systems. In order for this idea to work, the dynamics of the subnetworks needs to be preserved or partially preserved in the original network. A simple example where this is true is when a subnetwork does not receive any input from the rest of the network. However, the situation becomes quite subtle when the subnetwork and its complementary subnetwork have mutual interactions.

There is a large body of work devoted to identifying communities or motifs in biological networks ^{[6,14,17,18,22,23,34]}. Interestingly, very few works focus on the relations between the dynamics of subnetworks and that of the whole system. In this work, we address the issue based on the Boolean network framework.

Mathematical models have proven to be indispensable tools for studying network systems. Among various mathematical modeling frameworks, coupled differential equations and Boolean networks are popular for modeling regulatory networks ^{[1,2,5,7,10,12,15,16,20,21,26,28,29,30,31,33]}. Network systems are often represented by directed graphs, wherein components are represented by nodes and interactions by arrows. An $n$-node Boolean network system is a discrete dynamical system with the form of

$X(t+1) = F(X(t))$

(1.1)

where $X = (x_1, \cdots, x_n)$ and $x_i$ represents the state variable of the $i^{th}$ node, $F =(f_1, \cdots, f_n)$ and $f_i$ is the governing function of the $i^{th}$ node with its value being either 0 or 1. They can be set up %can be set up in situations where information on the detailed kinetic interactions is not available and can provide many valuable insights ^{[8,9,12,19,24,27,32]}.

In this work, we particularly consider networks formed by two subnetworks connected at a cutting node, which we will define next. A node is called a cutting node of a connected network if the removal of the node leads to two or more disjoint subnetworks. We introduce the notion of a network being agreeable. Let $G$ be the network of the whole system formed by $G_1$ and $G_2$ connected at a cutting node $c$. Let $x_c(t, *)$ be the value of the cutting node in the system * (here * can be $G_1$, $G$, or $G_2$) at time $t$. We say that $G$ is agreeable if $x_c(t, G) =z_0$ whenever $x_c(t, G_1) = x_c(t, G_2) = z_0$. We first show that if a network is agreeable and its subnetworks have only cycles, then the whole system has only cycles. We then prove that if $X_0$ is a fixed point of $G$, then $X_0$ restricted to the phase-space of one of the subnetwork systems must be a fixed point of that system. In addition, we discuss the relations between the product of the transition diagrams (a representation of trajectories) of the subnetwork systems and that of the whole system.

The paper is structured as follows: In Section 2, we introduce terminology related to Boolean network systems and prove a property of such network systems. Section 3 defines agreeable networks and gives an example of updating scheme for the cutting node that guarantees a network system to be agreeable. In Section 4, we prove results on the relations between cycles and fixed points of whole network system and its subnetworks. In Section 5, we discuss the relations between the transition diagram of a network system and the product diagram of its subnetworks. Finally, in Section 6, we introduce an algorithm to construct the transition diagram of the whole network from the transition diagram of the product system.

---

2. Boolean network systems

In this section, we will introduce several basic terminologies for Boolean network systems and give a general property (Proposition 2.1) for deterministic Boolean network systems. We use the standard gene regulatory network topological representation for a Boolean network -the species are represented by nodes and interactions between species by arrows. We also allow two types of arrows from the tail node to the head node: one representing activation ($\to$) and the other representing inhibition ($\dashv$). For example, in Fig. 1(a) the inhibition from node 2 to node 1 is represented by an arrow $\dashv$ from node 2 to node 1.

The dynamics of a Boolean network system can be represented by a transition diagram, which we represent by $X_0 \to X_1$ if $F(X_0) = X_1,$ where $F$ is a Boolean map. For example, suppose the Boolean map associated to the network in Fig. 1(a) is as shown in the table in Fig. 1. In that case, the state $(0, 0)$ transits to $(1, 0)$, (1, 0) to (1, 1) and so on. So, the transition diagram of the system can be set up as the one in Fig. 1(c). If $X_0 \to X_1$ occur in the transition diagram, we say that $X_0 \to X_1$ is a transition of the network system.

The trajectory of a given state $X_0$ is defined to be the sequence $\{F^n(X_0)\}_{n=0}^{\infty}$. $X_0$ is called a fixed point if $F(X_0) = X_0$ and a trajectory of $X_0$ is called a cycle with length $n>0$ if $F^{k+n}(X_0) = F^k(X_0)$ for any nonnegative integer $k$ and $F^{k+m}(X_0) \neq F^k(X_0)$ for some $k$ if $m < n$. Finally, for a deterministic dynamical system, the trajectory of a given state is unique.

Proposition 2.1. The transition diagram of a given Boolean network system consists of a set of disjoint connected sub-diagrams, in which the trajectory of any state in the same connected sub-diagram ends at the same steady-state: either a fixed point or a cycle.

Proof. First note that there are only a finite number of states, the trajectory starting from any state will either end up in a cycle or a fixed point. Also note that for any two states, say $X_1$ and $X_2$, in the same connected sub-diagram, there must exist integers $n_1\geq 0$ and $n_2\geq 0$, so that $F^{n_1}(X_1) = F^{n_2}(X_2)$. The reason is as follows. Suppose the trajectories of $X_1$ and $X_2$ are in the same connected diagram. There then exists a state $X^*$ and two integers $m_1>0$, $m_2>0$, such that $X^*= F^{m_1}(X_1) = F^{m_1}(X_2)$.

Let $F^{n_1}(X_1)=F^{n_2}(X_2)=Y_0$. Since there are only a finite number of states, the trajectory starting from $Y_0$ will either end up in a cycle or a fixed point.

---

3. Agreeable networks

We first introduce the definition of an agreeable network system. Then we present an updating scheme for the cutting node that guarantees that the network $\mathcal{G}$ is agreeable. We would like to point out that there is no restriction on the updating schemes for the rest of the nodes in the network. Also note that the update scheme in this section is just an example. The results we present later on, except for the example in Section 6, are valid even if the scheme is not satisfied.

Let $\mathcal{G}$ be a network formed by two subnetworks $\mathcal{G}_1$ and $\mathcal{G}_2$, connected via a cutting node. For example, the network in Fig. 2 can be formed by two subnetworks in Fig. 3, which are connected at node 2. i.e. node 2 is a cutting node..

Let $c$ be the cutting node, $C_1$ be the set of the nodes in $\mathcal{G}_1 \backslash \{c\}$ and $C_2$ be the set of nodes in $\mathcal{G}_2 \backslash \{c\}$. Let $x$ be the state variables of $C_1$, $y$ be the state variables of $C_2$, $z$ be the state variable of $c$ in $\mathcal{G}_1$ and $\mathcal{z}$ be the state variable of $c$ in $\mathcal{G}_2$. Suppose the governing equations of $\mathcal{G}_1$ are

$\left\{ \begin{array}{lll} x(t+1) &=& h(x(t), z(t)) \\ &&\\ z(t+1) &=& g_1(x(t), z(t)) \end{array} \right.$

(3.1)

and those of $\mathcal{G}_2$ are

$\left\{ \begin{array}{lll} \mathcal{z}(t+1) &=& g_2(\mathcal{z}(t), y(t)) \\ &&\\ y(t+1) &=& f(\mathcal{z}(t), y(t)) \end{array} \right.$

(3.2)

Since node $c$ is the only node that connects the two subnetworks, the governing system of $\mathcal{G}$ can be written in the form of

$\left\{ \begin{array}{lll} x(t+1) &=& h(x(t), z(t)) \\ &&\\ z(t+1) &=& g(x(t), z(t), y(t)) \\ &&\\ y(t+1) &=& f(z(t), h(t)) \end{array} \right.$

(3.3)

Definition 3.1. The network system of $\mathcal{G}$ is agreeable if

$g_1( x, z) = g_2(z, y)\ \ \ \ \ \ \ \mbox{ implies } \ \ \ \ \ \ \ g(x, z, y) = g_1(x, z) = g_2(z, y)$

(3.4)

We will show next an updating scheme of the cutting node with which the network $\mathcal{G}$ is agreeable. We will refer to the updating scheme as Axioms.

Updating schemes that guarantee network $\mathcal{G}$ to be agreeable

1. The effects of activators and inhibitors are never additive, but rather, inhibitors are dominant;

2. The activity of a node will be 'on' in the next time step if at least one of its activators is 'on' and all inhibitors are 'off';

3. The activity of a node will be 'off' in the next time step if none of its activators are 'on'.

4. If a node has an external/background activation, then we assume that the node has an activator that is permanently 'on'.

Let $z$ be the state variable of the cutting node $c$. Define

$B(z) = \{ \mbox{Inhibitors in $\mathcal{G}_1$ that are on} \}$

$D(z) = \{ \mbox{Inhibitors in $\mathcal{G}_2$ that are on} \}$,

$A(z) = \{ \text{activators in $\mathcal{G}_1$ that are on} \}$,

$C(z) = \{ \text{Activators in $\mathcal{G}_2$ that are on} \}$.

Suppose the updating scheme for the cutting node satisfies the Axioms. Then the first three axioms can be rewritten as

1. If at time $t$, $B(z) \cup D(z) \neq \emptyset$, then $z = 0$ at time $t+1$.

2. If at time $t$, $B(z) \cup D(z) = \emptyset$ and $A(z) \cup C(z) \neq \emptyset$, then $z = 1$ at time $t+1$

3. If $A(z) \cup C(z) = \emptyset$, then $z = 0$ at time $t+1$.

Theorem 3.2. Suppose the updating scheme for the cutting node $c$ follows Axioms, then $\mathcal{G}$ is agreeable.

Proof. Suppose $g_1(z, x) = g_2(z, y) = z'$.

Case Ⅰ $z' = 0$. From $\mathcal{G}_1$ system, $B(z) \neq \emptyset$ or $A(z) = \emptyset$; From $\mathcal{G}_2$ system $D(z) \neq \emptyset$ or $C(z) = \emptyset$. This implies that

$B(z) \cup D(z) \neq \emptyset \mbox{ or } A(z) \cup C(z) = \emptyset$

Following the system of $\mathcal{G}$, $g(x, z, y) = 0$. So $g_1(z, y) = g_2(z, y) = g(x, z, y)$.

Case Ⅰ $z' = 1$. From $\mathcal{G}_1$ system, $B(z) = \emptyset$ and $A(z) \neq \emptyset$; From $\mathcal{G}_2$ system $D(z) = \emptyset$ and $C(z) \neq \emptyset$. This implies that

$B(z) \cup D(z) = \emptyset \mbox{ and }A(z) \cup C(z) \neq \emptyset$

Following the system of $\mathcal{G}$, $g(x, z, y) = 1$. So $g_1(z, x) = g_2(z, y) = g(x, z, y)$. Therefore $\mathcal{G}$ is agreeable.

Remark 3.3. The system of $\mathcal{G}$ is not agreeable any more if $g(x, z, y) = 1$ only when both $x = y = 1$. That is, when the activation of the cutting node requires inputs from both subnetworks, $\mathcal{G}$ is not agreeable. Similarly, when deactivation of the cutting node requires inputs from both subnetworks, $\mathcal{G}$ is also not agreeable. So the condition agreeable means the requirement on certain independency of the subnetworks.

---

4. Relations between Dynamics of $\mathcal{G}$ and its subnetworks

In this section, we present our results on the relations between fixed points and cycles of the network system of $\mathcal{G}$ and those of its subnetwork systems $\mathcal{G}_1$ and $\mathcal{G}_2$. We prove that if the subnetwork systems have only cycles, then the whole system also has only cycles; on the other hand, if the whole network system has a fixed point, then the projection of the fixed point to the phase space of one of the subnetwork systems is a fixed point of that network systems. In addition, we show an example that the subnetwork systems have only fixed point(s) while the whole system has a cycle.

We assume throughout this section that the systems associated to $\mathcal{G}_1$, $\mathcal{G}_2$ and $\mathcal{G}$ are (3.1), (3.2) and (3.3) respectively.

Theorem 4.1. Suppose the system of $\mathcal{G}$ is agreeable, and suppose both subnetwork systems, $\mathcal{G}_1$ and $\mathcal{G}_2$, have only cycles, then $\mathcal{G}$ system also has only cycles.

Proof. Let the associated system of $\mathcal{G}_1$, $\mathcal{G}_2$ and $\mathcal{G}$ be of the form of equations (3.1), (3.2) and (3.3) respectively. Then we only need to prove that

$\left(h(x, z), g(x, z, y), f(z, y) \right) \neq (x, z, y)$

(4.1)

for any state $(x, z, y)$ since any synchronous Boolean system has only a finite number of states, any state will repeat itself in a finite number of steps.

Let $(x_0, z_0, y_0)$ be an initial state. First we show that

$\left(h(x_0, z_0), g(x_0, z_0, y_0), f(z_0, y_0) \right) \neq (x_0, z_0, y_0)$

(4.2)

Note that if $\left(h(x_0, z_0), g(x_0, z_0, y_0), f(z_0, y_0) \right) = (x_1, 1-z_0, y_1)$, then we are done. Otherwise, if $\left(h(x_0, z_0), g(x_0, z_0, y_0), f(z_0, y_0) \right) = (x_1, z_0, y_1)$, we claim that either $x_1 \neq x_0$ or $y_1 \neq y_0$. We can show this by using contradiction. Suppose $x_1 = x_0$ and $y_1 = y_0$. i.e. $h(x_0, z_0) = x_1 = x_0$ and $f(z_0, y_0) = y_1 = y_0$. Then, because the subnetwork systems $\mathcal{G}_1$ and $\mathcal{G}_2$ have only cycles, we have

$(h(x_0, z_0), g_1(x_0, z_0) ) = (x_0, 1-z_0)$

and

$(g_2(z_0, y_0), f(z_0, y_0) = (1-z_0, y_0)$

By the condition $\mathcal{G}$ being agreeable, $\left(h(x_0, z_0), g(x_0, z_0, y_0), f(z_0, y_0) \right) = (x_0, 1-z_0, y_0)$ which contradicts with the assumption $G(x_0, z_0, y_0) = (x_1, z_0, y_1)$. Hence, either $x_1 \neq x_0$ or $y_1 \neq y_0$. Therefore, $\left(h(x_0, z_0), g(x_0, z_0, y_0), f(z_0, y_0) \right) \neq (x_0, z_0, y_0)$. It follows that the system of $\mathcal{G}$ has no fixed point. i.e. it only has cycles.

Corollary 4.2. Suppose the network system of $\mathcal{G}$ is agreeable. If the system of $\mathcal{G}$ has a fixed point, then $\mathcal{G}_1$ or $\mathcal{G}_2$ must have a fixed point.

Proof. This Corollary follows directly from Theorem 4.1.

Corollary 4.3. Suppose the network system of $\mathcal{G}$ is agreeable.

1. If the system of $\mathcal{G}_1$ and $\mathcal{G}_2$ have fixed points $(x_0, z_0)$ and $(z_0, y_0)$ respectively, then $(x_0, z_0, y_0)$ is a fixed point of $\mathcal{G}$.

2. If $(x_0, y_0, z_0)$ is a fixed point of the system of $\mathcal{G}$, then either $(x_0, y_0)$ is a fixed point of the system of $\mathcal{G}_1$ or $(y_0, z_0)$ is a fixed point of the system of $\mathcal{G}_2$.

Proof. 1. By Theorem 3.2, $z_0=g_1(x_0, z_0) = g_2(z_0, y_0)$ implies $g(x_0, z_0, y_0)=z_0$. Also because $(x_0, z_0)$ and $(z_0, y_0)$ are the fixed points of $\mathcal{G}_1$ and $\mathcal{G}_2$, $f(x_0, z_0) = x_0$ and $h(z_0, y_0) = y_0$. Therefore, $(x, z, y)$ is a fixed point of $\mathcal{G}$.

2. If $(x_0, y_0, z_0)$ is a fixed point of the system of $\mathcal{G}$, then $g(x_0, z_0, y_0)=z_0$. Note that $g_1(x_0, z_0) = z_0$ or $1-z_0$ and $g_2(z_0, y_0)= z_0$ or $1-z_0$. Because the system $\mathcal{G}$ is agreeable, either $g_1(x_0, z_0) = z_0$ or $g_2(z_0, y_0)= z_0$.

Corollary 4.3 implies that when $\mathcal{G}$ is agreeable, the fixed points of whole network system can be obtained by first looking at the fixed points of the subnetwork systems.

Next, we show an example that both subnetwork systems have only fixed points while the whole network system has cycles. We consider the network in Fig. 4. Suppose the associate Boolean system satisfies the Axioms. Then a straightforward calculation shows that the system of network in Fig. 4 has a cycle $(010) \to (011) \to (111) \to (110) \to (010)$ while its two subnetwork systems shown in Fig. 5 have only fixed points.

---

5. Relations between transition diagrams

In a Boolean network system, the transition diagram of the system represents the trajectory space of the discrete dynamical system. That is, the transition diagram represents the dynamics of the system. Note that if the dynamics of the subnetworks are all independent, then the dynamics of the whole network is just the product of the subnetworks. However, when they are not independent, the relation is not all that transparent. In this section, we explore the relations between the transition diagrams of a network system and its subnetwork systems.

Product network systems

Let the associated systems of $\mathcal{G}_1$ and $\mathcal{G}_2$ be of the form of (3.1) and (3.2) respectively. Then the associated system of the product network $\mathcal{G}_1 \times \mathcal{G}_2$ is defined to be

$\left\{ \begin{array}{lll} x(t+1) &=& h(x(t), z(t)) \\ z(t+1) &=& g_1(x(t), z(t))\\ \mathcal{z}(t+1) &=& g_2(\mathcal{z}(t), y(t)) \\ y(t+1)) &=& f(\mathcal{z}(t), y(t)) \end{array}\right.$

(5.1)

That is, if $(x_0, z_0)\to (x_1, z_1)$ is a transition of the system of $\mathcal{G}_1$ and $(\mathcal{z}_0, y_0)\to (\mathcal{z}_1, y_1)$ is a transition of the system of $\mathcal{G}_2$, then $(x_0, z_0, \mathcal{z}_0, y_0) \to (x_1, z_1, \mathcal{z}_1, y_1)$ is a transition of the system of $\mathcal{G}_1 \times \mathcal{G}_2$. This can be represented by the diagram in Fig. 6, where peach-colored arrows represent transitions occurring in $\mathcal{G}_2$ system, green arrows represent transitions occurring in $\mathcal{G}_1$ system, and the blue arrow is the transition occurring in the product system.

It is obvious that the phase space of the system of $\mathcal{G}$ can be embedded in the phase space of the system of $\mathcal{G}_1\times \mathcal{G}_2$ by the map $J: \{0, 1\}^3 \to \{0, 1\}^4$ defined by $J(x, z, y) = (x, z, z, y)$. In order to simplify this notation, we identify point $(x, z, y)$ in the phase space of $\mathcal{G}$ with the point $(x, z, z, y)$ in the phase space of $\mathcal{G}_1 \times \mathcal{G}_2$. Now the question is: Does a transition such as $(x_0, z_0, z_0, y_0) \to (x_1, z_1, z_1, y_1)$ in the system of $\mathcal{G}_1\times \mathcal{G}_2$ imply a transition of $(x_0, z_0, y_0) \to (x_1, z_1, y_1)$ in the system of $\mathcal{G}$? The answer is yes provided $\mathcal{G}$ is agreeable.

Proposition 5.1. Suppose the network system of $\mathcal{G}$ is agreeable. Then, a transition in the system of the product network $\mathcal{G}_1 \times \mathcal{G}_2$ of the form $(x_0, z_0, z_0, y_0) \to (x_1, z_1, z_1, y_1)$ implies a transition $(x_0, z_0, y_0) \to (x_1, z_1, y_1)$ in the network system $\mathcal{G}$.

Proof. By definition of product system, saying that $(x_0, z_0, z_0, y_0) \to (x_1, z_1, z_1, y_1)$ is a transition of the system of the product network $\mathcal{G}_1 \times \mathcal{G}_2$ means that $f(x_0, z_0) = x_1$, $g_1(x_0, z_0) = z_1$, $g_2(z_0, y_0) = z_1$ and $g(z_0, y_0) = y_1$. Because $\mathcal{G}$ is agreeable, $g(x_0, z_0, y_0) = z_1$. Hence, $(x_0, z_0, y_0) \to (x_1, z_1, y_1)$ is a transition of the network system $\mathcal{G}$

We would like to point out that the reverse of Proposition 5.1 does not hold. That is, $(x_0, z_0, y_0) \to (x_1, z_1, y_1)$ in the system of $\mathcal{G}$ does not imply $(x_0, z_0, z_0, y_0) \to (x_1, z_1, z_1, y_1)$ of the product system. More precisely, there exists a transition such as $(x_0, z_0, z_0, y_0) \to (x_1, z_1, \mathcal{z}_1, y_1)$ with $z_1\neq \mathcal{z}_1$. We will see this in the example introduced in the next section.

Relation between transition diagrams

Next we will study relations between the transition diagram of $\mathcal{G}$ and that of the product system of its subnetworks. We achieve this goal by exploring the possibility of constructing the transition diagram of $\mathcal{G}$ from a product system.

Proposition 5.1 tells us that we can derive some transitions of $\mathcal{G}$ by simply translating $(x_0, z_0, z_0, y_0) \to (x_1, z_1, z_1, y_1)$ in the system of of $\mathcal{G}_1\times \mathcal{G}_2$ to $(x_0, z_0, y_0) \to (x_1, z_1, y_1)$ in the system of $\mathcal{G}$. As pointed out earlier, there exists transition such as $(x_0, z_0, z_0, y_0) \to (x_1, z_1, \mathcal{z}_1, y_1)$ with $z_1\neq \mathcal{z}_1$. In this case, we can not derive to which state $(x_0, z_0, y_0)$ transits to based on the information of the product space. However, by the definition of the product system, it is certain that $(x_0, z_0, y_0)$ transits to $(x_1, z, y_1)$ where $x_1$ and $y_1$ can be read off from the transition $(x_0, z_0, z_0, y_0) \to (x_1, z_1, \mathcal{z}_1, y_1)$ while the value of $z$ needs to be determined by $g$ evaluated at $(x_0, z_0, y_0)$.

Proposition 5.2. If $(x_0, z_0, z_0, y_0) \to (x_1, z_1, \mathcal{z}_1, y_1)$ with $z_1\neq \mathcal{z}_1$ is a transition of the product system $\mathcal{G}_1\times \mathcal{G}_2$, then $(x_0, z_0, y_0) \to (x_0, 0, y_0)$ or $(x_0, z_0, y_0) \to (x_0, 1, y_0)$ is a transition of the system of $\mathcal{G}$.

Proof. By the definition of the product system (5.1), $(x_0, z_0, z_0, y_0) \to (x_1, z_1, \mathcal{z}_1, y_1)$ means $h(x_0, z_0) = x_1$, $g_1(x_0, z_0) = z_1$, $g_2(z_0, y_0) = \mathcal{z}_1$ and $f(z_0, y_0) = y_1$. Following the definition of the system of $\mathcal{G}$ (system (3.3)), $(x_0, z_0, y_0)$ transits to $(h(x_0, z_0), g(x_0, z_0, y_0), f(z_0, y_0)) = (x_1, g(x_0, z_0, y_0), y_1)$. Since $g$ is a Boolean function, $g(x_0, z_0, y_0) = 0$ or $g(x_0, z_0, y_0)=1$. i.e. $(x_0, z_0, y_0) \to (x_0, 0, y_0)$ or $(x_0, z_0, y_0) \to (x_0, 1, y_0)$.

---

6. Construct transition diagram from that of sub-networks

In this section, by using an example, we discuss the construction of the transition diagram of a network $\mathcal{G}$ from the transition diagram of the product system of its subnetworks $\mathcal{G}_1$ and $\mathcal{G}_2$.

Example. Consider the network in Fig. 2 that is formed by the two subnetworks in Fig. 3. Suppose the updating scheme for all the nodes in the networks follow Axioms. Then, the transition diagrams of the subnetworks in Fig. 3(a), (b) are shown in the Fig. 7(a), (b), respectively.

The product of the transition diagrams in Fig. 7 is shown in Fig. 8 (left). By the definition of product network systems, the state $(0, 0, 0, 0)$ transits to $(1, 0, 0, 1)$ since $h(0, 0) = 1$, $g_1(0, 0) = 0$, $g_2(0, 0) = 0$ and $f(0, 0) = 1$; the state $(1, 0, 0, 1)$ transit to $(1, 1, 1, 1)$ since $h(1, 0) = 1$, $g_1(1, 0) = 1$, $g_2(1, 0) = 1$ and $f(1, 0) = 1$ and so on. As a result, we can get the transition diagram of the product network system as represented by the diagram with blue arrows on the right of Fig. 8.

Next we show how we can construct the transition diagram of the original three-node network system based on the transition diagram of the product system. Since the phase space of a three-node network system can be embedded in the phase space of the product system by the map $J$, we colored those states of the form $(x, z, z, y)$ in red and removed all arrows that are not from those nodes as shown in Fig. 10(left). We then identify states $(x, z, y)$ of the three-node system with states $(x, z, z, y)$ of the product network system and consider where each state in red transits in the system of three-node network system. By Proposition 5.1, $(x_0, z_0, z_0, y_0) \to (x_1, z_1, z_1, y_1)$ implies a transition $(x_0, z_0, y_0) \to (x_1, z_1, y_1)$. That means the transitions in blue in Fig. 10(right) are part of the transitions of the three-node network system. Next we need to determine transitions for remaining red states. The state $(1000)$ transit to $(1101)$ in the product network, see Fig. 10(left). However, $(1101)$ is not a state of the three-node network system. On the other hand, the transition $(1000) \to (1101)$ in the product system implies $(100) \to (1z1)$ in the three-node system. i.e. $h(1, 0) = 1$, $g(1, 0, 0)=z$ and $f(0, 0) =1$ where $z$ needs to be determined by $g$. Since $g(1, 0, 0) = 1$, $(100)$ transit to $(111)$ in the three-node system. We mark a transition: $(1000)$ transit to (1111) in the product space. Similarly, we find $(0111)\to (0110)$, $(1110) \to(0110)$ and $(0001)\to (1111)$ as shown in Fig. 10(right).

Now we have found the transitions for all the red states. The diagram that consists of only the red nodes and the arrows is the transition diagram of the three-node system --which is identical to the transition diagram we obtained directly using the rule for the three-node network system (Fig. 2) as shown in Fig. 10(right).

Algorithm of constructing transition diagram. We summarize how to construct the transition diagram of the whole network from the product systems of its subnetworks as follows.

Suppose $\mathcal{G}$ is agreeable at the cutting node.

1. Let $\mathcal{T}_1$ be the set of all transitions of the system of $\mathcal{G}_1$ and expressed by

$\mathcal{T}_1 = \left\{ (x_0, z_0) \to (x_1, z_1) \left| \begin{array}{l} x_i \in \{0, 1\}^k, z_i \in \{0, 1\}, i = 0, 1 \\ h(x_0, z_0) = x_1, g_1(x_0, z_0) = z_1 \end{array}\right. \right\}$

and let $\mathcal{T}_2$ be the set of all transitions of the system of $\mathcal{G}_2$ and expressed by

$\mathcal{T}_2 = \left\{ (\mathcal{z}_0, y_0) \to (\mathcal{z}_1, y_1) \left| \begin{array}{l} y_i \in \{0, 1\}^m, \mathcal{z}_i \in \{0, 1\}, i = 0, 1 \\ g_2(\mathcal{z}_0, y_0) = \mathcal{z}_1, f(\mathcal{z}_0, y_0) = y_1 \end{array}\right. \right\}$

Then the set $\mathit{Q}$ of all transitions of the product system is

$\mathit{Q} = \left\{ (x_0, z_0, \mathcal{z}_0, y_0) \to (x_1, z_1, \mathcal{z}_1, y_1) \left| \begin{array}{l} x_i \in \{0, 1\}^k, z_i \in \{0, 1\}, y_i \in \{0, 1\}^m, \\ \mathcal{z}_i \in \{0, 1\}, i = 0, 1 \\ h(x_0, z_0) = x_1, g_1(x_0, z_0) = z_1 \\ g_2(\mathcal{z}_0, y_0) = \mathcal{z}_1, f(\mathcal{z}_0, y_0) = y_1 \end{array}\right. \right\}$

Set the set of all transition of the system of $\mathcal{G}$ be $\mathcal{T}$.

2. Find all the states of the form of $(x, z, z, y)$ and their transitions in the product system.

3. If $(x_0, z_0, z_0, y_0) \to (x_1, z_1, z_1, y_1) \in \mathit{Q}$, then add $(x_0, z_0, y_0) \to (x_1, z_1, y_1)$ to the set $\mathcal{T}$. If $(x_0, z_0, z_0, y_0) \to (x_1, z_1, \mathcal{z}_1, y_1) \in \mathit{Q}$ with $z_1 \neq \mathcal{z}_1$, then add $(x_0, z_0, y_0) \to (x_1, g(x_0, z_0, y_0), y_1)$ to $\mathcal{T}$.

Remark 6.1. The transitions on the diagonal of the product network are always transitions of the whole network.

Remark 6.2. The algorithm is rather straight forward. However, it can be very useful when the subnetworks are large and their transition diagrams are ready to use. Also note that even though we add the condition agreeable on the system of $\mathcal{G}$, we can easily modify it to the case that the condition fail. We just need to change the step 3 to If $(x_0, z_0, z_0, y_0) \to (x_1, z_1, \mathcal{z}_1, y_1) \in \mathit{Q}$, then add $(x_0, z_0, y_0) \to (x_1, g(x_0, z_0, y_0), y_1)$ to $\mathcal{T}$. On the other hand, the algorithm provide a rather clear view on the relations between the dynamics of the whole network and that of its subnetworks.

---

Acknowledgement

A few days before KC passed away, he discussed with YW about finishing this work in the summer of 2015. YW is grateful for KC's mentoring and his friendship, and will cherish the memory of him. YW was supported by DHS-14-ST-062-001.

---

Conflict of Interest

All authors declare no conflicts of interest in this paper.

---