# Structure-based control of complex networks with nonlinear dynamics

See allHide authors and affiliations

Edited by Herbert Levine, Rice University, Houston, TX, and approved May 30, 2017 (received for review October 23, 2016)

## Significance

Many biological, technological, and social systems can be encoded as networks over which nonlinear dynamical processes such as cell signaling, information transmission, or opinion spreading take place. Despite many advances in network science, we do not know to what extent the network architecture shapes our ability to control these nonlinear systems. Here we extend a recently developed control framework that addresses this question and apply it to real networks of diverse types. Our results highlight the crucial role of a network’s feedback structure in determining robust control strategies, provide a dynamic-detail-independent benchmark for other control methods, and open up a promising research direction in the control of complex networks with nonlinear dynamics.

## Abstract

What can we learn about controlling a system solely from its underlying network structure? Here we adapt a recently developed framework for control of networks governed by a broad class of nonlinear dynamics that includes the major dynamic models of biological, technological, and social processes. This feedback-based framework provides realizable node overrides that steer a system toward any of its natural long-term dynamic behaviors, regardless of the specific functional forms and system parameters. We use this framework on several real networks, identify the topological characteristics that underlie the predicted node overrides, and compare its predictions to those of structural controllability in control theory. Finally, we demonstrate this framework’s applicability in dynamic models of gene regulatory networks and identify nodes whose override is necessary for control in the general case but not in specific model instances.

Controlling the internal state of complex systems is of fundamental interest and enables applications in biological, technological, and social contexts. An informative abstraction of these systems is to represent the system’s elements as nodes and their interactions as edges of a network. Often asked questions related to control of a networked system are how difficult to control it is, and which network elements need to be controlled, and through which control actions, to drive the system toward a desired control objective (1⇓⇓⇓⇓⇓⇓⇓⇓⇓–11). Among control frameworks, structure-based methods distinguish themselves due to their ability to draw dynamical conclusions based solely on network structure and a general assumption about the type of allowed dynamics. For example, structural controllability (SC), which assumes unspecified linear dynamics or linearized nonlinear dynamics, allows the identification of the minimal number of nodes whose receiving an external signal

Despite its success and widespread application (14⇓⇓⇓–18), SC may give an incomplete view of the network control properties of a system. In the case of systems with nonlinear dynamics, it provides sufficient conditions to control the system in the neighborhood of a trajectory or a steady state (refs. 1 and 18 and *SI Appendix*), and its definition of control (full control; from any initial to any final state) does not always match the meaning of control in biological, technological, and social systems, in which control tends to involve only naturally occurring system states (19). In addition to the approaches provided by nonlinear control theory (9⇓–11, 18), new methods of network control have been proposed to incorporate the inherent nonlinear dynamics of real systems and relax the definition of full control (4, 6, 11, 18, 20). Only one of these methods, namely, feedback vertex set control (FC), can be reliably applied to large complex networks in which only the structure is well known and the functional form of the governing equations is not specified. This method, introduced by Mochizuki and coworkers in refs. 3 and 21, incorporates the nonlinearity of the dynamics and considers only the naturally occurring end states of the system (e.g., steady states and limit cycles) as desirable final states. In this work, we use FC on biological, technological, and social networks to predict the nodes whose override (by external control) can steer a network’s dynamics toward any of its natural long-term dynamic behaviors (its dynamical attractors). We identify the topological characteristics underlying the predicted node overrides, compare the obtained results with those of control theory’s SC (1, 12, 13), and identify the model-dependent and model-independent overrides it provides for network models with parameterized dynamics.

## Structure-Based Network Control with Nonlinear Dynamics

Most real systems are driven by nonlinear dynamics in which a decay term prevents the system’s variables from increasing without bounds. The state of the system’s *SI Appendix*). Functions of the form **1** and **2** that occurs on the specified network structure.)

The dynamics described by Eqs. **1** and **2** are such that they possess some naturally occurring end states, or dynamical attractors. Dynamical attractors in biological, social, and technological systems represented by networks have been found to be identifiable with the stable patterns of activity of the system. For example, in gene regulatory networks, dynamical attractors correspond to cell fates (27⇓–29); in opinion spreading dynamics on social networks, they correspond to opinion consensus states of groups of individuals (25); and, in disease or computer virus spreading, they correspond to the long-term (endemic) patterns of infected elements (24).

