FOR 2975:  Algorithms, Dynamics, and Information Flow in Networks

• Subject Area: Computer Science, Systems and Electrical Engineering
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 411362735

The focus of this unit remains the analysis of dynamical processes on complex networks, their uses, their equilibria, and their unintended, potentially cataclysmic consequences, by means of the rigorous analytical machinery of the theory of computing. Computer science in the 21st century faces the necessity to cope with complex interactions that, rather than being designed by a purposeful authority, are shaped by natural, economical, or social forces. We urgently require tools to model such complex interactions, the processes that unfold on them, the equilibria that they may attain as well as the algorithmic tools to simulate such processes. The overarching aim of this research group is to develop these tools. In the second phase, the unit will adjust the research efforts to work on a set of timely and challenging directions. It will maintain a mixture of modeling network processes, design and analysis of dynamics and protocols, as well as simulation and experiments. A central aspect explored in the second phase is the temporal evolution of networks. While static random graph models of various types have been the mainstay of network science for nearly three decades, these models have obvious limitations when it comes to modelling, e.g., contact networks, which require a time axis. At present it is far from clear whether the main hypothesis of network science -- that networks across different contexts exhibit similar fundamental properties -- holds true of temporal networks as well. A further new aspect is metastability, i.e., the presence of attractive out-of-equilibrium states that may trap dynamics for an extraordinarily long period of time. A third new aspect is the role of structural network properties, in connection with fine-grained complexity theory. The underlying question is to what extent ideas from structural graph theory can replace probabilistic modelling assumptions.

• DFG Programme: Research Units

Projects

• Coordination Funds (Applicant Hoefer, Martin )
• Distributed and Collaborative Systems of Agents (Applicant Berenbrink, Petra )
• Formation of Realistic Networks (Applicant Friedrich, Ph.D., Tobias )
• Large-Scale Randomization and Certification (Applicant Meyer, Ulrich )
• Opinion Dynamics with Rational Agents (Applicant Hoefer, Martin )
• Parameterized Complexity of Network Dynamics (Applicant Dell, Holger )
• Reconstruction and Learning in Complex Networks (Applicant Coja-Oghlan, Amin )
• Systemic risk and financial contagion (Applicant Meyer, Ulrich )

• Spokesperson: Professor Dr. Martin Hoefer