$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

16.4: Simulating Adaptive Networks

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

The ﬁnal class of dynamical network models is that of adaptive networks. It is a hybrid of dynamics on and of networks, where states and topologies “co-evolve,” i.e., they interact with each other and keep changing, often over the same time scales. Theword “adaptive” comes from the concept that states and topologies can adapt to each other in a co-evolutionary manner, although adaptation or co-evolution doesn’t have to be biological in this context. Adaptive networks have been much less explored compared to the other two classes of models discussed above, bbut you can ﬁnd many real-world examples of adaptive networks , such as:

Development of an organism. The nodes are the cells and the edges are cell-cell adhesions and intercellular communications. The node states include intracellular gene regulatory and metabolic activities, which are coupled with topological changes caused by cell division, death, and migration.

Self-organization of ecological communities. The nodes are the species and the edges are the ecological relationships (predation, symbiosis, etc.) amongt hem. The node states include population levels and within-species genetic diversities, which are coupled with topological changes caused by invasion, extinction, adaptation, and speciation.

Epidemiological networks. The nodes are the individuals and the edges are the physical contacts among them. The node states include their pathologic states (healthy or sick, infectious or not, etc.), which are coupled with topological changes caused by death, quarantine, and behavioral changes of those individuals.

Evolution of social communities. The nodes are the individuals and the edges are social relationships, conversations, and/or collaborations. The node states include socio-cultural states, political opinions, wealth, and other social properties of those individuals,whicharecoupledwithtopologicalchangescausedbythepeople’sentry into or withdrawal from the community, as well as their behavioral changes.

In these adaptive networks, state transitions of each node and topological transformation of networks are deeply coupled with each other, which could produce characteristic behaviors that are not found in other forms of dynamical network models. As I mentioned earlier in this chapter, I am one of the proponents of this topic , so you should probably take what I say with a pinch of salt. But I ﬁrmly believe that modeling and predicting state-topology co-evolution of adaptive networks has become one of the major critical challenges in complex network research, especially because of the continual ﬂood of temporal network data  that researchers are facing today.

The ﬁeld of adaptive network research is still very young, and thus it is a bit challenging to select “well established” models as classic foundations of this research yet. So instead, I would like to show, with some concrete examples, how you can revise traditional dynamical network models into adaptive ones. You will probably ﬁnd it very easy and straightforward to introduce adaptive network dynamics. There is nothing difﬁcult in simulating adaptive network models, and yet the resulting behaviors may be quite unique and different from those of traditional models. This is deﬁnitely one of those unexplored research areas where your open-minded creativity in model development will yield you much fruit.

Adaptive epidemic model When you ﬁnd out that one of your friends has caught a ﬂu, you will probably not visit his or her room until he or she recovers from the illness. This means that human behavior, in response to the spread of illnesses, can change the topology of social ties, which in turn will inﬂuence the pathways of disease propagation. This is an illustrative example of adaptive network dynamics, which we can implement into the SIS model (Code 16.6) very easily. Here is the additional assumption we will add to the model:

• When a susceptible node ﬁnds its neighbor is infected by the disease, it will sever the edge to the infected node with severance probability $$p_s$$.

This new assumption is inspired by a pioneering adaptive network model of epidemic dynamics proposed by my collaborator Thilo Gross and his colleagues in 2006 . They assumed that the edge from the susceptible to the infected nodes would be rewired to another susceptible node in order to keep the number of edges constant. But here, we assume that such edges can just be removed for simplicity. For your convenience, Code 16.6 for the SIS model is shown below again. Can you see where you can/should implement this new edge removal assumption in this code? There are several different ways to implement adaptive edge removal in this code. An easy option would be just to insert another if statement to decide whether to cut the edge right before simulating the infection of the disease (third-to-last line). For example:  Note that we now have one more probability, p_s, with which the susceptible node can sever the edge connecting itself to an infected neighbor. Since this simulation is implemented using an asynchronous state updating scheme, we can directly remove the edge (a, b) from the network as soon as node a decides to cut it. Such asynchronous updating is particularly suitable for simulating adaptive network dynamics in general.