In many systems, there is adequate knowledge of the underlying wiring diagram but not of the specific functional forms and parameter values required to fully specify **1**, the control action of forcing (overriding) the state variables of the FVS into the trajectory specified by a given dynamical attractor of Eq. **1** ensures that the network will asymptotically approach the desired dynamical attractor, regardless of the specific form of the functions *SI Appendix*).] This type of intervention is often used in biological systems, with examples such as genome editing or pharmacological treatment (19, 32), and in epidemic spreading networks, where vaccination is a node state override that prevents a node from being infected. When using node state overrides as the control action, controlling the FVS is sufficient to drive the system to any of its attractors for each form of *SI Appendix*). The problem of exactly identifying the minimal FVS is nondeterministic polynomial-time hard (NP-hard), but a variety of fast algorithms exist to find close-to-minimal solutions (*SI Appendix*).

In the structural theory of Mochizuki and coworkers (3, 21), every element is governed by Eq. **1**. It is assumed that the source nodes converge to a unique state (or trajectory) and do not need independent control; thus they are iteratively removed from the network before applying FVS control. However, source nodes can denote external stimuli or boundary conditions the system is subject to; a different set of attractors may be available for each state of a source node. For example, in the parameterized biological models we consider, source nodes provide positional information for the cells and affect the patterning behaviors cells are capable of.

Here we adapt the structural theory of Mochizuki and coworkers (3, 21) to networks in which source nodes are governed by Eq. **2** (Fig. 1*A* and *SI Appendix*). Because the source nodes are unaffected by other nodes, one additionally needs to lock the source nodes of the network in the trajectory specified by the attractor. We emphasize that the treatment of source nodes is not merely cosmetic, because the state of a source node can affect the dynamical attractors available to the system. For example, steady states can merge, appear, or disappear depending on the presence or absence of an external stimulus represented by a source node (26, 33). In summary, control of the source nodes and of the FVS of a network guarantees that we can guide it from any initial state to any of its dynamical attractors (i.e., its natural long-term dynamic behaviors) regardless of the specific form of the functions. In the following, we refer to this attractor-based control method as FC (Fig. 1*A*), and to the group of nodes that need to be manipulated by FC as an FC node set.

To illustrate FC, consider the example networks in Fig. 1. In a linear chain of nodes (Fig. 1*B*, *Left*), the only node that needs to be controlled is the source node *C*, a source node connected to a cycle, FC requires controlling the source node *D* consists of a source node with three successor nodes, and FC requires controlling only the source node *E*, we show a more complicated network with a cycle and several source and sink nodes, and two minimal FC node sets. These examples illustrate an important feature of FC, namely, that it is determined by the cycle structure and the input layer of the network. *SI Appendix*, Fig. S1 illustrates FC in a network in which a specific form of the functions

## Feedback Vertex Set Control of Real Networks

We applied FC to several real networks and the ratio of the minimal FC node set, *SI Appendix*, Table S1 and Fig. 2*A*, where the FVS and source node contributions of

To understand the topological properties underlying the diversity of the fraction of control nodes

Applying this reasoning to the studied real networks (*SI Appendix*, Table S1), we expect the networks in which the fraction of nodes that are part of an SCC is high to have a large FVS contribution *B*, the networks show a strong correlation between the relative size of their SCCs (denoted by *SI Appendix*, Fig. S2*A*). For example, all of the networks with the largest FC node set size (*A* and *B*, pink shading; e.g., intraorganizational networks) have a large fraction of nodes in their SCCs (*A* and *B*, yellow shading; e.g., social communication networks, and most trust and WWW networks) have an intermediate *A* and *B*, green shading; e.g., food webs, circuits, and gene regulatory networks) have correspondingly small SCCs (

Motivated by the observed remarkable agreement between the number of control nodes of real networks and their degree-preserving randomized versions in SC (1, 36), we study FC in similarly randomized networks (*SI Appendix*, Table S1 and *SI Text*). We find much weaker agreement (Fig. 2*C*): For most networks, the number of FC nodes is higher than the number of control nodes in randomized versions (*C* and *F*). A closer look reveals that the cycle structure of the real networks—their cycles and SCCs—is responsible for the discrepancy of *E*), and reflected by the larger size of their FVS (*SI Appendix*, Table S1). The exceptions to this reasoning are food web and citation networks (Fig. 2*F*), which are known to have an acyclic (e.g., tree-like) or close-to-acyclic structure (37), and thus feature fewer cycles and fewer nodes in an SCC than randomized networks.

