# Information Spreading on Activity-Driven Temporal Networks with Two-Step Memory

Authors: Linfeng Zhong; Xiaoyu Xue; Yu Bai; Jin Huang; Qing Cheng; Longyang Huang; Weijun Pan
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

Information spreading dynamics on the temporal network is a hot topic in the field of network science. In this paper, we propose an information spreading model on an activity-driven temporal network, in which a node is accepting the information dependents on the cumulatively received pieces of information in its recent two steps. With a generalized Markovian approach, we analyzed the information spreading size, and revealed that network temporality might suppress or promote the information spreading, which is determined by the information transmission probability. Besides, the system exists a critical mass, below which the information cannot globally outbreak, and above which the information outbreak size does not change with the initial seed size. Our theory can qualitatively well predict the numerical simulations.


---

## Body

## 1. Introduction

Information spreading on social networks is a hot topic in the fields of network science, computer science, and physics [1–9]. Research studies wish to know the evolutionary mechanisms and diffusion laws of the information, and further design some effective measure to control the information spreading. Using the massive real-data, researchers revealed many important evolution mechanisms, such as social reinforcement effect and memory effect [10–12]. To include those important evolution mechanisms into the information spreading dynamics, scholars proposed some successful models [13–18]. For instance, Watts [19] generalized the threshold model to complex networks, and revealed that the information spreading size first increases then decreases with the average degree of the network.With these proposed mathematical models, the important question is how the network topologies affect the spreading dynamics. The studies in this topic can be divided into three aspects according to the complexity of the network. The first one is the effects of static networks. For static networks, research studies addressed the influences of the degree distribution, weight distribution, and community on the information spreading [20–26]. An important conclusion is that a small fraction of nodes with large degrees makes the information outbreak with any values of information transmission probability [27, 28]. In reality, individuals can transmit the information through more than one communication channel. Therefore, using the multiplex networks describes the real-world network more accurately [29–32], which is the second aspect. Research studies revealed that the network multiplexity could suppress or promote the information spreading, which depends on the interaction between two networks [33–36]. The third aspect is that the effects of temporal network [37–42] on information spreading, since the nodes and connections do not always exist. Scholtes et al. [43] revealed that the spreading dynamics might speed up and slow down the information spreading on non-Markovian temporal networks. Wang et al. [44] proposed a heuristic method immunization strategy for information spreading on the temporal network.To our best knowledge, when including the reinforcement and memory effect into the information spreading model, the study about the effects of network temporality on information spreading dynamics is still lacking. To this end, we propose an information spreading model, in which a node is accepting the information when its cumulative received information in the recent two steps is more significant than a threshold in Section2. With a generalized Markovian approach, we analyze the information spreading size in Section 3. Moreover, we perform extensive numerical simulations on activity-driven temporal networks in Section 4.


## 2. Model

In this section, we introduce the information spreading on temporal networks with two-step memory.


### 2.1. Activity-Driven Network

We first introduce the activity-driven temporal networkG=G1,…,Gtmax which is proposed by Perra et al. [45–47], where tmax is the maximum time step. We set tmax=100 in this paper. The activity-driven network is build according to the following three steps for a given network size N. (i) For each node i, a potential activity xi is assigned according to a given distribution fx. In this paper, we assume that fx follows a power-law distribution. Specifically, fx=ϱx−γe, where γe is an exponent of potential activity distribution, and ϱ=∑xx−γe, ɛ≤x<1. In numerical simulations, we set ɛ=0.001. The larger the value of γe, the more homogeneous of potential activity, which induces the more homogeneous of degree distribution. (ii) At time step, we generate a temporal network Gt. Each node i becomes active with probability ai=ηxi, where η is a parameter. If node i becomes active, it will connect m nodes randomly. Otherwise, node i can only receive other connections. (iii) At the end of time step t, all edges are deleted. We repeated steps (i)–(iii) until t=tmax. According to the above three steps, the average degree of network Gt is kt=2mηɛγe−1/γe−2. By adjusting the values of η, ɛ, and m, we can set the average degree of network Gt.


### 2.2. Information Spreading Model

In this subsection, we introduce a novel information spreading model in which each node can remember the pieces of information it received in recent two steps. The information spreading dynamics is described by a generalized susceptible-infected-susceptible (SIS) model. A node in the susceptible state means that it had not accepted or believed the truth of the information but may accept it when its misgivings were eliminated. A node in the infected state means that it has accepted the information and is willing to share it with neighbors. To include the willingness to accept the information, we introduce an adoption threshold ofθ; the higher the value of θ, the less willing to accept the information. In what follows, we introduce how the information is spreading on activity-driven temporal networks.Initially, we randomly selectp fraction of nodes in the infected state, and the remaining 1−p nodes in the susceptible state and every node do not obtain any pieces of information, i.e., mit=0=0. At each time step t, every infected node i tries to transmit the information to its every susceptible neighbor on network Gt, e.g., node j, with probability λ. If node j received the information, its received accumulated pieces of information become mj⟵mj+1. When node j received enough pieces of information from infected neighbors in recent steps, i.e., mjt−1+mjt≥θ, node j becomes infected. Since every node can only remember the recent two-step memory about its accumulated, we here call our model as “two-step-memory” (TSM)-based information spreading. The infected node i recovers with probability γ and returns to a susceptible state. Note that when t=tmax, the next time step is t=0. The information spreading dynamics evolves until there are no nodes in the infected state, or the time step reaches tf=1000.


