Ex) Article Title, Author, Keywords
New Phys.: Sae Mulli 2023; 73: 886-892
Published online October 31, 2023 https://doi.org/10.3938/NPSM.73.886
Copyright © New Physics: Sae Mulli.
Jeehye Choi1, Byungjoon Min1,2*
1Research Institute for Nanoscale Science and Technology, Chungbuk National University, Cheongju 28644, Korea
2Department of Physics, Chungbuk National University, Cheongju 28644, Korea
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/licenses/by-nc/3.0) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
In many complex systems, the dynamic processes that take place on a network and the changes in the network topology are intertwined. Here, we propose a model of coevolutionary dynamics of information spreading which is accompanied with link rewiring to facilitate the propagation of information. In our model, nodes possessing information attempt to contact new susceptible nodes through the link rewiring while the information spreads on a network. Using moment-closure and heterogeneous mean-ﬁeld approximations, we examine both the information spread dynamics and network evolution focusing on epidemic size, epidemic threshold, and degree distributions at the steady state. We found that more frequent heterophilic link rewiring leads to a larger epidemic size but does not alter the epidemic threshold. We also observed that link rewiring results in a broader degree distribution in the steady state. This study provides an insight into the the role of the heterophilic link rewiring in both facilitating information propagation and inducing network heterogeneity.
Keywords: Coevolution, Link rewiring
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. 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, game theoretical models[23,24], Boolean network dynamics, 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. For instance, if an agent identifies an infectious neighbor, that node can reduce its interaction with the infectious one to avoid infection. 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. 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.
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
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:
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
Based on the approximation, we can derive the time evolution of link densities:
The normalization condition such that
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
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.
We next derive heterogeneous mean-field (HMF) equations for our model. 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
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),
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
Additionally, we can obtain the degree distributions for susceptible
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
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 pc is independent of w. However, as p exceeds pc, 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 pc because there are no infectious nodes, but begins to increase at pc. 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
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
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).