To verify that the cycle structure of real networks explains the observed FC node set size, we generated degree-preserving randomized versions of these networks that maintain their cycle structure, which we achieve by randomizing the directed acyclic part of the graph while keeping intact the SCCs (*SI Appendix*). The results show a remarkable agreement between the FC node set size of the networks and their randomized versions (Fig. 2*D* and *SI Appendix*, Table S1). Given that short cycles were found to correlate well with the discrepancy in FC node set size in real networks compared with randomized networks (*SI Appendix*, Table S1, and Fig. 2 *E* and *F*), we reasoned that preserving only the short-cycle structure of networks (in addition to their degree) might be sufficient to explain the FC node set size of real networks. To test this theory, we generated degree-preserving randomized versions of the networks that maintain their short-cycle structure (cycles of length 4 or less) (*SI Appendix*). *SI Appendix*, Fig. S2*B* and Table S1 show the resulting FC node set sizes, which have an excellent agreement with that of the real networks, the exceptions being the near-acyclic food web and citation networks, for which short cycles cannot capture their near-acyclic structure.

Taken together, these results show that the cycle structure of a network, specifically its SCCs and short cycles, determines the number of nodes that need to be overridden in FC.

## Comparing Feedback Vertex Set Control and Structural Controllability

An interesting result from applying FC on real networks is that biological networks are easier to control than social networks, yet this prediction stands in contrast with those of SC on the same type of networks, in which the opposite result was obtained (1). This contradicting prediction is somewhat surprising, because both methods can be used to answer the question of how difficult to control a network is based solely on network structure, albeit each focuses on a different aspect of control (full control vs. attractor control), considers different underlying dynamics (linear vs. nonlinear), and uses different control actions (controller signal vs. node state override). To test whether this significant difference in the predictions of FC and SC is common among other networks, we compare their fraction of control nodes *A* and *SI Appendix*, Table S1,

The difference in

To illustrate how the cycle structure influences the number of control nodes in FC and SC, consider the networks in Fig. 3*B*. The left-most network contains several cycles (green background) and requires more nodes to be manipulated in FC compared with SC (*B* has *SI Appendix*).

## Feedback Vertex Set Control and Dynamic Models of Real Systems

Validated dynamic models can be an excellent testing ground to assess control methods (4, 6, 8). Here we use two models for the gene regulatory network underlying the segmentation of the fruit fly (*Drosophila melanogaster*) during embryonic development: a differential equation (ODE) model by von Dassow et al. (28) (Fig. 4*A*) and a discrete (Boolean) model by Albert and Othmer (29) (Fig. 4*B*). Both models consider a group of four subsequent cells as a repeating unit, include intracellular and intercellular interactions among proteins and mRNAs, and recapitulate the observed (wild type) stable pattern of gene expression (Fig. 4 *A*–*C* and *SI Appendix*).

Using FC on these network models, we find *A*–*C* and *SI Appendix*, Fig. S3, and *SI Text*). Both model networks have a large SCC and, thus, a significant FVS contribution to the FC node set; *D* and *E* and *SI Appendix*, Figs. S4 and S5 and *SI Text*). Thus, FC gives a control intervention that is directly applicable to dynamic models and that is directly linked to their long-term behavior.

FC gives a sufficiency condition about the ensemble of all models with a given network structure, and, consequently, a subset of the FC node set can often be sufficient for a given model and an attractor of interest (i.e., FC provides an upper limit for the size of the control node set). For the fruit fly gene regulatory models, we show that 16 (12) nodes are sufficient for the continuous (discrete) model, which is a 66% (14%) reduction (Fig. 4 *A*–*C* and *SI Appendix*, Figs. S4 and S5 and *SI Text*). Similar results were obtained by ref. 21, who found that five nodes (out of seven in the FVS) are sufficient for attractor-based control in a model of the mammalian circadian rhythm. The generality of these findings is supported by a recently developed control method in which controlling a subset of the cycles (and thus a subset of the FVS) in Boolean dynamic models was proven to be sufficient for attractor control (ref. 6 and *SI Appendix*, *SI Text*). This finding shows that FC provides a benchmark of attractor control node sets that are model independent, as well as an upper limit to model-dependent control sets.

## Discussion

