Complex networks, which mediate interactions among individuals, play a vital role in shaping dynamics between them[1,2]. For this reason, many studies have been conducted to understand the relationship between the structures of complex networks and the dynamics on these networks[2]. At the same time, the structure of networks constantly change under the influence of the state of the nodes[3-5]. Moreover, the topology of networks not only influences the dynamic processes occurring within them but also evolves in response to the changes in the states of the elements of networks[6-10]. This feedback inherent in adaptive systems fosters a coevolutionary dynamic between nodes' states and network structures, a phenomenon commonly observed in reality. Many studies of coevolving networks attempt to integrate these two facets, focusing on the coevolution of network topology and nodal dynamics[6,8-10]. Research on coevolving networks spans a wide range of contexts, including coevolving voter models[10-14], spin systems[15-17], adaptive epidemic models[8, 18-21], complex contagion models[22], game theoretical models[23,24], Boolean network dynamics[25], and ecological evolution[26,27].

Epidemic models on coevolving networks offer a powerful means to understand the interplay between network topology and disease transmission[7-9]. Traditionally, many studies have investigated the spread of infectious diseases through compartmental epidemic models on static networks[28-31]. However, real-world networks are often adaptive, meaning that the connections between individuals change over time in response to the states of their neighbors[7]. For instance, if an agent identifies an infectious neighbor, that node can reduce its interaction with the infectious one to avoid infection[8]. To model this scenario, an epidemic model that suppresses epidemic spread through link rewiring was proposed[9,19,32]. By considering the coevolution of epidemic spread and network structure, it might provide insights into effective interventions to mitigate the spread of infectious diseases.

Classical epidemic models can represent not only the spread of diseases but also the propagation of information, fads, or opinions[30,33-35]. In disease transmission, the primary focus is often on preventing the spread of the disease[36-38]. However, in the case of information propagation, the focus is on efficiently delivering information to others. Understanding this distinction, instead of employing tactics to hinder propagation, we suggest a strategy that amplify the spread of information via link rewiring. This change leads us to introduce a coevolutionary dynamics model with link rewiring to facilitate information dissemination. The scenario we are considering is as follows: individuals possessing certain information or opinions are motivated to spread that information to a larger fraction of the population. Since the total amount of interactions with other agents might be limited, it is advantageous for information propagation to have more frequent interactions with those who are unaware of the information. In this context, we propose a model in which individuals break ties with those who already possess the information and, instead, establish new links with individuals who do not have the information, so called ‘heterophilic’ link rewiring.

In our study, we derive and analyze moment-closure approximations[8,39] and heterogeneous mean-field approximations[19,28] to explore the coevolutionary dynamics of information propagation. Through this analysis, we show the impact of the heterophilic link rewiring on the spreading dynamics and the evolution of network structures. We found that the epidemic size increases with the increase of the rate of link rewiring, while the epidemic threshold remains insensitive to the process of link rewiring. This suggests that as the network undergoes more frequent rewiring of its connections due to the coevolutionary process, the overall size of the epidemic tends to increase. In addition, we observed a broadening of the degree distribution during the coevolutionary dynamics. We also confirmed that our theoretical frameworks accurately predict all numerical results.

We propose a model of coevolutionary dynamics based on the susceptible-infectious-susceptible (SIS) framework[28,30]. In this model, the structures of networks change to promote information propagation via link rewiring while information spreads into population by following the SIS model. While our model involves information spreading, we retain the terminology of the spread of infectious disease to maintain consistency with previous studies[30]. In our model, nodes can exist in either a susceptible or infectious state. Here, ‘susceptible’ corresponds to a state where nodes do not possess the information. Conversely, ‘infectious’ corresponds to a state where nodes have the information.

Our model consists of three dynamic processes: spreading, recovery, and rewiring (Fig. 1). Spreading and recovery follow the same procedures as in a typical SIS model on networks. Specifically, at each time, infectious nodes infect susceptible neighbors at a rate p. Each infectious node also has a rate r of autonomously returning to a susceptible state, representing the recovery process. In addition to infection and recovery, our model introduces a link rewiring process that forms the basis of the coevolutionary dynamics. At each time, links connecting two infectious nodes are removed at a rate w. Subsequently, one infectious node out of two nodes that used to form a link seeks a new neighbor among the susceptible nodes and forms a new connection. The heterophilic link rewiring process allows the network structure to dynamically respond to the spread of information, leading to an interplay between information dissemination and changes in network topology.

Figure 1. (Color online) Our coevolutionary model consists of three dynamical processes: (a) information spreading occurring at a rate of p, through links connecting susceptible and infectious nodes; (b) link rewiring at a rate of w, which involves removing a link between a pair of infectious nodes and establishing a new link between infectious and susceptible nodes; and (c) recovery at a rate of r, which an infectious node autonomously transitions to a susceptible state.

1. Moment-closure approximation

To investigate the coevolutionary dynamics, we first attempt to derive the time evolution of the densities of susceptible and infectious nodes, denoted as S and I, respectively. By definition, they satisfy the normalization condition S+I=1. When we define the fraction of SI links to the number of nodes N as SI, the evolution of I can be expressed as

