SIAM News Blog
SIAM News
Print

Sensitive Dependence on Network Structure: Analog of Chaos and Opportunity for Control

By Adilson E. Motter and Takashi Nishikawa

The advancement of network science over the past 20 years has created the expectation that we will soon be able to systematically control the behavior of complex network systems and in turn address numerous outstanding scientific problems, from cell reprogramming and drug target identification to cascade control and self-healing infrastructure development [4]. This expectation is not without reason, given that control technologies have been part of human development for over 2,000 years [1].

While significant progress has been made, our current ability to control is still limited in many systems. This is not so much from lack of available technologies to actuate specific network elements as from challenges imposed by unique characteristics of large real networks to designing system-level control actions [4]. These limiting characteristics include the combination of high dimensionality, nonlinearity, and constraints on the interventions, which set networks apart from other systems to which control has been traditionally applied [1]. Recent progress on developing control techniques scalable to large networks has been driven by the design of new approaches.

One such approach may now be possible due to the recent discovery [5] that network dynamics often depends sensitively on the network structure, especially when this structure is optimized for maximum stability of a desired behavior. Before considering how this property can be explored to make networks more responsive to control, we discuss in some detail what sensitive dependence on the network structure really means.

When considering a network system’s sensitivity to perturbations, one might contemplate whether damage to small parts of the network will compromise the system’s structural integrity. This question is meaningful when dealing with a network whose function is primarily structural, such as a spider web, the lattice of crystal materials, or the backbone of a tower. It can be traced back to James Maxwell, whose 1864 work on networks of forces [2] made him a pioneer in the study of networks. Incidentally, this was four years prior to his publication on the flyball governor, a control system then used in steam engines that is often credited as the beginning of the mathematical theory of control [3].

However, there is a potentially much larger class of network systems in which the network’s role is not mainly structural. It is instead to mediate a process, as in the case of a road network, power grid, neuronal network, metabolic network, food web, or social network. If one of these networks is perturbed slightly, will the relevant process on the network change only slightly or substantially? In other words, is there a sensitive dependence of the network dynamics on the network structure? For example, in a network of people deliberating an issue, how does the convergence to consensus depend on the details of the network of interactions? In our power-grid network, where collections of power generators must be in pace at approximately 60Hz, how does the stability of this synchronous state depend on the particulars of how the power lines are connected among them? How do the populations of the various species in an ecosystem depend on the specifics of their feeding relationships? And so on.

Our recent study [5], in collaboration with Jie Sun (Clarkson University), examined whether a process can change substantially as a result of small network perturbations even when the overall network structure remains uncompromised. For example, consider the evolution of cooperation in an iterated prisoner’s dilemma game. Starting with a mixed population of cooperators and defectors, the full population may eventually converge to cooperators only or defectors only, depending on a small structural detail in the network (see Figure 1 and the accompanying animation).

Figure 1. Final state of two realizations of the iterated prisoner’s dilemma game for the same initial condition and the network differing by a single edge. Visuals adapted from Nicky Case’s “The Evolution of Trust” game.

To formalize the problem, one can abstract the networks to their graph representations, namely as sets of nodes connected by weighted edges. Of all the networks with a given number of nodes and edges, the most interesting are those evolved or designed to optimize the process under consideration—be it speed to consensus, synchronization stability, or population diversity—where limitations in the availability of edges and nodes generally represent limitations in resource availability (see below animation).

Therein lies the rub: as we optimize the network to enhance the relevant dynamical process, this very process may become more sensitive to small changes in network structure. The removal or addition of a node or an edge, or even a small change in edge weights, can cause significant dynamical changes.

As a concrete example, consider network processes governed by the eigenvalues of a coupling matrix. An especially important eigenvalue is the algebraic connectivity—defined as the smallest non-identically zero eigenvalue of the graph Laplacian matrix—which determines the rate of convergence to a uniform distribution when something diffuses from node to node, the onset of pattern-forming Turing instability in a network, and various aspects of network synchronizability.

We now focus on networks that maximize the algebraic connectivity. As a function of the density of edges, this eigenvalue exhibits cusp-like peaks, which become more pronounced and numerous as the network size increases. In fact, there are infinitely many, infinitely sharp peaks in the limit of large networks (see Figure 2a). Such cusps are signatures of extreme sensitivity to structural changes.

Figure 2. Sensitivity of optimal networks. The algebraic connectivity can exhibit cusp-like responses to changes in (a) the density of edges (unweighted perturbations) and (b) edge weights (weighted perturbations), as summarized in (c). Image credit: Takashi Nishikawa and Adilson Motter.

What if we perturb the weights of the edges instead of the number of edges? In some networks, the algebraic connectivity varies linearly with the perturbation strength, while in others it exhibits a very pronounced singular dependence (see Figure 2b). One can determine theoretically a network’s sensitivity to edge-weight perturbations, showing in particular that sensitivity is more prevalent in optimal networks.

More broadly, whether the system exhibits sensitive dependence on network structure depends on the class of networks, type of perturbation, and dynamical process. For processes governed by the algebraic connectivity, undirected networks are sensitive to edge removal and node addition but not to edge-weight perturbation, whereas directed networks are sensitive to edge-weight perturbation but not to changes in the number of edges or nodes (see Figure 2c).

The sensitive dependence of collective dynamics on network structure is analogous to the butterfly effect observed in the phenomenon of chaos. The butterfly effect commonly refers to sensitive dependence on initial conditions, where small changes in the initial state lead to large changes in the system’s subsequent evolution. Here, large changes in the dynamics are instead determined by small changes in the system’s parameters, which in this case define the underlying network. Thus, one can interpret this phenomenon as a parameter counterpart of the sensitive dependence observed in low-dimensional systems. While the effect is associated with chaos in low-dimensional systems, it is induced by optimization in network systems (see below animation).

How can sensitive dependence on the network structure benefit control? This sensitive dependence to changes is akin to an instability, such as those explored in jet design for increased maneuverability. Moving the center of gravity aft reduces an airplane’s stability, and moving it past the neutral point makes the airplane unstable, which increases its response to a given action. In this partial analogy, sensitivity to network structure means that one can manipulate the dynamics substantially with small structural adjustments, as shown in Figure 3 and the accompanying animation. That is, a sensitive network can be responsive to control even when the control actions are highly constrained, either with respect to the number of network components that can be actuated or the extent to which they can be changed. Though limited by how well one can resolve the cusp structure in practice, this property has the potential to lead to new control approaches based on modification of the network’s effective structure in real time.

Figure 3. Control implication of sensitive dependence on network structure. Large changes in the dynamics can be induced by small adjustments in (a) density of edges or (b) edge weights. Image credit: Takashi Nishikawa and Adilson Motter.

The interplay between network structure, optimization, and sensitivity is a promising topic of future research that offers fundamental insights into the control properties of complex network systems.

References
[1] Astrom, K.J., & Kumar, P.R. (2014). Control: A Perspective. Automatica, 50, 3.
[2] Maxwell, J.C. (1864). On Reciprocal Figures and Diagrams of Forces. Philos. Mag., 27, 250. 
[3] Maxwell, J.C. (1868). On Governors. Proc. R. Soc. Lond., 16, 270.
[4] Motter, A.E. (2015). Networkcontrology. Chaos, 25, 097621.
[5] Nishikawa, T., Sun, J., & Motter, A.E. (2017). Sensitive Dependence of Optimal Network Dynamics on Network Structure. Phys. Rev. X, 7, 041044.

Adilson E. Motter is the Charles E. and Emma H. Morrison Professor and Takashi Nishikawa is a research associate professor of physics at Northwestern University.

blog comments powered by Disqus