## Epidemic spreading driven by biased random walks

Cunlai Pu, Siyuan Li, Jian Yang

Nanjing University of Science and Technology, Nanjing 210094, China

## Abstract

Random walk is one of the basic mechanisms found in many network applications. We study the epidemic spreading dynamics driven by biased random walks on complex networks. In our epidemic model, each time infected nodes constantly spread some infected packets by biased random walks to their neighbor nodes causing the infection of the susceptible nodes that receive the packets. An infected node get recovered from infection with a fixed probability. Simulation and analytical results on model and real-world networks show that the epidemic spreading becomes intense and wide with the increase of delivery capacity of infected nodes, average node degree, homogeneity of node degree distribution. Furthermore, there are corresponding optimal parameters such that the infected nodes have instantaneously the largest population, and the epidemic spreading process covers the largest part of a network.

Keywords: epidemic spreading, biased random walks, complex networks

## 1. Introduction

Unexpected outbreak of many epidemics in biological systems[1, 2] and the spread of viruses in technology systems[3, 4, 5] result in a lot of death or great damage in related systems. The study of epidemiological models has a long history, especially in the field of social science[6, 7]. The SIR (susceptible-infected-removed) model and the SIS (susceptible-infectedsusceptible) model are two representative models which capture the basic properties of epidemic spreading through the transition among several disease states[8, 9]. In SIR model, a susceptible individual will become infected with certain rate when it has contact with infected individuals. An infected individual will get immunity to the disease or die at some constant rate,

and becomes a removed node which means it can not get infected again. Therefore, the spread of disease will terminate when all the infected individuals are removed from the disease. Differently in SIS model, there are just two states, susceptible and infected. A recovered individual can get infected again. If the fraction of infected individuals is large enough the disease will spread indefinitely, otherwise it will die out after sometime. Initially, the epidemic models are considered under the homogeneous mixing hypothesis[10], in which it assumes that each time an arbitrary individual has an equal opportunity to contact with everyone else in the population. Later, results from network science community demonstrate that most real-world networked systems have heterogeneous topological structures[11, 12, 13], and this greatly promote many mathematicians and physicists to explore epidemic models on heterogeneous random networks[14, 15, 16, 17] by means of mean-field approximation[18, 19, 20], generating functions formalism[21] and percolation theory[22]. It was found that for random networks with strongly heterogeneous degree distribution, like many real-world networks, the epidemic threshold is absent, which means epidemics always have a finite probability to survive indefinitely[11, 18].

Besides of topological properities, traffics in networks also have great impacts on the epidemic spreading. For instance, in the Internet computer viruses transmit from a node to another one with data packets. Without transmission of packets, viruses can not spread even if the two nodes are physically connected. Another example is the air traffics speed the spread of disease among different spatial areas. The combination between epidemic spread and traffic dynamics were first considered in the metapopulation model[23] which characterizes the dynamics of systems composed of subpopulations. Then, Meloni et al[24] studied the impact of traffic dynamics on the spread of virus in the Internet, in which the information packets are transmitted with the shortest path protocol. Later, many mechanisms were proposed to suppress the traffic-driven epidemic spreading, for instance controlling the traffic flow[25], the routing strategy[26, 27], or the heterogeneous curing rate[28], deleting some particular edges[29], etc.

Random walk is one of the basic mechanisms related to spreading processes[30, 31, 32]. For example, a mobile phone virus may randomly dial some phone numbers from the directory. Some computer viruses propagate randomly by email or other online communication tools. Therefore, the role of random walks in the epidemic spreading should be explored. We propose an epidemic model driven by biased random walks. In our model, an infected node sends

infected packets at a constant rate to its neighbor nodes through biased random walks. A susceptible node gets infected after receive the infected packets, and will be removed from the set of infected nodes with a constant rate. We inverstigate the spreading dynamics, the optimal control parameter of our model and the influence of network topologies on our model.

## 2. SIR model

