Concentration effects and collective variables in dynamical systems on networks

Abstract

Dynamical systems on networks, which can be seen as a special type of agent-based model, are widely used to model systems that consist of many interacting entities called agents. In this framework the nodes in the network represent the agents, the edges represent the relations between them, and the state of each agent evolves over time in dependence on the states of its neighbors, typically in a stochastic manner. Although the state evolution of each single agent is often dictated by simple rules and mechanisms, the overall collective or emergent behavior of the system, which is the result of many individual interactions, can be incredibly hard to anticipate and understand. The investigation of this collective behavior is the main focus of this thesis. Even though the collective behavior is difficult to predict, it is typically much less complex than the vast number of degrees of freedom would allow for and instead (approximately) follows some low-dimensional dynamics. The understanding of collective behavior hence consists of two steps. Firstly, a projection that maps the high-dimensional microscopic state, containing the state of each agent, to a low-dimensional macroscopic state, containing only the essential aggregated information to describe the collective behavior, has to be found. This projection, which filters out unnecessary degrees of freedom and quickly decaying processes of the original system, is called a collective variable (CV). Secondly, the reduced macroscopic system that dictates the evolution of the macroscopic state has to be derived. If the choice of CV was appropriate, this macroscopic system is able to reproduce the low-dimensional projection of the original model, i.e., the collective behavior. Akin to the law of large numbers, the aggregated random actions of many agents sometimes lead to an approximately deterministic macroscopic dynamics, which is referred to as a concentration effect. This thesis mainly considers Markovian discrete-state dynamics on (random) networks and addresses efficient simulation, discovery of CVs and macroscopic dynamics, and the occurrence of concentration effects. In this setting the shares of each discrete state in the system, or in certain subsystems, constitute an important choice of CVs. Conditions that guarantee the convergence of the dynamics of the shares to a deterministic mean-field ordinary differential equation in the large population limit are proved. These conditions enable the derivation of parameter bounds for popular random graph models, e.g., Erdős-Rényi random graphs, the stochastic block model, and random regular graphs, that ensure convergence to the mean-field limit, which is demonstrated for a continuous-time noisy voter model (CNVM). For systems that do not exhibit convergence to the mean-field limit and for which the simple state shares are not appropriate CVs because they lack essential state information, a data-driven method for algorithmically learning good and interpretable CVs from model simulations is presented. This method permits to assess the quality of the learned CVs and to infer their relation to topological features of the network. In combination with established techniques for learning dynamics from data, an automatic evaluation of the collective behavior can be achieved. This is demonstrated for the CNVM on scale-free networks.

Dynamische Systeme auf Netzwerken werden häufig verwendet, um Systeme zu modellieren, die aus vielen interagierenden Einheiten, welche Agenten genannt werden, bestehen. Hierbei stellen die Knoten im Netzwerk die Agenten dar, die Kanten repräsentieren die Beziehungen zwischen den Agenten, und der Zustand jedes Agenten entwickelt sich im Laufe der Zeit in Abhängigkeit von den Zuständen seiner Nachbarn, in der Regel auf stochastische Weise. Obwohl die Zustandsentwicklung jedes einzelnen Agenten oft durch einfache Regeln und Mechanismen bestimmt wird, kann das kollektive oder emergente Verhalten des gesamten Systems, welches das Ergebnis vieler individueller Interaktionen ist, sehr schwer zu antizipieren und zu verstehen sein. Die Untersuchung dieses kollektiven Verhaltens ist der Schwerpunkt dieser Arbeit. Obwohl das kollektive Verhalten schwer vorherzusagen ist, ist es in der Regel deutlich weniger komplex als es die große Anzahl von Freiheitsgraden zulassen würde und folgt stattdessen (ungefähr) einer niedrigdimensionalen Dynamik. Das Verständnis des kollektiven Verhaltens besteht daher aus zwei Schritten. Erstens muss eine Projektion gefunden werden, die den hochdimensionalen mikroskopischen Systemzustand, der den Zustand jedes einzelnen Agenten enthält, auf einen niedrigdimensionalen makroskopischen Systemzustand abbildet, der nur die wesentliche aggregierte Information zur Beschreibung des kollektiven Verhaltens enthält. Diese Projektion, die unnötige Freiheitsgrade und schnell abklingende Prozesse des ursprünglichen Systems herausfiltert, wird als kollektive Variable bezeichnet. Zweitens muss das reduzierte makroskopische System hergeleitet werden. Wenn die Wahl der kollektiven Variable angemessen war, ist das makroskopische System in der Lage die niedrigdimensionale Projektion des ursprünglichen Modells, also das kollektive Verhalten, zu reproduzieren. Ähnlich wie beim Gesetz der großen Zahlen führen die aggregierten zufälligen Aktionen der vielen Agenten manchmal zu einer annähernd deterministischen makroskopischen Dynamik, was als Konzentrationseffekt bezeichnet wird. Diese Arbeit befasst sich hauptsächlich mit gedächtnislosen dynamischen Systemen mit diskretem Zustandsraum auf (zufälligen) Netzwerken und behandelt die effiziente Simulation, die Herleitung von kollektiven Variablen und makroskopischer Dynamik sowie das Auftreten von Konzentrationseffekten. Für solche Systeme stellen die Anteile jedes diskreten Zustands im System (oder in bestimmten Teilsystemen) eine wichtige Wahl der kollektiven Variablen dar. Es werden Bedingungen nachgewiesen, welche die Konvergenz der Dynamik dieser Anteile zu einer deterministischen "mean-field" Differentialgleichung im Limit unendlich vieler Agenten garantieren. Diese Bedingungen ermöglichen die Herleitung von Parameterschranken für populäre Zufallsgraphenmodelle, zum Beispiel Erdős-Rényi Zufallsgraphen, das stochastische Blockmodell und reguläre Zufallsgraphen, sodass die Konvergenz zum "mean-field" Limit gewährleistet ist. Dies wird für ein zeitkontinuierliches "voter model" demonstriert. Für Systeme, die keine Konvergenz zum "mean-field" Limit aufweisen und für welche die oben genannten Anteile keine geeigneten kollektiven Variablen sind, wird eine datengesteuerte Methode zum algorithmischen Lernen interpretierbarer kollektiver Variablen aus Modellsimulationen vorgestellt. Diese Methode ermöglicht es die Qualität der gelernten kollektiven Variablen zu bewerten und ihre Beziehung zu topologischen Merkmalen des Netzwerks abzuleiten. In Kombination mit etablierten Techniken zum Lernen von Dynamik aus Daten kann eine automatische Evaluation des kollektiven Verhaltens erreicht werden. Dies wird beispielhaft für das "voter model" auf skalenfreien Netzwerken demonstriert.