where p and r represent the rates of infection and recovery, respectively. As shown in Eq. (1), the fraction of the link SI is required to predict the evolution of both I and S.

We further define the fraction of SS and II links to the number of nodes N as SS and II. The sum of II, SS, and SI satisfies the following condition: lSS+lII+lSI=〈k〉/2, where 〈k〉 represents the average degree. The time evolution of link densities involves the densities of the triplets, for example, the densities of ISI, IIS, SSS, etc, because i-th moments will depend on the (i+1)-th moments. Similarly, higher-order moments are recursively needed in principle, up to infinite order terms.

Here, we employ the moment-closure approximation[8,39] to terminate the recursion. In the following, we explain how to decompose the density of triplets into link densities based on the moment-closure approximations. We begin by approximating the density of triplet ABC, where A, B, and C represent the states of nodes (e.g., S and I in our example). One half of the ABC-triplet is an AB link, which occurs at density AB. The other half is an BC link that share B node with an AB link, that is ABC-triplets. To approximate the number of ABC-triplets, we estimate the number of nodes with state C that are connected to node with state B in AB links. Since we arrived at the node with state B by following a link, the distribution of the expected number of neighbors of that node can be approximated as (k−1)P(k)/〈k〉 where P(k) is the degree distribution of a network, assuming the networks are uncorrelated. Each of these links is a BC-link with probability lBC/(〈k〉B). Then the estimated number of nodes with state C that are connected to node with state B in AB links is 〈k2〉−〈k〉〈k〉2lBCB

In general, 〈k2〉 at a steady state is not known a priori because the degree distribution varies by link rewiring. In this study, we use Erdös-Rényi (ER) graphs as the initial network configuration. On ER graphs, 〈k2〉−〈k〉〈k〉2 is unity in the thermodynamic limit. However, the value changes in time since the rewiring in our model is not entirely random. If we neglect the heterogeneity of the degree distribution caused by the link rewiring, we can assume that this value is approximately 1 regardless of time. Taking the density of AB-link and the probability that they connect to an additional BC-link into account, we obtain an approximation for the density of triples as lABC≈lABlBC/B[8,39].

Based on the approximation, we can derive the time evolution of link densities:

The normalization condition such that lSS+lII+lSI=〈k〉/2 gives the time evolution of SI. The trivial solution of the coupled equations given in Eqs. (1)–(3) at the steady state is (I,lSI,lSS)=(0,0,1), corresponding to the disease-free phase. In this phase, all nodes are in the susceptible state, so that all links are also SS state. The non-trivial solution at the steady state of the equations can be computed as

The non-trivial solution corresponds to the active epidemic phase with a non-zero value of I.

The onset of the epidemic phase can be predicted by the linear stability analysis of the Jacobian matrix of Eqs. (1)–(3). The epidemic threshold is located at where the largest eigenvalue of the Jacobian matrix at (I,lSI,lSS)=(0,0,1) becomes zero. When we apply the linear stability analysis, we arrive at the epidemic threshold as

regardless of the value of w. It implies that the link rewiring process does not change the location of the epidemic threshold, but it affects the steady-state density of infectious nodes.

2. Heterogeneous mean-field approximations

We next derive heterogeneous mean-field (HMF) equations for our model[19]. By using the HMF approximations, we attempt to obtain not only the fraction of infectious nodes but also the network structure that emerges at the steady state. Let Sk,q and Ik,q respectively be the fraction of susceptible and infectious nodes with degree k and the number q of infectious neighbors. Using these defined fractions for different states of nodes, we can derive the differential equations for the susceptible and infectious fractions, Sk,q and Ik,q[19],

where the first moments are defined as

and the second moments are defined as

The meaning of each term in Eqs. (7) and (8) is transparent. The first term of Eq. (7), rIk,q, represents the recovery process from infectious nodes to susceptible nodes. The second term represents the infection process of susceptible nodes through infectious neighbors q with the infection rate p. The third term represents the recovery of infectious neighbors' for susceptible nodes, meaning that Sk,q→Sk,q−1. The fourth term represents the infection of susceptible neighbors' for susceptible nodes, meaning that Sk,q→Sk,q+1. The last term stands for the susceptible nodes which are obtained a new connection through rewiring. Each term in Eq. (8) can be explained similarly. Note that the last term in Eq. (8) corresponds to the breaking of II links and rewiring of SI links.

To calculate the density of susceptible and infectious nodes at the steady state, we solve Eqs. (7,8) by numerical iterations. We can determine the density of susceptible (S) and infectious (I) nodes by summing Sk,q and Ik,q over all possible values of k,q, respectively. That is, the densities of S and I nodes are given by

Additionally, we can obtain the degree distributions for susceptible PS(k) and infectious PI(k) nodes at the steady state. These distributions represent the probability of finding a node with a degree k in the susceptible or infectious state, respectively. We can calculate the degree distributions for susceptible and infectious nodes by summing Sk,q and Ik,q over q, then dividing by the total density of S and I nodes, respectively. The equations for calculating the degree distributions of infectious and susceptible nodes are given by