We improve the traditional SIR model by incorporating the traffic dynamics driven by random walks. The SIR model is one of the traditional epidemic spread models in literature. In the SIR model, there are three types of nodes including susceptible nodes, infected nodes and removed nodes. A susceptible node is susceptible to epidemics. An infected node is already infected by the epidemic. A recovered node is the one that is removed from the set of infected nodes. Assume the numbers of susceptible, infected and removed nodes at time t are denoted as S t ( ), I ( ) t and R t ( ) respectively. There are three basic elements in the SIR model as follows[8]:

- (1) Assume the number of nodes in the network is fixed to N . Then N = S t ( ) + I ( ) + t R t ( ) for all t .
- (2) At time t , an arbitrary infected node infects the susceptible nodes by a ratio β . Then the increased number of infected nodes at t is β ∗ s t ( ) ∗ I ( ). t
- (3) At time t, the number of infected nodes removed is proportional to the total number of infected nodes I ( ), which is t λ ∗ I ( ). t

According to the three elements, the dynamics of the SIR model can be expressed as follows[8]:

$$\begin{cases} \begin{array} { c } \frac { d I } { d t } & = \beta S I - \lambda I, \\ \frac { d S } { d t } & = - \beta S I, \\ \frac { d R } { d t } & = \lambda I. \end{array} \end{cases} ( 1 ) \\ \sigma \text{ enough all the infected nodes will eventually becomes}$$

When time t is large enough, all the infected nodes will eventually becomes removed nodes, and the epidemic spreading stops.

The SIR model is based on the assumption that a node has equal probability to contact with every other node in a network. However, in real situations, individuals often have heterogeneous numbers of contacts[11]. A few individuals have large number of contacts which will get more contacts according to the rich-get-richer mechanism, while most of the individuals

Figure 1: Illustration of the transitions among the susceptible, infected and removed nodes in our model.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0063v1-figure-45ab1710-68d2-433f-ab32-d202b85975f8.jpg)

have a few contacts. Especially in the Internet, the epidemic can not spread from a node to another node unless there is transport of infected packets between the two nodes. Additionally, in city networks even the cities are physically well connected, an epidemic can not spread among cities unless individuals who get infected by the disease move among the cities. Therefore, epidemics are often correlated with traffics for their spreading.

## 3. Epidemic model driven by biased random walks

We consider the traffic dynamics driven by biased random walks in the epidemic spreading process. In our model, each time an infected nodes will delivery constantly C infected packets to its neighbor nodes through biased random walks. If an infected or removed node receives the packets, it will drop the packets. If a susceptible node receives the packet, it becomes an infected node and starts delivering infected packets from next time step. An infected node has the probability λ to become a removed node. The transitions among susceptible, infected and removed nodes are shown in Fig. 1.

## 3.1. Dynamics of our model

Assume an arbitrary infected node a which has 〈 K 〉 neighbor nodes. 〈 K 〉 is the average node degree of the network. The degrees of a 's neighbor nodes are k , k 1 2 , · · · , k 〈 K 〉 respectively. According to the biased random walk mechanism, for a neighbor node i the probability that node a sends an infected packet to node i is as follows:

$$P _ { a i } = \frac { k _ { i } ^ { \alpha } } { \sum _ { j = 1 } ^ { \langle K \rangle } k _ { j } ^ { \alpha } }.$$

Where α is the control parameter of the biased random walk. When α = 0, all the neighbor nodes have equal opportunity to receive an infected packet delivered from node a which means they have equal probability to get infected. When α &gt; 0, nodes of larger degree have larger probability to receive the packet. When α &lt; 0, nodes of smaller degree have larger probability to receive the packet. Since a send C infected packets each time, the probability that node i will not receive any packets from node a is:

$$\bar { P } _ { a i } & = ( 1 - \frac { k _ { i } ^ { \alpha } } { \sum _ { j = 1 } ^ { \langle K \rangle } k _ { j } ^ { \alpha } } ) ^ { C }. \\, & \quad \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot$$

Assume X i is an random variable that represents the event that node i is infected. Then X i = 0 means node i hasn't get any infected packet from node a , and node i is not infected. X i = 1 means node i has received at least one of the infected packets from node a , and node i is infected. Then we have:

Then the expected value of X i is:

