# MULTIPLEX

## Foundational Research on MULTIlevel comPLEX networks and systems (MULTIPLEX)

MULTIPLEX is a large-scale integrating project (IP) with 17 participating research institutes from all over Europe, funded by the European Commission. It addresses the objective "Dynamics of Multi-Level Complex Systems" of the FP7-ICT work program. The project started in November 2012 and will last for 48 month.

The goal of the project is to understand how multi-level complex systems evolve, and how they can be controlled and optimized. Indeed, multi-level dependencies may amplify cascading failures that might result in a sudden collapse of the entire system. Recent large-scale blackouts resulting from cascades in the power-grid coupled to the control communication system witness this point very clearly. A better understanding of multi-level systems is essential for future ICTs and for improving life quality and security in an increasingly interconnected and interdependent world. In this respect, complex networks science is particularly suitable for the many challenges that we face today, from critical infrastructures and communication systems to techno-social and socio-economic networks.

MULTIPLEX proposes a substantial paradigm shift for the development of a mathematical, computational and algorithmic framework for multi-level complex networks. Firstly, this will lead to a significant progress in the understanding and the prediction of complex multi-level systems. Secondly, it will enable a better control and optimization of their dynamics. By combining mathematical analyses, modeling approaches and the use of massive heterogeneous data sets, we shall address several prominent aspects of multi-level complex networks, i.e. their topology, dynamical organization and evolution.

Research in this project is divided into four work packages:

- WP1 deals with the "Foundational Study of Structure & Topology of Multi-level Complex Systems".
- WP2 focusses on the "Foundational Study of Dynamics of Multi-level Complex Systems".
- In WP3, "Modeling of Multi-level Complex Systems", the ideas, mathematical quantities, approaches and algorithms of the first two work packages are tested on specific ICT applications.
- WP4 provides a "Data-driven validation in specific application domains".

More information is available at the official project homepage.

In Paderborn, the research groups "Algorithms and Complexity" of Friedhelm Meyer auf der Heide and "Theory of Distributed Systems" of Christian Scheideler contribute to this project. We will mainly focus our research on the following topics:

## Maintaining Scalability and Robustness

We will investigate approaches in which the nodes themselves manipulate the network in order to maintain properties that are central for a high scalability and robustness. The first direction is network creation games. In a network creation game, each node maintains a certain number of edges to other nodes in the network, and each node greedily decides how to change its connections in order to improve its utility function. An example of such a function is to minimize its maximum distance to any other node in the network. Network creation games have already been studied for simple, uniform networks, but for complex networks, in which nodes and networks of different types are available, nothing is known yet. Besides scalability, network creation games can also be applied to make the network more robust. For example, a node may spread its edges to minimize the chances that it gets disconnected from the network. Robustness issues have not been studied in network creation games so far. In addition, to studying network creation games that can maintain a certain degree of robustness, we will also consider potential trade-offs between maintaining robustness and scalability.

## Certifying Distributed Algorithms

A central aspect of maintaining a certain state of a network is to assure that nodes or agents can quickly determine whether a given property is still satisfied. Here, local certificates can help. Our use of certificates is closely related to the notion of "proof labels" and "certificates" and bears some similarity to the notion of witnesses in the theory of NP. However, beyond a few results, little is known in distributed computing about the space complexity of certificates as well as about the complexity of computing them. This opens many interesting questions to explore. For an example, consider the spanning tree problem. It was recently shown that verifying the correctness of a spanning tree in a distributed system without the use of certificates could be harder than computing it. On the other hand, it is known that when using appropriate local certificates, the correctness of a spanning tree can be checked by just exchanging these certificates between direct neighbors. We will study the complexity of using certificates in order to obtain solutions for the first two subtasks that can quickly detect and therefore react to dynamics.