Network control methods have the general objective of identifying network elements that can drive a system toward a specified goal while satisfying a set of constraints. Different control methods answer complementary aspects of control in a complex network; which one to use depends on the specific question being asked, on the natural definition of control, and on the underlying dynamics in the system or discipline of interest. We argue that attractor-based control (and thus FC) is the appropriate choice of control for biological systems, for which a long history of dynamic modeling has established the correspondence of attractors with biological states of interest (27), but also in many social and technological contexts, as illustrated by opinion dynamics and the consensus state, and by epidemic processes and the endemic state (24, 25).

As we showed in this work, FC is directly applicable to systems in which only structural information is known, and also to systems in which a parameterized dynamic model is available, for which it provides realizable control strategies that are robust to changes in the parameters and functions. FC also provides a benchmark and a point of contact with the large body of work in network control methods that require the network structure and a dynamic model (4, 6, 8, 18, 20). The prescription of a directly realizable control action (even if a controller signal is not provided) has no analogue in control theory’s structure-based methods such as SC, wherein the existence of a controller signal is guaranteed but is yet to be determined. SC instead has the advantage of integrating controller signals into its framework, and being a well-developed concept in control and systems theory with connections to other notions of control in linear and nonlinear systems (9⇓–11). Further work is needed to extend FC and address topics such as the level of control provided by a subset of nodes, the task of building a controller signal that can implement the node state overrides, and the difficulty of steering the system toward a desired state, concepts that are well-developed in control theory (9⇓–11, 18). Taken together, our work opens up a research direction in the control of complex networks with nonlinear dynamics, connects the field of dynamic modeling with structure-based methodologies, and has promising theoretical and practical applications.

## Acknowledgments

We thank A. Mochizuki, Y.-C. Lai, and M. T. Angulo for helpful discussions, and Y. Y. Liu for his assistance and for providing us some of the networks in this study. We also thank the Mathematical Biosciences Institute (MBI) for the workshop “Control and Observability of Network Dynamics,” which greatly enriched this paper. This work was supported by National Science Foundation Grants PHY 1205840, 1545832, and IIS 1160995. J.G.T.Z. is a recipient of an SU2C-V Foundation Convergence Scholar Award.

## Footnotes

↵

^{1}Present address: Department of Medical Oncology, Dana–Farber Cancer Institute, Boston, MA 02215.↵

^{2}Present address: Cancer Program, Eli and Edythe L. Broad Institute of Harvard and Massachusetts Institute of Technology, Cambridge, MA 02142.- ↵
^{3}To whom correspondence should be addressed. Email: jgtz{at}phys.psu.edu.

Author contributions: J.G.T.Z. and R.A. designed research; J.G.T.Z. and G.Y. performed research; J.G.T.Z. and G.Y. contributed new reagents/analytic tools; J.G.T.Z., G.Y., and R.A. analyzed data; and J.G.T.Z., G.Y., and R.A. wrote the paper.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission.

This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1617387114/-/DCSupplemental.

## References

- ↵
- ↵
- ↵.
- Mochizuki A,
- Fiedler B,
- Kurosawa G,
- Saito D

- ↵
- ↵.
- Ruths J,
- Ruths D

- ↵
- ↵.
- Wang LZ, et al.

- ↵.
- Gates AJ,
- Rocha LM

- ↵.
- Slotine JJE,
- Li W

*Applied Nonlinear Control*(Prentice-Hall, Englewood Cliffs, NJ), Vol 199 No. 1. - ↵.
- Sontag ED

- ↵.
- Schättler H,
- Ledzewicz U

- ↵
- ↵.
- Shields RW,
- Pearson JB

- ↵.
- Vinayagam A, et al.

- ↵.
- Kawakami E, et al.

- ↵
- ↵
- ↵.
- Liu YY,
- Barabási AL

- ↵
- ↵.
- Murrugarra D,
- Dimitrova ES

- ↵.
- Fiedler B,
- Mochizuki A,
- Kurosawa G,
- Saito D

- ↵.
- Allen LJ

- ↵.
- Novozhilov AS,
- Karev GP,
- Koonin EV

- ↵.
- Daley DJ,
- Gani J,
- Gani JM

- ↵
- ↵
- ↵.
- Alon U

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵.
- Bassett DS,
- Alderson DL,
- Carlson JM

- ↵.
- Kramer AD,
- Guillory JE,
- Hancock JT

- ↵.
- Newman MEJ

- ↵.
- Maslov S,
- Sneppen K

- ↵

## Citation Manager Formats

## Article Classifications

- Physical Sciences
- Applied Physical Sciences

- Biological Sciences
- Systems Biology