By the way, there is a minor bug in the code above. Because there is a possibility for the edges to be removed from the network, some nodes may eventually lose all of their neighbors. If this happens, the rd.choice(g.neighbors(a)) function causes an error. To avoid this problem, we need to check if node a’s degree is positive. Below is a slightly corrected code:  If you run this code, the result will probably look quite similar to the original SIS model, because the parameter settings used in this code ($$p_{i} = p_{r} = 0.5$$) don’t cause a pandemic. But if you try different parameter settings that would cause a pandemic in the original SIS model (say, $$p_{i} = 0.5$$, $$p_{r} = 0.2$$), the effect of the adaptive edge removal is much more salient. Figure 16.4.1 shows a sample simulation result, where pandemic-causing parameter values ($$p_{i} = 0.5$$, $$p_{r} = 0.2$$) were used, but the edge severance probability $$p_{s}$$ was also set to 0.5. Initially, the disease spreads throughout the network, but adaptive edge removal gradually removes edges from the network as an adaptive response to the pandemic, lowering the edge density and thus making it more and more difﬁcult for the disease to spread. Eventually, the disease is eradicated when the edge density of the network hits a critical value below which the disease can no longer survive. Figure $$\PageIndex{1}$$: Visual output of Code 16.15, with varied parameter settings ($$p_{i} = 0.5$$, $$p_{r} = 0.2$$, $$p_{s} = 0.5$$). Time ﬂows from left to right.

Exercise $$\PageIndex{1}$$

Conduct simulations of the adaptive SIS model on a random network of a larger size with $$p_{i} = 0.5$$ and $$p_{r} = 0.2$$, while varying ps systematically. Determine the condition in which a pandemic will eventually be eradicated. Then try the same simulation on different network topologies (e.g, small-world, scale-free networks) and compare the results.

Exercise $$\PageIndex{2}$$

Implement a similar edge removal rule in the voter model so that an edge between two nodes that have opposite opinions can be removed probabilistically. Then conduct simulations with various edge severance probabilities to see how the consensus formation process is affected by the adaptive edge removal.

Adaptive diffusion model The ﬁnal example in this chapter is the adaptive network version of the continuous state/time diffusion model, where the weight of a social tie can be strengthened or weakened according to the difference of the node states across the edge. This new assumption represents a simpliﬁed form of homophily, an empirically observed sociological fact that people tend to connect those who are similar to themselves. In contrast, the diffusion of node states can be considered a model of social contagion, another empirically observed sociological fact that people tend to become more similar to their social neighbors over time. There has been a lot of debate going on about which mechanism, homophily or social contagion, is more dominant in shaping the structure of social networks. This adaptive diffusion model attempts to combine these two mechanisms to investigate their subtle balance via computer simulations.

This example is actually inspired by an adaptive network model of a corporate merger that my collaborator Junichi Yamanoi and I presented recently . We studied the conditions for two ﬁrms that recently underwent a merger to successfully assimilate and integrate their corporate cultures into a single, uniﬁed identity. The original model was a bit complex agent-based model that involved asymmetric edges, multi-dimensional state space, and stochastic decision making, so here we use a more simpliﬁed, deterministic, differential equation-based version. Here are the model assumptions:

• The network is initially made of two groups of nodes with two distinct cultural/ideological states.

• Each edge is undirected and has a weight, $$w ∈ [0,1]$$, which represents the strength of the connection. Weights are initially set to 0.5 for all the edges.

• The diffusion of the node states occurs according to the following equation:

$\frac{dc_{i}}{dt} =\alpha{\sum{(c_{j}-c_{i})w_{ij}}_{j\epsilon{N_{i}}}}\label{(16.18)}$

Here $$α$$ is the diffusion constant and$$w_{ij}$$ is the weight of the edge between node $$i$$ and node $$j$$. The inclusion of $$w_{ij}$$ signiﬁes that diffusion takes place faster through edges with greater weights.

