Adaptive Networks

research topic visualization

In an adaptive network the network structure responds dynamically to the state of the nodes, while the nodes are subject to processes that occur on that structure.

A simple example is an epidemic where infected people self-isolate to avoid infecting their friends [1]. The infection is transmitted along the links of the network, hence it is a structure-dependent process that affects node states. The self-isolation of infected breaks links in the network and hence is a node-dependent process that affects the structure. In this way a dynamical feedback loop between the state and the topology is formed that gives adaptive networks the ability to self-organize in interesting and often unexpected ways.

A brief history

In certain applications adaptive networks have already for a long time. However, the realization that the state-structure feedback gives rise to a distinct set of phenomena only dawned in response to four ground-breaking papers in 2000. These include the neural model of Bornholdt and Rohlf [2], an abstract Boolean network by Paczuski et al. [3], a network formation model by Skyrms and Pemantle [4], and network cooperation game by Zimmermann et al. [5]. It followed a steady trickle of papers in a broad variety of applications.

Adaptive networks really took of with an explosion of papers in 2006. In this year also our own first contribution to adaptive networks [1] was published. In this paper we showed how properties of the network structure can act as variables in epidemic dynamics. Later it would be shown by Scarpino et al. [6] with a closely-related that the resulting feedback explained a previously unexplained phenomenon in epidemic data.

Our 2006 paper [1] also led to the widespread adoption of the name 'adaptive networks' and the subsequent review [7] contributed to their recognition as an independent class of networks within network science.

Interplay of topology and local states

What makes adaptive networks interesting is the dynamical interplay between network topology and local node states. Dynamics on a static network are often effectively low dimensional which limits the range of dynamical phenomena that can be observed. By contrast, in an adaptive network the dynamics of the nodes reshape the topology. The myriad of topological degrees of freedom then act as a memory leading to complex and often surprising dynamics.

Among the dynamical phenomena that have been observed in adaptive networks is the robust self-organization to critical state, the emergence of phase transitions involving structural and dynamical variables, and the emergence of complex self-organized structures from homogeneous initial conditions.

Mathematical investigation

Most adaptive networks models consider discrete-state notes (e.g. infected and susceptible agents). These models can be explored mathematically using network moment expansions, which were first applied to adaptive networks in [1].

While moment expansions continue to be the main workhorse for adaptive networks studies, there are some systems that can only be poorly described with this type of approximation, particularly these are systems that can undergo fragmentation transitions, where the networks breaks into multiple components. A classic example, proposed originally by Holme and Newman [8] and analyzed in details by Vazquez et al. [9]. BioND lab managed to show this type of system much can be much more accurately described by a different type of approximation that we call motif expansion [10].

Among other mathematical ideas that the lab has pioneered is the so-called triple jump method [11] in which one uses a very accurate type of moment expansion that leads to an infinite dimensional differential equation system. Due to their particular structure these systems can then be mapped exactly to a two-dimensional partial differential equation in two-dimensional space. If this equation is hyperbolic it can further be mapped back onto a low-dimensional ordinary differential equation, which can then be solved.

While there is no universal approximation that works well for every adaptive networks, we have discovered some general approaches that allow us to build approximation schemes that work for a particular application. For example we were thus able to analyze a very difficult growing adaptive network, that approximates scale-free degree distributions [12].

A subject we are particularly fascinated with is the analysis of continuous valued adaptive networks. Although the high dimensional dynamics make this class of systems particularly tricky, they lend themselves to application of elegant methods from algebra and exhibit surprising types of self-organization [13,14].

Applications

Adaptive networks have been widely applied but at least for this lab four applications stand out in particular. Perhaps the premier application of adaptive networks are epidemic dynamics. Our paper in this area [1] inspired many many subsequent works, which used adaptive networks to model social distancing responses to epidemic states of agents. Some of our own subsequent contributions to this field are [12], which showed that adaptive behavior leads can lead to vanishing epidemic thresholds in networks where the degree distribution has a finite second moment, and [15] which showed that a small transient epidemic can leave networks "inocculated" against a subsequent epidemic even if the individual nodes do not retain resistance against the disease.

Another application that is currently getting a lot of attention is neural criticality. Our brains seem to be poised at a transition between two different dynamical regimes. The adaptive self-organization of synapses may explain why the brain manages to stay exactly on this narrow edge on which meaningful information processing is possible. Building on the pioneering work of Bornholdt and Rohlf [2] we formulated the first fairly realistic model of neural self-organization [16] and demonstrated some prediction in data from patients [17]. However, the main focus of the lab has been to explore the underlying dynamical foundations of adaptive self-organization [18,19,20].