$$\begin{cases} \ P ( X _ { i } = 0 ) = ( 1 - \frac { k _ { i } ^ { \alpha } } { \sum _ { j = 1 } ^ { ( K ) } k _ { j } ^ { \alpha } } ) ^ { C }, \\ \ P ( X _ { i } = 1 ) = 1 - ( 1 - \frac { k _ { i } ^ { \alpha } } { \sum _ { j = 1 } ^ { ( K ) } k _ { j } ^ { \alpha } } ) ^ { C }. \end{cases} \\ \text{expected value of $X_{i}$ is: }$$

$$E ( X _ { i } ) = 1 - ( 1 - \frac { k _ { i } ^ { \alpha } } { \sum _ { j = 1 } ^ { \langle K \rangle } k _ { j } ^ { \alpha } } ) ^ { C }. \quad \quad \quad ( 5 ) \\. \quad \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \colon$$

Assume a random variable Y that represents the number of neighbor nodes infected by node a . Then the average value of Y is:

$$\Lambda \quad & \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
 \text{E} ( Y ) \ & = \ & \sum _ { i = 1 } ^ { \langle K \rangle } E ( X _ { i } ) \\ & = \ & \langle K \rangle - \sum _ { i = 1 } ^ { \langle K \rangle } ( 1 - \frac { k _ { i } ^ { \alpha } } { \sum _ { j = 1 } ^ { \langle K \rangle } k _ { j } ^ { \alpha } } ) ^ { C }. \\ \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
 \end{cases} \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \text{e sum is over all the $\langle K \rangle$ neighbor nodes of node $a$. However, in the}$$

Where the sum is over all the 〈 K 〉 neighbor nodes of node a . However, in the epidemic spreading process the neighbor nodes of node a may not be only susceptible nodes. To effevtively estimate the number of neighbor nodes that node a infects, we need to know the number of susceptible nodes among all the neighbor nodes of node a . To estimate the total number of new infected

nodes at time t , we count the ratio µ of susceptible nodes among neighbor nodes of infected nodes in the network, which is as follows:

$$\mu \ & = \ \frac { \sum _ { j = 1 } ^ { I ( t ) } n _ { j } } { \sum _ { j = 1 } ^ { I ( t ) } k _ { j } } \\ & \approx \ \frac { \langle n \rangle } { \langle K \rangle }.$$

Where n j is the number of susceptible nodes among the neighbor nodes of an infected node j . 〈 n 〉 represents the average number of susceptible nodes among all the neighbors of infected nodes at time t . According to Eq. 6 and Eq. 7, the total new infected nodes at time t is:

$$I _ { n e w } ( t ) \ & \approx \ \mathbb { E } ( Y ) * \mu * I ( t ) \\ & \approx \ ( \langle K \rangle - \sum _ { i = 1 } ^ { \langle K \rangle } ( 1 - \frac { k _ { i } ^ { \alpha } } { \sum _ { j = 1 } ^ { \langle K \rangle } k _ { j } ^ { \alpha } } ) ^ { C } ) * \frac { \langle n \rangle } { \langle K \rangle } * I ( t ). \\ \text{Combinine $Eq $1$ with $Eq $8$ we set the dynamic amounts of our modal}$$

Combining Eq. 1 with Eq. 8, we get the dynamics equations of our model as follows:

$$\begin{cases} \begin{array} { c c } \frac { d I } { d t } & = ( \langle K \rangle - \sum _ { i = 1 } ^ { ( K ) } ( 1 - \frac { k _ { i } ^ { \alpha } } { \sum _ { j = 1 } ^ { ( K ) } k _ { j } ^ { \alpha } } ) ^ { C } ) * \frac { ( n ) } { ( K ) } * I ( t ) - \lambda I, \\ \frac { d S } { d t } & = - ( \langle K \rangle - \sum _ { i = 1 } ^ { ( K ) } ( 1 - \frac { k _ { i } ^ { \alpha } } { \sum _ { j = 1 } ^ { ( K ) } k _ { j } ^ { \alpha } } ) ^ { C } ) * \frac { ( n ) } { ( K ) } * I ( t ), \\ \frac { d R } { d t } & = \lambda I. \end{array} \end{cases} \\ \text{We study the behaviours of $S(t). $I(t)$ and $R(t)$ with increase of time $t$ on a}$$

