The research within NETWORKS is split into two synergistic directions:
A. Network Structure: Statics and Dynamics, with emphasis on
B. Network Shaping: Design, Operation and Optimization, with emphasis on
Network Structure revolves around stochastic and algorithmic aspects of networks whose topologies are given, Network Shaping around stochastic and algorithmic aspects of networks whose topologies can be controlled.
The networks can be either static or dynamic, and either centrally organized or self-organized.
Each direction addresses foundational issues as well as applications to real-life networks. The
first direction aims at studying stochastic models for networks, classifying these models, analyzing their functionality, and developing efficient algorithms to perform large-scale and complex network computations. The second direction aims at studying design, operation and optimization of networks, i.e., how they can best be built and controlled and how their functionality can be improved by manipulating them. The main focus is on the scheduling of resources (as in transportation, traffic, communication and energy networks) and on real-time adaptation in settings where high variability requires the use of stochastic models.
Research in the two directions will be organized into 7 themes, each revolving around a number of key questions that zoom in on the challenging mathematical problems underlying complex large-scale networks. For each of these themes several smaller research projects are defined for PhD-students and postdocs.
Theme 1: Approximate network methods
The fact that a problem is NP-complete implies that it is generally believed to be impossible to compute an optimal solution in polynomial time. In many practical settings, however, it is good enough to compute a solution that it almost optimal. The question then becomes how close to the true optimum we can get using an efficient (polynomial-time) algorithm. Understanding this question is at the hart of profound developments in both algorithms and complexity theory, and requires fascinating connections between various areas of mathematics.
Theme 2: Spatial networks
In many networks, nodes have locations in a geometric space, and typically, connections between nearby nodes are more abundant than connections between distant nodes. Nevertheless, long-range connections and highly-connected nodes play crucial roles as well. Most algorithms designed for complex networks do not fully exploit the underlying geometry. This calls for novel approaches, to speed up and improve complex network algorithms using spatial network information.
Theme 3: Quantum networks
Quantum computers are the next generation computing devices, holding a tremendous promise to revolutionize the way we process and handle information throughout science, technology, and our rapidly growing information society. A big open problem is to classify which algorithmic network problems are amenable to a quantum speed-up. For those problems that are, novel quantum-based algorithms should be designed, to deal with network complexity.
Theme 4: Dynamics of networks
Networks typically evolve over time. Random graphs and graph limits are essential tools to model network structures as stochastic objects that grow in time and space according to certain local growth rules. By adapting these rules, different types of dynamic network behavior can be captured and analyzed. Key questions are how local growth rules give rise to the global network structure and behavior, and whether universal network behavior, applying to many complex yet different real-life networks, can be discovered.
Theme 5: Dynamics on networks
Many state-of-the-art network problems are about the speed at which, and the precise way in which information spreads over networks. While many networks themselves are too complex to describe in detail, the local dynamics that describes how information diffuses gives a mathematical handle to understand global behavior of network processes. Big challenges in this field relate to modeling, understanding, and in the end designing algorithms to control network processes.
Theme 6: Transportation and traffic networks
In virtually all sectors of society we are faced with issues regarding the design, operation and control of highly complex networks. Of crucial societal interest are transportation and traffic networks, for which the range of network-related problems is staggering. Among the big challenges are the shaping of network structures, and robust on-line routing and scheduling. Can we design control algorithms to dynamically regulate road traffic and reduce considerably traffic congestion?
Theme 7: Communication and energy networks
Communication and energy networks are both prominent instances of highly complex large-scale networked systems that are of critical importance to society. Because of their vital interest, these systems need to be designed to achieve consistently high levels of performance and reliability, and yet be cost-effective to operate. This is extremely difficult, due to inherent uncertainty and random variation in demand as well as supply. Among the great challenges are to develop stochastic models and optimization algorithms for next-generation networks that can deal in real-time with complexity and changing environments.