Large-scale systems

Node aggregation and Scale-free methods

The task of controlling large-scale networks is very difficult in the first place because of its large dimensionality, making the computation of traditional control algorithms too expensive. In systems of large dimensions, the number of sensors is often much lower than the number of states, which makes hard to identify the mathematical model of the system and to estimate its state. Similar issues arise regarding the number of actuators. Another difficulty is that the energy needed to control all nodes of the network can grow exponentially with the number of nodes, at least for some network structures. Therefore, in some cases, it can be preferable to control and estimate some aggregated measure of the entire network rather than all individual states, since the energy required to control aggregated quantities instead of all network states is much less. Examples of aggregate quantities would be, for instance, the average state of the whole network and its variance, or the average values in different regions of the network. Therefore, the scale-free approach that is developed in the ERC Scale-FreeBack project is based on the aggregation of the variables that belong to neighboring nodes. The aggregation is done in such a way to construct a scale-free network, where the goal is to control the averaged state and the variance of the hubs, corresponding to regions or groups of nodes, and the control is applied to the boundaries of the hubs. A graphical illustration of the approach is provided in the figure that shows the a scale-free network with hubs (shaded in yellow) controlled from the boundary nodes (double circles). In scale-free dynamic network modelling & analysis, the purpose is to reduce the system network complexity by finding the appropriate level of scale aggregation, while preserving the physical properties of the original system and imposing the control and observation model properties required. Examples include output controllability of a scale-free network and the dual problem of reconstruction of an averaged state. The ultimate goal has been developing novel control methods for scale-free network systems. The team has applied these novel tools to traffic networks, namely in the GTL-Ville experimental platform.

The continuation method

When considering limit models for large networks, we naturally fall into continuous limits. These limits can take different forms. One way to define continuous limits is to regard, instead of the agent states, their distribution in space. The evolution of the distribution would then be naturally described by a partial differential (PDE) or integro-differential equation. In a control perspective, the purpose of a good approximation is that control actions can be designed on the continuous system and have guaranteed performance on the original (graph-based) one; see illustration in the figure.
By the thesis work of Denis Nikitin and a series of papers, we have reached a twofold objective:

1. We have developed a sound and complete theoretical framework for the PDE approximation of large networked ODE systems, showing that this continuation can be performed both for linear and nonlinear systems, including multidimensional, space-and time-varying systems. When applied to a large-scale network, the continuation provides a PDE describing evolution of continuous state approximation that respects the spatial structure of the original ODE.
2.  We have applied this framework to multiple applications including swarms of autonomous robots, traffic networks, laser arrays, spin-torque oscillators. In all these examples, the continuous PDE approximates remarkably well the original ODE system.

Graphons

Another promising intrument to define continuous limits of graphs are graphons, which are defined as the limit objects of sequences dense networks. A visual intuition of what a graphon is can be gained with the help of a pixel picture. Starting from the adjacency matrix of a graph, if we visualize a 0 as a small white square and a 1 as a small black square, we can construct a pixel diagram, as we can appreciate in the figure. Letting the number of nodes go to infinity, we obtain a continuous object, a “heat map” of connectivity that characterizes the whole sequence.

Conversely, finite graphs can be generated by sampling from the continuous graphon. Recent works related to the application of graphons include the study of dynamics over networks, link prediction problems, and large population games. Inspired by very recent results on centrality measures, we have been able to use graphons to define performance metrics that quantify system-theoretic properties like stability, controllability, or sensitivity to noise. These metrics can be computed from the graphon at low computational cost and approximate well the system-theoretic properties of the corresponding dynamics on graphs of large-but-finite size: our results cover networked SIS dynamics and the spectra of graph Laplacians.