# Effect of Heterogeneity of Vertex Activation on Epidemic Spreading in Temporal Networks

Authors: Yixin Zhu; Dongfen Li; Wenqiang Guo; Fengli Zhang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Development of sensor technologies and the prevalence of electronic communication services provide us with a huge amount of data on human communication behavior, including face-to-face conversations, e-mail exchanges, phone calls, message exchanges, and other types of interactions in various online forums. These indirect or direct interactions form potential bridges of the virus spread. For a long time, the study of virus spread is based on the aggregate static network. However, the interaction patterns containing diverse temporal properties may affect dynamic processes as much as the network topology does. Some empirical studies show that the activation time and duration of vertices and links are highly heterogeneous, which means intense activity may be followed by longer intervals of inactivity. We take heterogeneous distribution of the node interactivation time as the research background to build an asynchronous communication model. The two sides of the communication do not have to be active at the same time. One derives the threshold of virus spreading on the communication mode and analyzes the reason the heterogeneous distribution of the vertex interactivation time suppresses the spread of virus. At last, the analysis and results from the model are verified on the BA network.


---

## Body

## 1. Introduction

The network topology which is formed by the interaction between individuals plays a fundamental role in the process of determining the epidemic spread [1–6]. The original study of epidemiology [7] is based on homogeneous mixing hypothesis, assuming that all people have the same opportunity to contact other individuals in the populations. The assumption and the corresponding results were challenged by empirical studies. The interactions in the populations can use a meaningful network structure to better describe [8]. A large number of empirical studies show that the node degree distribution in many of reality networks obeys heavy-tailed power-law distribution, which is conducive to the spread of virus.Communication between individuals is the basis of the human society. Nowadays technology, such as sensor devices and online communication services, provides us with a large number of records of interaction between individuals, including face-to-face meetings, e-mail, and telephone communication [9–11]. A traditional way to describe these data is to represent them as an aggregate static network, in which an edge is established if interaction between the two ends of it took place at least once [8].Another richer representation of this type of data is the temporal network model [12–21], in which the connection between two nodes only exists at the time of an event. A large number of these data usually consist of a sequence of interactive events. Every event is a triplet, that is, the IDs of two individuals involved in the event and the time of the event. Some studies of the temporal network focused on the impact of interevent time bursty on the spread of information or virus.However, many human interactions are not always face-to-face or synchronous communication mode, such as e-mail exchange, short message, Twitter, and WeChat. Not all sent information can be accepted by the recipient, such as the recipient refusing to open a suspicious mail or refusing to click the link received. When a nodei sends a message to another node j at the time t
1, node j in its active time t
2 decides whether to accept this message, where t
1
<
t
2. What effect does the heterogeneous distribution of individual interactivation time have on the asynchronous information transmission and virus propagation and how does the heterogeneous behavior pattern of individuals impact on asynchronous transmission? These issues are worthy of attention and research.


## 2. Model

