Satellite 14. Controlling Complex Networks: When Control Theory Meets Network Science

Final Program  

Registration of this symposium is free of charge. Yet, symposium participants still need to register for the NetSci2015 main conference.

June 2, 2015

Location (2 km north of main conference)

Biocomputación y Física de Sistemas Complejos (BIFI)
Mariano Esquillor ( Edificio I+D )
50018 Zaragoza, Spain
Directions and map from main conference (Google)


List of Speakers

Multilayer Control of Complex Networks
In this talk, a multilayer control architecture will be presented to achieve control of the collective behavior of a complex network of interest. The idea is to  deploy the control action across multiple layers so that different types of  strategies can be used concurrently to better achieve the control objective.  The resulting architecture is a multiplex control network that is used to tame the collective behavior of the multi-agent system in a desired manner.  As a representative example, we will focus on the problem of reaching consensus or synchronization in a network of linear or nonlinear, possibly heterogeneous, systems (that we shall term as the “open-loop network”). We will start by presenting the design of a multilayer PID control network able to steer towards consensus or synchronization an heterogeneous ensemble of linear or nonlinear agents.  We will show that such PID multiplex strategy  guarantee convergence in networks of linear or nonlinear systems despite the presence of heterogeneity in the node dynamics and constant disturbances. This will be achieved by deploying on the links of the open loop network different types of coupling [proportional (P), integral (I) or derivative (D)] through different layers, each characterized by a different structure. Conditions linking the strength of the control gains will be derived that link their values with the structural properties of the open loop network and each of the control layers. It will be shown that the main advantage of the multilayer strategy is that the control effort can be substantially reduced by changing the structure of the layers of the control architecture. To further illustrate the flexibility and effectiveness of the multilayer structure of the control architecture presented in this talk, we will then look at the problem of adaptively selecting optimal gains in a directed network to achieve consensus in an optimal manner. We will show that it is possible to combine a consensus layer to optimize the algebraic connectivity of the open loop network with an adaptive layer selecting the optimal gains to achieve synchronization or consensus. Finally, perspectives and future work will be discussed

[1] D. Burbano, M. di Bernardo, Distributed PID Control for Consensus of Homogeneous and Heterogeneous Networks, IEEE Transactions on Control of Network Systems, to appear, 2015 [10.1109/TCNS.2014.2378914]
[2] D. Burbano, M. di Bernardo, Consensus and synchronization of complex networks via proportional-integral coupling, Proc. IEEE International Symposium on Circuits and Systems, 1796-1799, 2014
[3] D. Burbano, M. di Bernardo, Multilayer PI Control for Consensus in Networks of Heterogeneous Linear Agents, Automatica, under review, 2014
[4] L. Kempton, G. Hermann, M. di Bernardo, Adaptive weight selection for optimal consensus performance, Proc. IEEE Conference on Decision and Control, 2234-2239, 2014

Controllability of dynamic networks: isotropic vs. anisotropic networks
In the last years a lot of work has been devoted to determine how the topology of a dynamic network influences its controllability properties. A dynamic network is said to be controllable if its state can be driven to an arbitrary target by imposing a suitable input profile. In some cases, however, the complexity of the network requires a huge amount of energy to achieve this goal, making this operation impossible in practice. For this reason more recently some research has been devoted for understanding the “degree” of controllability of complex networks. In this presentation we will propose a metric for specifying the controllability degree of a complex network. This metric is based on the worst-case control energy to drive the network to an arbitrary configuration. We show that symmetric networks are difficult to control in the sense that the control energy grows exponentially with the network complexity when the number of controlled nodes remains constant. This result can be shown to hold true also for asymmetric networks that nevertheless keep an isotropic dynamics, namely a dynamics that is symmetric on average. On the contrary, we show that sufficiently anisotropic networks might be easy to control, as the control energy remains bounded independently of the network complexity.

