Supervisors: Carlos Canudas-de-Wit (DR-CNRS, supervisor), Paolo Frasca (co-supervisor).
Context: ERC-AdG Scale-FreeBack
Employer: CNRS. Location: Grenoble, France
Applications: http://www.gipsa-lab.grenoble-inp.fr/~carlos.canudas-de-wit/ERC.php
Context. Scale-FreeBack is an ERC Advanced Grant 2015 awarded to Carlos Canudas-de-Wit, Director ofResearch at the National Center for Scientific Research, (CNRS), during Sept. 2016-2021. The ERC is hosted bythe CNRS. The project will be conducted within the NeCS group (which is a joint CNRS (GIPSA-lab)-INRIA team).Scale-FreeBack is a project with ambitious and innovative theoretical goals, which were adopted in view of thenew opportunities presented by the latest large-scale sensing technologies. The overall aim is to developholistic scale-free control methods of controlling complex network systems in the widest sense, and to set thefoundations for a new control theory dealing with complex physical networks with an arbitrary size. Scale-FreeBack envisions devising a complete, coherent design approach ensuring the scalability of the whole chain(modelling, observation, and control). It is also expected to find specific breakthrough solutions to theproblems involved in managing and monitoring large-scale road traffic networks. Field tests and other realisticsimulations to validate the theory will be performed using the equipment available at the Grenoble Traffic Labcenter, and a microscopic traffic simulator replicating the full complexity of the Grenoble urbannetwork. The proposed work will be undertaken in the context of this project.
Topic description. Many physical systems (i.e. Like road traffic networks) are homogenous networks inwhich the node-link distribution follows a bell-shaped, exponentially decaying curve and all the nodes havepractically the same number of links. Due to this homogenous distribution, the modeling and control issues arebound to be complex. Scale-FreeBack project is elaborated on the idea that complexity can be broken down byabstracting an aggregated evolutionary scale-free model by dynamically merging neighboring nodes present inthe original network. This idea is in line with previous scale-free network concepts [Bar’02, Bar-et-al’13],according to which the underlying network structure is dominated by relatively small numbers of nodes (hubs)having a large number of connections. Scale-free (or heterogeneous) networks are characterized by heavytailednode/link distributions obeying a power law, at least asymptotically. The main idea conveyed by Scale-FreeBack is that controlling scale-free networks by acting on only a limited number of lumped nodes, thecontrol design for large-scale systems will be tractable. The first step towards this goal consists of studying in ageneral framework how a complex homogenous network can be abstracted by scale-free models.
This research proposal deals with specific problem of devising on-line partitioning algorithms forevolutionary scale-free dynamic networks. Questions addressing the problem of lumped model constructionscorresponding to the best trade-off between scalability and performance, and having the relevantcontrollability/observability properties are in order. Performance in the lumped system can be enhanced by theidentification of the most central/influential nodes within each portion of graph corresponding to lumpednodes. These algorithms must yield low complexity solutions consistent with the scalable project approach andthe on-line implementation of the rest of the components.
When designing these algorithms, we plan to build on a wide literature ranging from on-line computation ofcentrality indices to graph partitioning and community detection, in which many methods have been proposedfor solving the problem of partitioning a graph into components while minimizing some representative indexes(such as the number of edges between different components, or their total weight, or the modularity).However, our problem will differ significantly from those solved in the literature, mainly because ourpartitioning objective is more complex, and also because of the additional constraints imposed here on thedynamic partitioning process by the need to make only small increments in the partitions. For instance, duringthe dynamic construction of the models, the next partitioning step is restricted to making small changes in thecurrent one, and has to be adapted to variations in the optimization objectives during the dynamic evolution ofthe system.
Request Background. Control Systems, Applied mathematics.
Applications. Please follow the application procedure indicated at http://www.gipsa-lab.grenoble-inp.fr/~carlos.canudas-de-wit/ERC.php
[Bar’02 ] A.-L. Barabasi, “Linked; the new science of networks”, Perseus publishing, Cambridge, M. (2002).
[Bar-et-al’13] A. Barrat, M. Berthélemy, A. Vespignani , “Dynamical Processes on Complex Networks”,Cambridge U-press, 2013.