• In the meantime, each edge also changes its weight dynamically, according to the following equation:
$\frac{dw_{ij}}{dt} =\beta{w_{ij}}(1-w_{ij})(1-\gamma{ \ |{c_{i}-c_{j}}}|)\label{(16.19)}$

Here $$β$$ is the rate of adaptive edge weight change, and $$γ$$ is a parameter that determines how intolerant, or “picky,” each node is regarding cultural difference. For example, if $$γ = 0$$, $$w_{ij}$$ always converges and stays at 1. But if $$γ$$ is large (typically much larger than 1), the two nodes need to have very similar cultural states in order to maintain an edge between them, or otherwise the edge weight decreases. The inclusion of $$w_{ij}(1−w_{ij})$$ is to conﬁne the weight values to the range $$[0,1]$$ dynamically.

So, to simulate this model, we need a network made of two distinct groups. And this is the perfect moment to disclose a little more secrets about our favorite Karate Club graph (unless you have found it yourself already)! See the node attribute of the Karate Club graph, and you will ﬁnd the following:  Each node has an additional property, called ’club’, and its values are either ’Mr. Hi’ or ’Officer’! What are these?

The truth is, when Wayne Zachary studied this Karate Club, there was an intense political/ideological conﬂict between two factions. One was Mr. Hi, a part-time karate instructor hired by the club, and his supporters, while the other was the club president (Ofﬁcer) John A., other ofﬁcers, and their followers. They were in sharp conﬂict over the price of karate lessons. Mr. Hi wanted to raise the price, while the club president wanted to keep the price as it was. The conﬂict was so intense that the club eventually ﬁred Mr. Hi, resulting in a ﬁssion of the club into two. The Karate Club graph is a snapshot of the club members’ friendship network right before this ﬁssion, and therefore, each node comes with an attribute showing whether he or she was in Mr. Hi’s camp or the Ofﬁcer’s camp. If you are interested in more details of this, you should read Zachary’s original paper , which contains some more interesting stories.

his data looks perfect for our modeling purpose. We can set up the initialize function using this ’club’ property to assign binary states to the nodes. The implementation of dynamical equations are straightforward; we just need to discretize time and simulate them just as a discrete-time model, as we did before. Here is a completed code:     In the initialize function, the edge weights are all initialized as 0.5, while node states are set to 1 if the node belongs to Mr. Hi’s faction, or 0 otherwise. There are also some modiﬁcations made to the observe function. Since the edges carry weights, we should color each edge in a different gray level. Therefore additional options(edge_color, edge_cmap, edge_vmin, and edge_vmax) were used to draw the edges in different colors. The update function is pretty straightforward, I hope.

Figure 16.4.1 shows the simulation result with $$α = 1$$, $$β = 3$$, $$γ = 3$$. With this setting, unfortunately, the edge weights became weaker and weaker between the two political factions (while they became stronger within each), and the Karate Club was eventually split into two, which was what actually happened. In the meantime, we can also see that there were some cultural/ideological diffusion taking place across the two factions, because their colors became a little more gray-ish than at the beginning. So, there was apparently a competition not just between the two factions, but also between the two different dynamics: social assimilation and fragmentation. History has shown that the fragmentation won in the actual Karate Club case, but we can explore the parameter space of this model to see if there was any alternative future possible for the Karate Club!

Exercise $$\PageIndex{3}$$

Examine, by simulations, the sensitivity of the Karate Club adaptive diffusion model on the initial node state assignments. Can a different node Figure $$\PageIndex{2}$$: Visual output of Code 16.17. Time ﬂows from left to right.

state assignment (with the same numbers of 0’s and 1’s) prevent the ﬁssion of the Club? If so, what are the effective strategies to assign the node states?

Exercise $$\PageIndex{4}$$

Conduct simulations of the Karate Club adaptive diffusion model (with the original node state assignment) by systematically varying α, β, and γ, to ﬁnd the parameter settings with which homogenization of the node states can be achieved. Then think about what kind of actions the members of the Karate Club could have taken to achieve those parameter values in a real-world setting, in order to avoid the fragmentation of the Club.