Data-Driven Control of Epidemic Outbreaks
In this talk, we introduce a novel mathematical framework to control viral spreading process in a network with unknown contact rates. We assume that we have access to time series data describing the evolution of the spreading process observed by a collection of sensor nodes over a finite time interval. We propose a data-driven robust optimization framework to find the optimal allocation of protection resources (e.g., vaccines and/or antidotes) to control the viral spread at the fastest possible rate. In contrast to current network identification heuristics, in which a single network is identified to explain the observed data, we use available data to define an uncertainty set containing all networks that are coherent with empirical observations. Through convexification of the uncertainty set, we are able to efficiently find the optimal allocation of resources to control the worst-case spread that can take place in the uncertainty set of networks.

  • Tyler Summers,
    Swiss Federal Institute of Technology, Switzerland

Submodularity and controllability in complex dynamical networks
Controllability and observability have long been recognized as fundamental structural properties of dynamical systems, but have recently seen renewed interest in the context of large, complex networks of dynamical systems. A basic topology design problem is sensor and actuator placement: choose a subset from a finite set of possible placements to optimize some real-valued controllability and observability metrics of the network. Surprisingly little is known about the structure of such combinatorial optimization problems. In this talk, I will show that several important classes of metrics based on the controllability and observability Gramians have a strong structural property that allows for either efficient global optimization or an approximation guarantee by using a simple greedy heuristic for their maximization. In particular, the mapping from possible placements to several scalar functions of the associated Gramian is either a modular or submodular set function. The results are illustrated on problems of sensor and actuator placement in power grids.

Structural reduction for controlling complex networks:
We propose a general and efficient framework to explore controllability of complex networks. By implementing 1st- and 2nd-order structural reduction, we can preserve a minimum set of driver nodes for achieving full control of any complex networks. The structural approach has a rigorous theoretical support that stems from canonical control theory. The framework has several advantages compared to recently developed approaches. First, the structural approach with great efficiency goes beyond the structural controllability theory and can offer exact controllability of networks with arbitrary link weights and topology. Second, the framework offers an intuitive and comprehensive understanding of the relationship between network controllability and structure, and build a connection between the structural controllability theory and the exact controllability theory. Third, links whose weights have no effect on controllability can be identified, which can be use to determine if a network is strongly controllable (a network is said to be strongly controllable if its controllability is exclusively determined by its topology, regardless of link weights). Fourth, nodes can be efficiently classified into three categories: critical, redundant and intermediate during the reduction process. Fifth, the tools offered by the framework are of extremely high efficiency, higher than the maximum matching algorithm and the methods based on eigenvalues and matrix ranks, because the tools are basically local structural algorithm without the need of global search. Applying our tools to complex networks yields several interesting results, including a phase transition at natural logarithm when carrying out the 1st-order structural reduction and two phase transitions in node classification. We have also offered analytical predictions of all the results based on network theory.

Towards controlling complex networks, more or less?
The past decades have witnessed flourishing advances of understanding the essence of complex networking worlds, which not only help people show sufficient respect to the significance of connectivity patterns of complex networks to their collective behaviors and functional performance, but also arouse wide attention to the huge desire of controlling complex networks. The fruitful outcomes to pinning a small fraction of nodes in a network to achieve the desired collective behaviors, i.e., the so-called pinning control, have exhibited the feasibility and effectiveness of controlling complex nonlinear networks with extending to leader-follower patterns in multi-agent networks and pacemakers for kuramoto-oscillator networks. When neglecting the nodal nonlinear dynamics embedded into a network and concerning reachability of control signals, structural controllability as well as strong structural controllability of a network is a key factor to depict the topological complexity of controlling a complex network. In this talk, I will briefly overview the main interests towards controlling a complex network along with the latest findings from my group involving temporal networks and heterogeneous nodal dynamics, and discuss some examples to explore in future.