## 2.1. Activity-Driven Network

We first introduce the activity-driven temporal networkG=G1,…,Gtmax which is proposed by Perra et al. [45–47], where tmax is the maximum time step. We set tmax=100 in this paper. The activity-driven network is build according to the following three steps for a given network size N. (i) For each node i, a potential activity xi is assigned according to a given distribution fx. In this paper, we assume that fx follows a power-law distribution. Specifically, fx=ϱx−γe, where γe is an exponent of potential activity distribution, and ϱ=∑xx−γe, ɛ≤x<1. In numerical simulations, we set ɛ=0.001. The larger the value of γe, the more homogeneous of potential activity, which induces the more homogeneous of degree distribution. (ii) At time step, we generate a temporal network Gt. Each node i becomes active with probability ai=ηxi, where η is a parameter. If node i becomes active, it will connect m nodes randomly. Otherwise, node i can only receive other connections. (iii) At the end of time step t, all edges are deleted. We repeated steps (i)–(iii) until t=tmax. According to the above three steps, the average degree of network Gt is kt=2mηɛγe−1/γe−2. By adjusting the values of η, ɛ, and m, we can set the average degree of network Gt.


## 2.2. Information Spreading Model

In this subsection, we introduce a novel information spreading model in which each node can remember the pieces of information it received in recent two steps. The information spreading dynamics is described by a generalized susceptible-infected-susceptible (SIS) model. A node in the susceptible state means that it had not accepted or believed the truth of the information but may accept it when its misgivings were eliminated. A node in the infected state means that it has accepted the information and is willing to share it with neighbors. To include the willingness to accept the information, we introduce an adoption threshold ofθ; the higher the value of θ, the less willing to accept the information. In what follows, we introduce how the information is spreading on activity-driven temporal networks.Initially, we randomly selectp fraction of nodes in the infected state, and the remaining 1−p nodes in the susceptible state and every node do not obtain any pieces of information, i.e., mit=0=0. At each time step t, every infected node i tries to transmit the information to its every susceptible neighbor on network Gt, e.g., node j, with probability λ. If node j received the information, its received accumulated pieces of information become mj⟵mj+1. When node j received enough pieces of information from infected neighbors in recent steps, i.e., mjt−1+mjt≥θ, node j becomes infected. Since every node can only remember the recent two-step memory about its accumulated, we here call our model as “two-step-memory” (TSM)-based information spreading. The infected node i recovers with probability γ and returns to a susceptible state. Note that when t=tmax, the next time step is t=0. The information spreading dynamics evolves until there are no nodes in the infected state, or the time step reaches tf=1000.


## 3. Theory

In this section, we propose a generalized discrete Markovian approach [44, 48–50] to steady the TSM-based information spreading dynamics on activity-driven temporal networks. In the theory, we assume that every node transmitting the information to susceptible is independent. As a result, the dynamical correlations among the state of neighbors are neglected.Thepit is denoted as the probability that node i is in the infected state at time t, and 1−pit is denoted as the probability of node i is in the susceptible state. For a susceptible node j, it becomes infected state at time t only when its received accumulated pieces of information in time steps t and t−1 are larger than the threshold θ. qjnt is denoted as the probability of the node j obtaining n pieces of information from infected neighbors at time t simultaneously on the network Gt. To compute the value of qjnt, we should consider three aspects: (i) select n neighbors from the neighbor set ∂j of node i, and denote the subset as Θ. (ii) Every node in Θ transmits the information to node j with probability ∏ℓ∈Θλpℓt. (iii) Each node in the set ∂j/Θ does not transmit the information to node j. Combining the above three aspects, we obtain the expression of qjnt as(1)qjnt=∑Θ⊆∂j,Θ=n∏ℓ∈Θλpℓt∏h∈∂j/Θ1−λpht,where Θ represents the number of elements in set Θ. Once we know the expression of pit, we obtain the value of qjnt.To compute the value ofpit, we should consider two aspects. On the one hand, node i is in the infected state at time t−1 but does not recover at time t. The probability of this event is pit−11−γ. On the other hand, node i is in the susceptible state at time t−1, and we obtained more than θ pieces of information at time steps t−1 and t with probability:(2)Γit=1−pit−11−∑n=0θ−1Qint,where Qint represents that node i received at most θ−1 pieces of information from neighbors at time t−1 and t. The expression of Qint is(3)Qint=∑m=0nqimt−1qin−mt.Considering the above two aspects, we obtain the evolution ofpit as(4)pit=pit−11−γ+1−pit−11−∑n=0θ−1Qint.Averaging all values ofpit, we obtain the probability that a node is randomly selected in the infected state at time t as(5)ρt=1N∑i=1Npit.In the steady-state, the fraction of nodes in the infected state can be denoted asρ for simplicity.According to equation (4), the nonlinearity of the system makes us hardly obtain an analytical threshold. Therefore, we locate the threshold of the system by using the following method: observing the peak of Δρ, which defines as(6)Δρ=ρλ+δλ−ρλ,where ρλ is the information outbreak size with information transmission probability λ, and δλ is a small increment of λ. At the threshold point, Δρ reaches its maximum value [51].The above theoretical derivation is for the information spreading dynamics on temporal networks. When studying the spreading dynamics on static networks, we only need to setGt=Gt′ for t≠t′.