We study the behaviours of S t ( ), I ( ) and R(t) with increase of time t t on a large-scale scale-free network. In Fig. 2, S t ( ) decreases abruptly, and then saturates with t . I ( ) t increases with t , then decreases with t , and finally saturates. There is a peak of I ( ) t that corresponds to the instantaneous maximum population of infected nodes. R t ( ) increases abruptly, and then saturates with t , which is opposite to S t ( ). When t is large enough, the epidemic spreading process stops, and R t ( ) is number of all the nodes that have ever been infected and removed finally from the disease. The trends of the curves for biased random walks of α = -1 are similar with that of simple random walks of α = 0. Also, the simulation results and the analytical results obtained from Eq. 9 are consistent, as shown in Fig. 2.

/s32

/s32

/s32

/s32

/s32

Figure 2: S t ( ), I ( ), t and R t ( ) vs. t for α = 0 and α = -1. A randomly selected node is set to be infected initially. Delivery capacity of infected nodes is C = 5. λ = 0 1. . The network is generated by the static model[33]. The parameters are N = 10000, 〈 k 〉 = 5, and γ = 2 5. .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0063v1-figure-dfe5e49a-6bdb-47de-8252-a936d4a575da.jpg)

/s32

/s32

/s32

/s32

Figure 3: S t ( ), I ( ), and t R t ( ) vs. t for various delivery capacities C. A randomly selected node is set to be infected initially. α = 0. λ = 0 1. The network is generated by the static . model. The parameters of the network are N = 10000, 〈 k 〉 = 5, and γ = 2 5. .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0063v1-figure-6a4ca43e-5dad-466c-a228-a1cb85301cee.jpg)

/s32

/s32

/s32

/s32

Figure 4: S t ( ), I ( ), t and R t ( ) vs. t for various α . A randomly selected node is set to be infected initially. C = 5. λ = 0 1. . The network for (a), (b) and (c) is generated by the static model. The parameters of the network are N = 10000, 〈 k 〉 = 5, and γ = 2 5. . The Epinions network for (d), (e) and (f) has 75, 879 nodes and 508, 960 edges.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0063v1-figure-2184448a-4a96-4ddb-aabb-3dc9391c2bdf.jpg)

## 3.2. Factors of our model

Delivery capacity C of infected nodes is a critical factor in our epidemic spreading model. The larger the delivery capacity of an infected node, the more susceptible neighbor nodes an infected node will likely infects each time. When C →∞ , I new ( ) t →〈 〉 ∗ n I ( ). t Then Eq. 9 is reduced as follows:

$$\begin{cases} \quad \frac { d I } { d t } & = \langle n \rangle * I ( t ) - \lambda I, \\ \quad \frac { d S } { d t } & = - \langle n \rangle * I ( t ), \\ \quad \frac { d R } { d t } & = \lambda I. \end{cases} \\ \intertext { \text{tion results of $S(t)\ I(t)\ and $R(t)\ for different value of $C$ in} }$$

We show simulation results of S t ( ), I ( ) and t R t ( ) for different value of C in Fig.3. Clearly, the larger C , the faster S t ( ), I ( ) and t R t ( ) convergence, and the epidemic spreads. The larger C , the larger population of nodes that has ever been infected which is inferred from S(t) and R(t) when t is large enough. The larger C , the larger instantaneous population of infected nodes which is indicated from the peak of I ( ). t The parameter α is another key factor in our epidemic model which determines the probability that the neighbors of an infected node get infected when C is a limited constant. In Fig. 4, we

/s32

see that α is correlated with the instantaneous maximum number of infected nodes I peak , and the range of the spread that is reflected by the ultimate number of removed nodes R end . α = -1 corresponds to a larger I peak and a larger R end than α = 0 and α = 1. This indicates that random walks biased on small-degree nodes favors the epidemic spreading which is hold for the model network and the Epinions network, as shown in Fig.4. Then we investigate the optimal parameters α opt that lead to the maximum I peak and the maximum R end on the model network and the Epinions network. In Fig.5, we see I peak and R end as a function of α . Clearly, I peak and R end increase with α first, then decrease with α respectively. There are α opt that correspond to maximum I peak and maximum R end respectively. We present the results of maximum I peak , maximum R end , and the corresponding α opt for some real-world networks, as shown in Table 1.