In some temporal network literature, any two active nodes are likely to build a temporal edge. But the reality is that the neighbor nodes of a node are at a certain scope. The various factors decide the range of an individual contact, such as geographical areas of individual activity, the social circle of individual life and learning, kinship, and hobby. These links are established between one node and each of its possible interaction nodes, which constitutes a static aggregation network to descript node activity range. The network is denoted byG. An e-mail exchange system, for example, can constitute a static network, which its nodes are formed by e-mail account address in system and edges are established between each e-mail user and users of his or her e-mail address list. So in the network, the vast majority of activities are carried out between the adjacent nodes. When a node is activated, it can interact with its neighbors rather than any other node in the network. The static network topology and node activation sequence properties affect the spread behavior on networks together.The mathematical epidemiological model that is probably the most widely used for theorizing about and emulating epidemics is the so-called SIR (susceptible-infected-recovered) model. In the SIR model, with which we are concerned in the present report, each individual belongs to either an S (susceptible), I (infected), or R (recovered) state at any given time. When a susceptible individual contacts an infected individual, the former may be infected at an infection rate.In our model, an action of an individual, such as sending a short message or receiving an e-mail, is called an activation event of the node. There is a difference in meaning between the interactivation time of a node and the interevent time of an edge. The former is based on the behavior of an individual and the latter is based on the interaction between two individuals.In the model of the bursts of node interactivation time from recent literature [19], at each time point, an activated node chooses randomly another activated node to build an edge between them. If one of the two nodes is I state node and the other is S state node, the I state node will infect the S state node with some probability. Clearly, the model and the previous models have one thing in common, that is, the synchronous interaction, such as phone call, video meeting, and real-time files. However, many cases are closer to the asynchronous communication, such as e-mail exchange, SMS, Twitter, BBS, and other network communication ways, which the two sides of the communication can be active at different times. At each time t, each active node in the model can accept from neighboring nodes some information or send some information to a neighbor. In reality, user may send or receive a group of information to or from more users at the same time. For simplicity, as long as the time scale is small enough, it can be considered that information is only sent to one of its adjacent nodes from an activated node at a time.In our model, all nodes are S state at initial moment except for a nodei which is I state. When the initial infected node i is activated, it chooses randomly one of its neighbor nodes j and sends node j a message containing infection content no matter whether node j is currently activated. Then the node i becomes inactive state at the next time. At each time t, every activated node i will accept one or more messages containing virus in accordance with a certain probability for each message of them and then change from S state to I state at the next moment if it has received messages containing virus sent from its neighbor nodes and the node i is S state before time t. If the activated node i is I state, it will choose a neighbor from some address book, such as e-mail address book, the telephone communication book, or MSN friends list, to send a message containing virus. At each time t, an infected node recovers to R state with some probability.If an S state node receive messages containing viruses from other nodes, it is at the risk of infection. To facilitate the narrative of node state transition in the model, we introduce a new state, which is denoted by D (dangerous). An S state node change into a D state node. When it receive the message containing virus. When a D state node is activated, it has the potential to accept this suspicious message and then its state changes from D to I.As shown in Figure1, each activated node i is subject to the following rules at each time t.(1)
If the nodei is I state, it sends a message containing viruses to its neighbor node j randomly chosen. If the node j is S state at present, it becomes D state at the next moment t
+
1; if the node j is D state, I state, or R state, it will maintain the current state.
(2)
If the nodei is D state, that is, it received one or more messages containing viruses from neighbors at some point t
′
(
t
′
<
t
), it turns into I state if it accepted the message with probability β, in which the transmission time delay is t
-
t
′; it recovers to S state if it refuses to accept the message with probability 1
-
β.
(3)
If the nodei is in the S state or R state, any action from it will not be considered. The sent message that does not contain virus does not affect the propagation process of virus and therefore is not considered in the model.
At each timet, no matter whether the node i is activated, it is subject to the following rule:
(4)
if it is I state node, it will be restored to R state with probabilityμ.Figure 1
A typical drawing of nodes state transition of the asynchronous communication model.In the second point, we assume that if a user saw the suspicious messages, suspicious information, or suspicious links and refused to accept them for the first time, then he or she will never accept them. So, the corresponding node state can be changed into S state from D state at the next moment.In many types of empirical data, a wide range of patterns of human activity are known to exhibit long-tailed dynamics [22–24]. Here, we model the node interactivation time heavy-tailed distribution with the power law distribution. Node interactivation time τ obeys power-law distribution with lower bound [25]:
(1)
P
(
τ
)
=
α
-
1
τ
min
⁡
(
τ
τ
min
⁡
)
-
α
,
where τ
min
⁡ is a lower bound of node interactivation time τ and α is the exponent or scaling parameter of the power-law distribution.


## 3. Epidemic Threshold