## 4. Results

In this section, we will perform extensive numerical simulations on the activity-driven temporal networks and their corresponding static networks. To build the static network, we only need to generate networkG1 and set the remaining temporal network equal to network G1. All numerical simulation results presented in this paper are averaged over 500 times.In Figure1, we first investigate the information spreading size ρ on both temporal and static networks for a given average degree kt=10. We focus on the following three aspects. (i) How the temporal network affects the information spreading? We reveal two distinct results. For small values of λ, the temporal network structure suppresses the information spreading since the network connectivity is small than that in its corresponding static networks. However, when λ is very large, the temporal network structure promoting the information spreading since a node in a temporal network can connect more distinct nodes. We note that the results are not affected by the initial seed size of p and γe. (ii) The phase transition of the system is the second point we will discuss. We find that the system always exhibits a hysteresis loop. Specifically, the spreading size ρ depends on the initial seed size p between the invasion threshold λinv and persistence threshold λpre [52]. The two threshold points can be located by using equation (6). (iii) The third point we investigate in Figure 1 is how γe affects ρ. We find that ρ increases with γe on both temporal and static networks. That is to say, the more homogeneous the degree distribution of the network, the less robust of the network for information spreading. The theoretical predictions agree well with the numerical simulation results. The differences between the theoretical and numerical predictions are induced by the strong dynamical correlations among the states among neighbors.Figure 1
Information spreading on activity-driven networks and the corresponding static networks. The information spreading sizeρ in the steady-state versus the information transmission probability λ with potential distribution exponent: (a) γe=2.1, (b) γe=3.0, and (c) γe=3.5 with adoption threshold θ=2. ρ is a function of λ with (d) γe=2.1, (e) γe=3.0, and (f) γe=3.5 with θ=3. Other parameters are set to be m=50, γ=0.2, kt=10, and N=200. The lines are theoretical predictions according to equations (1)–(5), and symbols are average values of numerical predictions. The shadow represents the standard deviations of numerical simulations. In each subfigure, the lines and symbols in the same color have the same parameter.
(a)(b)(c)(d)(e)(f)We further investigate the effects of initial seed sizep on the information spreading dynamics in Figure 2. For any values of θ and λ, there is a finite value of critical mass pc, below which the information cannot outbreak globally and above which the information outbreak size does not change with p. For the effects of network temporality, there have two situations. When θ=2, the network temporality suppresses the information spreading for small values of λ, e.g., λ=0.2. However, when θ=3, the network temporality always promotes the information spreading regardless of the value of λ. Our suggested theory can qualitatively describe the above phenomena.Figure 2
Information spreading on activity-driven networks and the corresponding static networks. The information spreading sizeρ versus initial seed size p with potential distribution exponent (a) γe=2.1, (b) γe=3.0, and (c) γe=3.5 with adoption threshold θ=2. ρ versus p with (d) γe=2.1, (e) γe=3.0, and (f) γe=3.5 with θ=3. Other parameters are set to be m=50, γ=0.2, kt=10, and N=200. The lines are theoretical predictions, and symbols are average values of numerical predictions. The shadow represents the standard deviations of numerical simulations. In each subfigure, the lines and symbols in the same color have the same parameter.
(a)(b)(c)(d)(e)(f)


## 5. Conclusions

In this paper, we study the information spreading dynamics on activity-driven temporal networks. To study the effects of network temporality on information spreading, we first proposed an information spreading model, which assumes that a node accepting the information depends on the cumulatively received pieces of information from neighbors in the recent two steps. Then, we developed a generalized Markovian approach to describe the information spreading dynamics, and gave the expression of the information outbreak size. By performing extensive numerical simulations, we found that network temporality may suppress and promote the spreading of information. Specifically, the network temporality suppresses the information spreading for small values of information transmission probability, while promoting the information spreading for large values of information transmission probability. Finally, we found that the system has a critical mass. When the initial seed size is smaller than the critical mass, the information cannot outbreak globally. When the initial size is larger than the critical mass, the information spreading size does not change with the initial seed size values. Our presented results help us understand the effects of network temporality on information spreading dynamics. And the results can also help us analyze the traffic of the complex dynamic aviation network.



---

*Source: 4506012-2021-01-16.xml*