Table 1: maximum I peak and maximum R end with corresponding optimal parameters α for real-world networks. C = 5. λ = 0 1. .

| NAME            |   NODES |   EDGES |   I peak |   α opt |    R end |   α opt |
|-----------------|---------|---------|----------|---------|----------|---------|
| Oregon-1        |   10790 |   22469 |  2903.33 |    -0.4 |  6010.37 |    -0.8 |
| Gnutella        |   62586 |  147892 | 37833.4  |    -0.8 | 58155.7  |    -1.4 |
| Epinions        |   75879 |  508837 | 35274.1  |    -0.8 | 61560.2  |    -1.2 |
| Wiki-Vote       |    7115 |  103689 |  4294.22 |    -1   |  6623.23 |    -1.4 |
| Yeast           |    2361 |    7182 |  1314.21 |    -0.8 |  2214.63 |    -1.2 |
| email-Enron     |   36692 |  183831 | 12789.5  |    -0.8 | 24254.2  |    -1.4 |
| Facebook        |    4039 |   88234 |  2105.11 |    -0.8 |  3920.21 |    -0.4 |
| Geom            |    7343 |   11898 |  1778.5  |    -0.4 |  3202.5  |    -1   |
| Political blogs |    1222 |   19021 |   813.26 |    -1.2 |  1192.14 |    -2.2 |
| Power grid      |    4941 |    6594 |  1278.36 |     0.4 |  4304.27 |    -0.2 |

## 4. Impacts of networks structures on our model

We investigate the influence of topological properties of complex networks including average node degree and degree distribution, on the behaviors of our epidemic spreading model. We focus on the spontaneous number of infected nodes I peak and the final population of nodes that have ever been infected R end , as well as the related optimal parameters α opt . According Eq.

/s32

/s32

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0063v1-figure-5dce6689-5bb2-4931-820b-a4c410409497.jpg)

/s32

Figure 5: I peak and R end vs. α . A randomly selected node is set to be infected initially. C = 5. λ = 0 1. . The networks are the same as in Fig. 4. The results are the average of 100 independent runs.

## 6, we have:

$$6, \, \text{we have} \colon \\ E ( Y ) \ & = \ \langle K \rangle - \sum _ { i = 1 } ^ { \langle K \rangle } ( 1 - \frac { k _ { i } ^ { \alpha } } { \sum _ { j = 1 } ^ { \langle K \rangle } k _ { j } ^ { \alpha } } ) ^ { C } \\ & = \ \langle K \rangle - \sum _ { i = 1 } ^ { \langle K \rangle } ( 1 - C \frac { k _ { i } ^ { \alpha } } { \sum _ { j = 1 } ^ { \langle K \rangle } k _ { j } ^ { \alpha } } + \frac { C ( C - 1 ) } { 2 } ( \frac { k _ { i } ^ { \alpha } } { \sum _ { j = 1 } ^ { \langle K \rangle } k _ { j } ^ { \alpha } } ) ^ { 2 } - \cdots ) \\ & = \ \sum _ { i = 1 } ^ { \langle K \rangle } ( C \frac { k _ { i } ^ { \alpha } } { \sum _ { j = 1 } ^ { \langle K \rangle } k _ { j } ^ { \alpha } } - \frac { C ( C - 1 ) } { 2 } ( \frac { k _ { i } ^ { \alpha } } { \sum _ { j = 1 } ^ { \langle K \rangle } k _ { j } ^ { \alpha } } ) ^ { 2 } + \cdots ). \\ \text{When} \, \langle K \rangle & \to \infty, \, \text{we get} \colon$$

When 〈 K 〉 → ∞ , we get:

$$E ( Y ) \ & \approx \ \sum _ { \begin{subarray} { c } i = 1 \end{subarray} } ^ { \langle K \rangle } \frac { C k _ { i } ^ { \alpha } } { \sum _ { j = 1 } ^ { \langle K \rangle } k _ { j } ^ { \alpha } } \\ \approx \ C$$