Key quantities for epidemic dynamics are the so-called transmissibilityT and the secondary reproductive number R [26]. T is the probability that an infected individual would transmit virus to a susceptible neighbor before it recovers, and R is the expected number of new nodes infected by infected nodes.An infected node is restored into recovered state within a time step with the probability ofμ, which obeys the binomial distribution of the mean for 1
/
μ. So the average time that an infected node of network changes into a recovered node is 1
/
μ. When an infected node is activated, it will randomly select its neighborhood to send information containing virus. The neighbor accepts the information at some futural time with probability of β and will be infected as a consequence if it was previously S state. The interactivation time τ for each node of network is subject to identically independent distribution. According to the theory of update [27], the transmissibility T for the dynamics can be obtained as
(2)
T
=
β
μ
∫
0
1
/
μ
g
(
Δ
)
d
Δ
=
β
μ
(
1
-
∫
1
/
μ
∞
g
(
Δ
)
d
Δ
)
,
where g
(
Δ
)
=
(
1
/
〈
τ
〉
)
∫
Δ
∞
P
(
τ
)
d
τ, g
(
Δ
) is to generate time distribution [28], 〈
τ
〉 is the mean of node interactivation time, and P
(
τ
) is the density distribution function of node interactivation time τ. Where the node interactivation time τ obeys power-law distribution with exponent α, given by (1), transmissibility T can be written as
(3)
T
=
{
β
μ
(
α
-
2
)
(
α
-
1
)
1
μ
τ
min
⁡
,
1
μ
≤
τ
min
⁡
β
μ
[
1
-
(
μ
τ
min
⁡
)
α
-
2
(
α
-
1
)
]
,
1
μ
>
τ
min
⁡
.When we arrive at a node by following a random chosen edge, the number of remaining edges of the node excluding we along is denoted byk
′. When a node i is infected by its neighbor node j, node i selects randomly one of its neighbor nodes as the spread object and the probability that the selected node is not node j is k
′
/
(
k
′
+
1
). Thus the reproductive number R equals T
〈
k
′
〉
/
(
〈
k
′
〉
+
1
) in our model, where 〈
k
′
〉 is the average remaining degree of network nodes. It can be expressed by node average degree 〈
k
〉 and the second moment of node degrees 〈
k
2
〉 [26, 29]; that is, 〈
k
′
〉
=
(
〈
k
2
〉
-
〈
k
〉
)
/
〈
k
〉. Hence the reproductive number R
=
T
(
〈
k
2
〉
-
〈
k
〉
)
/
〈
k
2
〉. A necessary condition for virus epidemic on network is that the reproductive number R must be greater than one; combined with (3), we can obtain the epidemic threshold as (for derivation see the Appendix)
(4)
λ
c
=
{
C
μ
τ
min
⁡
(
α
-
1
)
(
α
-
2
)
,
1
μ
≤
τ
min
⁡
C
[
1
-
(
μ
τ
min
⁡
)
α
-
2
(
α
-
1
)
]
-
1
,
1
μ
>
τ
min
⁡
,
where λ
≡
β
/
μ, which is the effective transmission rate of virus, λ
c is epidemic threshold, and C
=
〈
k
2
〉
/
(
〈
k
2
〉
-
〈
k
〉
). Parameter C is only related to the structure of the static network G and has nothing to do with the dynamic activation properties of nodes.


## 4. Results and Analysis

Under the condition of nodes dynamic activation, the characteristics of the epidemic threshold of virus are analyzed firstly. BA network [30] is in a typical heterogeneous structure network. Each new node connects m existing nodes of the network and the final total number of the network nodes is N. For a limited scale of BA network [31], the node degree distribution P
(
k
)
=
2
m
2
k
-
3
/
(
1
-
N
-
1
), the node average degree 〈
k
〉
=
2
m, and the node maximum degree k
c
=
m
N
(
1
/
2
). We can get the parameter C of BA network as
(5)
C
B
A
=
m
ln
⁡
N
m
ln
⁡
N
-
2
(
1
-
N
-
1
)
.In Figure2, the epidemic threshold of virus is calculated by (4) and (5) according to the following conditions: the static network G is the BA network of node average degree for 10, the total number of nodes N
=
5000, the node interactivation time τ obeys power-law distribution given by (1), the minimum value of node interactivation time τ
min
⁡
=
1, and node average recovery time was shown in the illustration in Figure 2.Figure 2
The epidemic threshold of virusλ
c as a function of exponent α of power-law distribution which node interactivation time τ obeys, for the different average recovery time.We can see from Figure2 three points. First, the epidemic threshold becomes larger as the more heterogeneous node interactivation time distribution is (i.e., α decrease) for different average recovery time of infected node. The smaller the power-law exponent of node interactivation time distribution is, the greater the average value of node interactivation time derived by (1) is, that is, the fewer the average times of node activation are at the same time. That means an infected node has less chance to spread virus to its adjacent nodes before it recovers. Thus only high effective transmission rate of virus ensures its epidemic under the circumstances. Second, the greater the average recovery time of infected node 1
/
μ is, which means infected nodes have more chance to be activated and transmit virus to their adjacent nodes, therefore the smaller the epidemic threshold is. Thirdly, as the power-law exponent α of node interactivation time τ increases, propagation threshold is tending to the same value no matter what value node average recovery time 1
/
μ is. The increase of the power-law exponent α of node interactivation time τ makes the heterogeneity and mean of τ diminish so that there are a large number of nodes of network activated at every moment. Until most of the nodes remain active, dynamic activation network gradually closes to the static network G. In this case, epidemic threshold on temporal network is only related to the topology of cumulative static network G, which can be proved from (4).One simulates the model on the static BA network, which its scale is 5000 nodes and each new node connects existing 5 nodes of network. A randomly selected node is set initially to infected state, namely, seed node. The average recovery probabilityμ of infected nodes is 0.1. The node interactivation time τ obeys the power-law distribution forms of (1) and the minimum value of node interactivation time τ
min
⁡
=
1. The exponent α is 2.1, 2.5, and 3.0, respectively. Figure 3 shows the node density infected by virus change along with virus transmission rate β. It is observed that the stronger the heterogeneity of node interactivation time τ is, the greater the epidemic threshold of virus is and the less the final spread scope of virus is. The node density infected by virus change along with time in Figure 4. As Figure 4 shows, the stronger the heterogeneity of node interactivation time τ is, the slower the spread speed of the virus is. That the heterogeneity of node interactivation time τ inhibits the propagation of virus is illustrated from two different aspects of the scale and the speed of virus propagation, respectively, in Figures 3 and 4, which demonstrate that the data simulation results accord with the theoretical analysis results of Figure 2.Figure 3
The node density infected by virus as a function of virus transmission rateβ, for the different exponent α of power-law distribution which node interactivation time τ obeys. Network node number N
=
5
000, new edge number from each node m
=
5, the recovery rate of the virus spread μ
=
0.1, and τ
min
⁡
=
1.Figure 4
The node density infected by virus as a function of timet, for the different exponent α of power-law distribution which node interactivation time τ obeys. Network node number N
=
5
000, new edge number from each node m
=
5, virus transmission rate β
=
0.4, the recovery rate of the virus spread μ
=
0.1, and τ
min
⁡
=
1.


## 5. Conclusion

Differring from previous studies that the heterogeneous of interevent time distribution affects the spread of the virus on networks, this work is based on the heterogeneous distribution of node interactivation time and establishes the asynchronous communication model, which is more obviously universal than the former. Asynchronous interaction style is suitable for the case that the two sides of interaction are not always active at the same time, which is prevailing in the applications from Internet and mobile Internet. Where node interactivation time follows power-law distribution, epidemic threshold of the model is deduced by means of the theory of updates. Simulating in BA network, it is concluded that the stronger the heterogeneity of node interactivation time is, the greater the epidemic threshold of virus is and the smaller the scale and speed of virus propagation are, which is consistent with the results of threshold theoretical derivation.In this work, asynchronous communication is elaborated by means of the example of sending and receiving e-mails and messages, and epidemic threshold is derived by using the power-law distribution as the heterogeneous distribution of node interactivation time. But time statistics of human behavior is far from being so simple. Different data sets, such as the data sets from mobile phone text messages, blog, BBS, and online services, have different heterogeneous time distribution of individual behavior [21], so the time distribution of individual behavior itself is a complicated and worth studying issue.



---

*Source: 409510-2014-04-08.xml*