Voltage Collapse and Control in Complex Power Grids
(Florian Dörfler, John W. Simpson-Porco, and Francesco Bullo)
The ability of a large-scale power grid to transfer energy from producers to consumers is constrained by the network structure, by the nonlinear physics of power flow, as well as by operational limits. Any violation of these fundamental constraints has been observed to result in voltage collapse blackouts, where nodal voltages slowly decline before precipitously falling. In fact, the majority of recent blackouts in Western countries have been attributed to voltage collapse and related instabilities. The available methods to test for voltage collapse are dominantly simulation-based and offer little fundamental insight for the design of control strategies. Here we present a closed-form condition under which a power network is safe from voltage collapse. The condition combines the complex structure of the network with the reactive power demands to produce a node-by-node measure of network stress, lower bounding the distance to collapse and predicting the largest nodal voltage deviation in the network. We extensively test our prediction on large-scale systems, and demonstrate how our stability condition can be applied to increase grid stability margins through corrective control actions.

Structural controllability and control of temporal networks
The control of complex systems is an ongoing challenge of complexity research. Recent advances using concepts of structural control deduce a wide range of control related properties from the network representation of complex systems. Here, we examine the controllability of complex systems for which the timescale of the dynamics we control and the timescale of changes in the network are comparable. We apply both analytical and computational tools to study controllability based on the characteristics of the temporal network. We investigate the controllable subnetwork using a single input, present analytical results for a generic class of temporal network models, and perform measurements using data collected from a real system (email communication network). Depending upon the density of the interactions compared to the timescale of the dynamics, we witness a phase transition describing the sudden emergence of a giant controllable subspace spanning a finite fraction of the network. We also study the role of temporal patterns and network topology in real data making use of various randomization procedures, finding that the overall activity and the degree distribution of the underlying network are the main features influencing controllability.

[1] M. Posfai and P. Hövel: Structural controllability of temporal networks, New J. Physics 16, 123055 (2014).

Disclosing network structure by Markov chain models
Markov chains are standard tools in virtually all fields of applied mathematics. In systems and control theory, they have often been exploited to effectively solve many problems in identification, optimal control, and decision theory. Markov chains find a natural application to networks, where they model random walks which are simply created by concatenating random steps from node to node. By analysing the properties of random walks, a number of structural properties of the network can be investigated. Not only one can attribute centrality scores to nodes (PageRank), but one can also characterize the network properties at the meso-scale level, e.g., detect the existence of communities or assess the core-periphery structure of the network. We review some recent results on this topic, with the help of several illustrative examples.

Profiting from Nonlinearity, Noise, and Interconnectivity to Circumvent the Curse of Dimensionality and Parameter Uncertainty in Network Control
The concept of a “complex” network pervades science and engineering. Due to the interconnected nature of such systems, perturbations that affect one or more nodes can propagate through the network and potentially cause the system as a whole to fail or change behavior. In this presentation I will show that this aspect of interconnectivity can be a blessing in disguise, giving rise to new strategies to control collective behavior. A hallmark of real complex networks, both natural and engineered, is that their dynamics are high dimensional and inherently nonlinear. It is this nonlinearity that permits the coexistence of multiple stable states (some desirable, others not), which correspond to different possible modes of operation of a real network. Because of this, when a network is perturbed, it can spontaneously go to a “bad” state even if there are “good” ones available. The question I will address is: can this principle be applied in reverse? In other words, can we perturb a network that is in (or will approach) a “bad” state in such a way that it spontaneously evolves to a target state with more desirable properties? I will provide an affirmative answer to this question by presenting a framework that is highly scalable, robust to parameter uncertainty, and that allows the use of noise as an additional control tool.

[1] S.P. Cornelius, W.L. Kath, and A.E. Motter, Realistic control of network dynamics, Nature Communications 4, 1942 (2013).
[2] S.P. Cornelius and A.E. Motter, NECO - A scalable algorithm for NEtwork COntrol, Protocol Exchange (2013), doi:10.1038/protex.2013.063.
[3] J. Sun and A.E. Motter, Controllability transition and nonlocality in network control, Phys. Rev. Lett. 110, 208701 (2013).
[4] D.K. Wells, W. L. Kath, and A.E. Motter, manuscript in review (2015).


Directions and Map to Satellite

CSS from NetSci2015 Grupo-Pacifico