Eq. 12 means that generally the number of nodes that an infected nodes infects in one time step increases with average degree 〈 K 〉 , and tends to C , which is further confirmed in Fig. 6. Also, for the whole epidemic spreading process, the maximum I peak and the maximum R end increase substantially, then saturate with 〈 K 〉 respectively, as shown in Fig. 7 and 8. Their corresponding optimal parameters α opt are generally negative and decrease with

/s32

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0063v1-figure-f8767960-276c-40fe-a12b-9a28705d3b24.jpg)

/s32

Figure 6: E( Y ) vs. 〈 K 〉 obtained from Eq. 6.

〈 K 〉 . This indicates that when the networks become dense, random walks should be more biased on small-degree nodes to make the epidemic spreading more intense and wide. These results are consistent both for random networks (Fig. 7) and scale-free networks (Fig. 8). We also investigate the impact of degree distribution on the epidemic spreading dynamics. In Fig. 9, the maximum I peak and the maximum R end increase abruptly, then saturate with γ respectively, and this means when the degree distribution becomes homogeneous, the spread of the epidemic becomes more fierce and wide in the network. The optimal parameters for I peak and R end increase with γ . This indicates when the network becomes homogeneous, the extent that random walks are biased on small-degree nodes to get a wide and fierce epidemic spreading decreases. need less However, the fluctuations in the curves are clear.

## 5. Conclusions and discussions

In summary, we investigate the epidemic spreading on complex networks including model networks and real-world networks. In our model, the epidemic spreading goes with packets transmission driven by biased random walks. Analytical and simulation results demonstrate that Epidemic spreading becomes fierce and wide with increase of delivery capacity of infected nodes, average node degree, and the homogeneity of the network. The optimal parameters of the biased random walks in epidemic spreading are generally negative values. This means the random walks are biased on small-degree nodes to make an intense and wide spread of the epidemic. However, the bi-

/s32

/s32

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0063v1-figure-a9cf06c3-a01a-44ff-9565-288f4f20da6d.jpg)

/s32

/s32

Figure 7: α opt and the corresponding I peak and R end vs. 〈 K 〉 for random networks. The networks are generated by the ER (Erd¨s-R´ enyi) model[34], and the network size is o N = 5000. A randomly selected node is set to be infected initially. C = 5. λ = 0 1. . The results are the average of 10 4 independent runs.

/s32

/s32

/s32

/s32

Figure 8: α opt and the corresponding I peak and R end vs. 〈 K 〉 for scale-free networks. The networks are generated by the static model, the network size is N = 5000, and the power-law parameter is γ = 2 5. . A randomly selected node is set to be infected initially. C = 5. λ = 0 1. The results are the average of 10 . 4 independent runs.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0063v1-figure-5551987c-e914-4fb9-a517-2467b4444cec.jpg)

/s32

/s32

/s32

/s32

Figure 9: α opt and the corresponding I peak and R end vs. power-law parameter γ . The networks are generated by the static model, the network size is N = 5000, and the average node degree is 〈 K 〉 = 5. A randomly selected node is set to be infected initially. C = 10. λ = 0 1. The results are the average of 10 . 4 independent runs.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0063v1-figure-9443065a-a845-44b5-91e4-5012e8e3f2d3.jpg)

ased random walks are based on only degrees of the nearest neighbor nodes in our model. The effects of biased random walks with more topological information on the epidemic spreading still need to be explored.

## Acknowledgments

This work was supported by the Natural Science Foundation of China (Grant No. 61304154), the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20133219120032), and the Postdoctoral Science Foundation of China (Grant No. 2013M541673).

## References

- [1] D. G. Green, T. Bossomaier, eds, Complex systems: from biology to computation, IOS press, 1993.
- [2] H. W. Hethcote, SIAM Rev. 42 (2000) 599.
- [3] J. Balthrop, S. Forrest, M. E. J. Newman, et al, arXiv preprint cs/0407048, 2004.