We investigate the role of the link rewiring in the propagation of information in coevolutionary dynamics. We explore the density I of infectious nodes, which represents the extent of information spread. Figure 2(a) shows the density of infectious nodes as a function of infection rate p for various values of link rewiring rates, w=0,0.02,0.2. We use ER graphs as the initial structure of networks with a size of N=105 and mean degree 〈k〉=20. Our theoretical predictions based on moment-closure approximations show a great agreement with the numerical simulations across different parameter values.

Figure 2. (Color online) The density I of (a) infectious nodes and (b) the fraction lSI of SI links for each node with respect to the infection rate p, with various values of rewiring rate w are shown. The symbols represent numerical simulations obtained with N=105, 〈k〉=20, and r=0.02. The lines represent theoretical predictions based on Eqs. (4,5).

Our results reveal a direct relationship between the size of the epidemic, representing the extent of information spread, and the link rewiring rate w. As the link rewiring rate w increases, the size of the epidemic increases correspondingly. This finding indicates that the more frequent rewiring of links by infectious nodes in search of susceptible neighbors enhances the spread of information. However, the epidemic threshold remains constant with respect to w, as predicted by Eq. (6). It implies that the heterophilic link rewiring has no impact on coevolutionary dynamics when II links do not extensively exist, leading to the result where p_c is independent of w. However, as p exceeds p_c, rewiring plays a role in increasing the fraction of infectious nodes.

We next examine the average fraction SI of SI links, indicating the density of active interactions for information spreading between susceptible and infectious nodes. Figure 2(b) illustrates the behavior of the average fraction SI of SI links. The lines in this figure represent the values of SI obtained from our moment-closure approximations, as given in Eq. (5). The fraction SI remains null below p_c because there are no infectious nodes, but begins to increase at p_c. It exhibits a sharp increase initially, but then starts to decline as the growth of I slows down. In addition, we found that as the link rewiring rate w increases, SI reaches higher values, reflecting the higher density of infectious nodes as w increases.

We show the numerical results of the density I of infectious nodes as a function of w and p in Fig. 3(a) and as a function of 〈k〉 and p in Fig. 3(b). Once again, we found that the epidemic threshold predicted by Eq. (5), denoted in dotted lines in Figs. 3(a,b) matches well with the numerical simulations. Figure 3(a) shows that as the link rewiring rate w increases, the size of the epidemic increases. Figure 3(b) shows that for various values of 〈k〉 the epidemic threshold follows the relation in Eq. (6). We also confirm that while the extent of information spread is sensitive to link rewiring, the epidemic threshold remains unaffected by changes in network topology.

Figure 3. (Color online) The fraction I of infectious nodes with respect to (a) w and p with the mean degree 〈k〉=20 and (b) 〈k〉 and p with w=0.02 are shown. The dashed lines correspond to the epidemic threshold predicted by Eq. (6). The numerical results are obtained with N=105 and r=0.02.

Finally, we study the network structure that emerges at the steady state of the adaptive dynamics. We particularly focus on how the rewiring influences the degree distribution in the network. Figure 4 exhibits the degree distributions of infectious PI(k) and susceptible nodes PS(k) with various values of w=0,0.02,0.2. The theoretical predictions obtained from the HMF approximations denoted by lines in Fig. 3 show a great agreement with numerical results. We found that a higher rewiring rate results in a more heterogeneous degree distribution at the steady state, even though the networks initially share identical structures. When the rewiring rate increases, the fraction of isolated nodes also increases. This is because when an II link is broken, one of the nodes are connected to a susceptible node while the other loses its degree. This implies that increased rewiring rate in coevolutionary dynamics of information spreading can be a source of the heterogeneity of network topology.

Figure 4. (Color online) Degree distribution of (a) infectious nodes PI(k) and (b) susceptible nodes PS(k) at the steady state with various values of w. The numerical results denoted by symbols are averaged over 500 realizations with the parameters N=105, 〈k〉=20, p=0.005 and r=0.02. The analytical predictions denoted by lines are obtained by the HMF.

In this study, we explore coevolutionary dynamics of information spreading that combines network structural changes with spreading dynamics. We use moment-closure approximations and heterogeneous mean-field analysis for the scenario where link rewiring occurs by infectious nodes in search of susceptible neighbors to enhances the spread of information. Our research highlights the impact of link rewiring on information spread dynamics, emphasizing its effects on epidemic size, epidemic threshold, and network structures. We found that that the epidemic size increases with the increase of rewiring rate, but the epidemic threshold remains insensitive to the process of link rewiring. Furthermore, we observe more heterogeneous degree distributions at the steady state as the link rewiring rate increases. Our study presents a coevolutionary spreading model that utilizes link rewiring as a catalyst for both information propagation and a source of the heterogeneity in network topology.

We thank N. Masuda for helpful discussion. This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (no. 2020R1I1A3068803).