Perhaps the biggest problem of our time is the post-truth phenomenon. Here adaptive networks can be used to understand social self-organization processes that lead to the formation to echo chambers. The foundational adaptive network model in this area is the voter model [8,9]. Our main contribution in this area is to demonstrate that a variant of this model describes collective motion in animals [21,22] this contributed to the discovery of new phenomenon that demonstrated in experiments [23].

Apart form the specific application of misinformation there is a wider interest in the adaptive self-organization of social interactions. In particular we used adaptive networks to study the evolution of cooperative behavior and the formation of cooperation networks in common goods games. Among others we showed that a dynamical instability can lead to cooperative behavior in a discrete state model of cooperation [24]. In continuous state models an even richer phenomenology of self-organization emerges where some nodes rise to leadership position due to spontaneous pattern formation [13].

Further information

For further information on adaptive networks check out our review [7] or the adaptive networks book [25].

[1]
Epidemic Dynamics on an Adaptive Network
T Gross, CJ Dommar D’Lima and B Blasius
Phys. Rev. Lett. 96, 208701, 2006
[2]
Topological Evolution of Dynamical Networks: Global Criticality from Local Dynamics
S Bornholdt and T Rohlf
Phys. Rev. Lett. 84, 6114-6117, 2000
[3]
Self-Organized Networks of Competing Boolean Agents
M Paczuski, KE Bassler and A Corral
Phys. Rev. Lett. 84, 3185-3188, 2000
[4]
A dynamic model of social network formation
B Skyrms and R Pemantle
Proceedings of the National Academy of Sciences 97, 9340-9346, 2000
[5]
Cooperation in an Adaptive Network
MG Zimmermann, VM Eguíluz, M San Miguel et al.
Advs. Complex Syst. 03, 283-297, 2011
[6]
The effect of a prudent adaptive behaviour on disease transmission
SV Scarpino, A Allard and L Hébert-Dufresne
Nature Phys 12, 1042-1046, 2016
[7]
Adaptive coevolutionary networks: a review
T Gross and B Blasius
J. R. Soc. Interface. 5, 259-271, 2007
[8]
Nonequilibrium phase transition in the coevolution of networks and opinions
P Holme and MEJ Newman
Phys. Rev. E 74, 056108, 2006
[9]
Generic Absorbing Transition in Coevolution Dynamics
F Vazquez, VM Eguíluz and MS Miguel
Phys. Rev. Lett. 100, 108702, 2008
[10]
Analytical calculation of fragmentation transitions in adaptive networks
GA Böhme and T Gross
Phys. Rev. E 83, 035101, 2011
[11]
Exploring the adaptive voter model dynamics with a mathematical triple jump
H Silk, G Demirel, M Homer et al.
New J. Phys. 16, 093051, 2014
[12]
Dynamics of epidemic diseases on a growing adaptive network
G Demirel, E Barter and T Gross
Sci Rep 7, 42352, 2017
[13]
Patterns of cooperation: fairness and coordination in networks of interacting agents
A Do, L Rudolf and T Gross
New J. Phys. 12, 063023, 2010
[14]
Graphical notation reveals topological stability criteria for collective dynamics in complex networks
A Do, S Boccaletti and T Gross
Phys. Rev. Lett. 108, 194102, 2012
[15]
Network inoculation: Heteroclinics and phase transitions in an epidemic model
H Yang, T Rogers and T Gross
Chaos 26, 083116, 2016
[16]
Adaptive self-organization in a realistic neural network model
C Meisel and T Gross
Phys. Rev. E 80, 061917, 2009
[17]
Failure of Adaptive Self-Organized Criticality during Epileptic Seizure Attacks
C Meisel, A Storch, S Hallmeyer-Elgner et al.
PLoS Comput Biol 8, e1002312, 2012
[18]
Analytical investigation of self-organized criticality in neural networks
F Droste, A Do and T Gross
J. R. Soc. Interface. 10, 20120558, 2013
[19]
Self-organized criticality as a fundamental property of neural systems
J Hesse and T Gross
Front. Syst. Neurosci. 8, 166, 2014
[20]
Not one, but many critical states: A dynamical systems perspective
T Gross
Front. Neural Circuits 15, 614268-7, 2021
[21]
Adaptive-network models of swarm dynamics
C Huepe, G Zschaler, A Do et al.
New J. Phys. 13, 073022, 2011
[22]
Adaptive network models of collective decision making in swarming systems
L Chen, C Huepe and T Gross
Phys. Rev. E 94, 022415, 2016
[23]
Uninformed Individuals Promote Democratic Consensus in Animal Groups
ID Couzin, CC Ioannou, G Demirel et al.
Science 334, 1578-1580, 2011
[24]
A homoclinic route to asymptotic full cooperation in adaptive networks and its failure
G Zschaler, A Traulsen and T Gross
New J. Phys. 12, 093015, 2010
[25]
Adaptive Networks: Theory, Models, and Applications
T Gross and H Sayama
Springer, 2009