- [4] P. Wang, M. C. Gonz´lez, C. A. Hidalgo, et al, a Science 324 (2009) 1071.
- [5] A. Vespignani, Nature Physics 8 (2012) 32.
- [6] F. Brauer, C. Castillo-Chavez, Mathematical models in population biology and epidemiology, Springer, 2011.
- [7] L. F. Berkman, I. Kawachi, eds, Social epidemiology, Oxford University Press, 2000.
- [8] N. T. J. Bailey, The Mathematical Theory of Infectious Diseases and its Applications, Griffin, London, 1975.
- [9] R. M. May, Infectious diseases of humans: dynamics and control, Oxford University Press, 1995.
- [10] R. M. Anderson, R. M. May, Infectious diseases of humans, Oxford: Oxford university press, 1991.
- [11] M. Newman, Networks: an introduction, Oxford University Press, 2010.
- [12] S. N. Dorogovtsev, A. V. Goltsev, J. F. F. Mendes, Rev. Mod. Phys. 80 (2008) 1275.
- [13] A. Barrat, M. Barthelemy, A. Vespignani, Dynamical processes on complex networks, Cambridge University Press, Cambridge, 2008.
- [14] T. Zhou, Z. Q. Fu, B. H. Wang, Progress in Natural Science 16 (2006) 452.
- [15] R. Yang, B. H. Wang, J. Ren, et al, Phys. Lett. A 364 (2007) 189.
- [16] G. Yan, Z. Q. Fu, J. Ren, W. X. Wang, Phys. Rev. E 75 (2007) 016108.
- [17] S. W. Chou, K. Wang, Q. Liu, et al, Acta Phys. Sin 61 (2012) 150201.
- [18] R. Pastor-Satorras, A. Vespignani, Phys. Rev. Lett. 86 (2001) 3200.
- [19] Z. Yang, T. Zhou, Phys. Rev. E 85 (2012) 056106.
- [20] F. D. Sahneh, C. Scoglio, P. Van Mieghem, IEEE/ACM Transactions on Networking (TON) 21 (2013) 1609.

- [21] M. E. J. Newman, Phys. Rev. E 66 (2002) 016128.
- [22] R. Cohen, K. Erez, D. ben Avraham, et al, Phys. Rev. Lett. 85 (2000) 4626.
- [23] V. Colizza, A. Vespignani, Journal of Theoretical Biology 251 (2008) 450.
- [24] S. Meloni, A. Arenas, Y. Moreno, PNAS 106 (2009) 16897.
- [25] P. Bajardi, C. Poletto, J. J. Ramasco, et al, PLoS ONE 6 (2011) e16591.
- [26] H. X. Yang, W. X. Wang, Y. C. Lai, et al, Phys. Rev. E 84 (2011) 045101(R).
- [27] H. X. Yang, Z. X. Wu, J. Stat. Mech. 3 (2014) P03018.
- [28] C. Shen, H. Chen, Z. Hou, Phys. Rev. E 86 (2012) 036114.
- [29] H. X. Yang, Z. X. Wu, B. H. Wang, Phys. Rev. E 87 (2013) 064801.
- [30] L. Lov´sz, a Combinatorics: Paul Erd¨s is eighty o 2 (1993) 1.
- [31] J. D. Noh, H. Rieger, Phys. Rev. Lett. 92 (2004) 118701.
- [32] M. Bonaventura, V. Nicosia, V. Latora, Phys. Rev. E 89 (2014) 012803.
- [33] K.-I. Goh, B. Kahng, D. Kim, Phys. Rev. Lett. 87 (2001) 278701.
- [34] P. Erd¨s, A. R´nyi, o e Publ. Math. Inst. Hung. Acad. Sci. 5 (1960) 17.
Cunlai Pu Siyuan Li Jian Yang
Epidemic spreading driven by biased random walks
Random walk is one of the basic mechanisms found in many network
applications. We study the epidemic spreading dynamics driven by biased random
walks on complex networks. In our epidemic model, each time infected nodes
constantly spread some infected packets by biased random walks to their
neighbor nodes causing the infection of the susceptible nodes that receive the
packets. An infected node get recovered from infection with a fixed
probability. Simulation and analytical results on model and real-world networks
show that the epidemic spreading becomes intense and wide with the increase of
delivery capacity of infected nodes, average node degree, homogeneity of node
degree distribution. Furthermore, there are corresponding optimal parameters
such that the infected nodes have instantaneously the largest population, and
the epidemic spreading process covers the largest part of a network.