key: cord-0792490-jhxov1gu
authors: Bao, Z.J.; Jiang, Q.Y.; Yan, W.J.; Cao, Y.J.
title: Stability of the spreading in small-world network with predictive controller
date: 2010-03-29
journal: Phys Lett A
DOI: 10.1016/j.physleta.2010.01.045
sha: c4e1545ed0590073cac29802bd2153a548b575e9
doc_id: 792490
cord_uid: jhxov1gu

In this Letter, we apply the predictive control strategy to suppress the propagation of diseases or viruses in small-world network. The stability of small-world spreading model with predictive controller is investigated. The sufficient and necessary stability condition is given, which is closely related to the controller parameters and small-world rewiring probability p. Our simulations discover a phenomenon that, with the fixed predictive controller parameters, the spreading dynamics become more and more stable when p decreases from a larger value to a smaller one, and the suitable controller parameters can effectively suppress the spreading behaviors even when p varies within the whole spectrum, and the unsuitable controller parameters can lead to oscillation when p lies within a certain range.

Recently, Watts and Strogatz have proposed the small-world network model to discover the large-clustering and small-distance properties, which universally exists in many natural and artificial networks, ranging from the Internet, the World Wide Web, human society, power grids, to economic and biological systems [1, 2] . In the small-world model, the regular lattices are responsible for large clustering, and a very small density of long-range connections has a drastic influence on short average distance [3, 4] .

The spreading of viruses, diseases and even disasters has been observed in many real large-scale and small-world networks [5] . For example, the progress in science and technology cannot hold back the spread of infectious biological viruses in human society; on the contrary, the current networking age makes the diseases easily propagate all around the world [6] . The current outbreak of H1N1 flu was first detected in Mexico City on March 18, 2009 . The World Health Organization (WHO) declared an H1N1 pandemic on June 11, 2009 , moving the alert level to phase 6, marking the first global pandemic since the 1968 Hong Kong flu. Up till now, the virus has already propagated in all regions of the world. In 2003, the spread of Severe Acute Respiratory Syndrome (SARS) leads to 8096 known infected cases and 774 deaths worldwide, declared by the WHO in the concluding report. The spread of computer viruses and worms on the Internet is another urgent problem.

There were more than $30 billion in damage caused by the Sobig worm, and the entire Internet came to a halt in a very short period given without any countermeasures to control the worms [7] . The cascading financial crisis of the East Asia and the avalanching blackouts in the electric grid of North America are also the typical examples of failure propagation in the small-world networks [8] [9] [10] . In the view of wide occurrence of spreading behaviors in the small-world networks, it becomes a very interesting issue to investigate the spreading of viruses, diseases and even disasters in the network [11] [12] [13] .

Much work has concentrated on the dynamics of spreading in small-world network. Moukarzel proposed a novel linear model of disease spreading in d-dimensional small-world lattices, which produces an exponential growth of infection to the limit of network scale [14] . The investigations on the outbreak of SARS in 2003 have shown that the high clustering of small-world human social network is one of the keys to transmit SARS [15] [16] [17] . In fact, when the epidemic diseases propagate among humans or the computer viruses spread through the Internet, the administrative authorities usually take some counter measures to control the unfavorable prevalence. Prof. Li et al. have carried out some pioneering researches on the stability of the spreading dynamics in smallworld network when control strategies are applied, and made great achievements. It was recently reported that there exist oscillating infective behaviors with some unsuitable recovery rates in the epidemiology [18] , indicating the possible oscillations resulted from control strategies applied by the administrative authorities. However, Prof. Li inherent after studying the stability of spreading models with linear and nonlinear feedback controllers [8] . Prof. Li et al. further investigated three linear delayed SIR models for different cases of recovery response, and found that the unsuitable recovery strength may lead to oscillations [6] .

In this Letter, based on the small-world spreading model used in Ref. [8] , we investigate the stability of spreading dynamics when advanced predictive control strategy is applied to suppress the propagation of diseases, viruses and disasters. We try to investigate the stability condition of the small-world spreading model with predictive controller applied, and whether the epidemic oscillations in predictive-controlled small-world spreading model are avoidable.

Over the last two decades, predictive control strategy has emerged as a powerful control technique in a wide variety of application areas [19, 20] . The basic mechanism of predictive control is to calculate a sequence of future control signals in such a way that it minimizes a multistage cost function. The index to be optimized is normally the expectation of a function measuring the discrepancy between the predicted output and the desired output of the system over the prediction horizon plus a function measuring the control effort over the control horizon [21] . The first calculated control input is actually implemented, the horizons are moved one sample period towards the future and the optimization process is repeated at the next time step.

Consider a single-input-single-output analytical system governed by the following:

(1)

The future system outputs y p (t + i) for i = 1, . . . , H p , are predicted over the prediction horizon H p using a model of the system. These values depend on the current process state and the fu-

is the control horizon. The control variable is manipulated only within the control horizon and remains constant afterwards, i.e.,

timizing a given objective function. The objective function defines the goal over the prediction horizon in combination with a cost function on the control effort over the control horizon. A general objective function is the following quadratic form

where P i and Q i are positive definite weight matrices. The first term accounts for minimizing the variance between the predictive output and the desired output of the system, while the second term, u(k) = u(k) − u(k − 1), represents a penalty on the control effort (related, for instance, to energy). Eq. (2) is mostly used in combination with input or output constraints.

To investigate the spreading dynamics of small-world evolving networks in the whole probability spectrum 0 p 1, we describe a general spreading model for small-world network with delayed predictive controller applied. Because the generative algorithm of the small-world network may result in the formulation of isolated clusters, we hold the following assumption that the small-world evolving network is always connected without any isolated cluster for all 0 p 1.

Recall that there exists an infective disease which spreads with a constant radial velocity v = 1 from an original infected node in small-world evolving network [22] . The random rewiring in the small-world model means in the propagation process that, each time the infective node spreads through the forthcoming edge in the nearest-neighbor ring, it may be linked with another node through the rewired long-range connection with probability 0 p 1. Therefore, based on the mean-field approach, the total volume of infected individuals V (t) in the one-dimensional smallworld evolving model satisfies

where the time delay δ > 0 is due to the long-range spatial distance [23] . From Eq. (3) we can easily find that the infected volume V (t) grows exponentially and finally can cover the whole network if no counter measure is taken. Faced with the cascading spread of diseases or disasters, authorities usually implement the control strategies to struggle against the propagation, which, for example, result in the decrease of infected individuals by the increasing recovery of SARS patients, or the slaughter of infected animals [8] . Therefore, we translate the reactions taken by the authorities to the following spreading equation with a feedback controller:

where the controller takes effect after the time delay > 0. Without loss of its generality, we assume = δ. After discretizing Eq. (4), we have

In predictive control strategy, the predictive model of system behaviors is very important. According to Eq. (5), we derive the i-step-ahead predictive value of the infected volume at time k

The objective function of predictive control is defined to be min u(k+i)

where H p is the prediction horizon, H u is the control horizon, q i and r i are the weighting values, V s (k + i) is the set value of the infected individuals at time k + i, and u(k + i) is the increment of control input at time k + i satisfying u(k

From Eq. (6) we can know that V (k + i|k) is related to u(k) only for i δ + 1 because of the input time-delay δ. Consequently, we take H p δ + 1 and q i = 0 when 1 i δ. For simplicity, here we apply the one-step-ahead predictive control to investigate the stability of spreading dynamics, i.e. H p = δ + 1 and H u = 1, and the control performance is adjusted by changing the parameters q H p and r 0 .

Use Eq. (6) repeatedly and derive 

A necessary condition for Eq. (7) to have a minimum is to set ∂ J ∂ u(k) = 0. Therefore, the optimal increment of control at time k is

As we know, predictive control is a class of feedback control strategies. In the following, we analyze the stability of small-world spreading model with the predictive controller applied.

By using Laplace transform variable z, we can respectively rewrite Eqs. (9) and (5) as (10) and

Therefore, small-world spreading model with the one-stepahead predictive controller is a closed-loop system, whose structure diagram is shown in Fig. 1 , and the parameters in Fig. 1 are listed as follows:

Theorem. Small- 

Proof. As shown in Fig. 1 , the transfer functions from two inputs to output are G 1 (z) = F DG

1+F D H+F DGL respectively. From the classic control theory, we can know that the system is stable if and only if the poles of the system are all inside the unit circle [24, 25] . According to G 1 (z) and G 2 (z), we can arrive at the proof of this theorem. From Eq. (12) it is discovered that the stability of spreading behaviors in small-world network with predictive controller applied is closely related to the parameters r, q H p , δ and p. 2

We choose δ = 1 and V s (k + H p ) = 1, and performed large simulations with different control parameter values of r, q H p and p to demonstrate the above stability condition. In the simulations, the output constraint V (k) 0 is considered. The spreading dynamics are depicted in Fig. 2 , which are the results from single runs and the corresponding poles' magnitudes of the closed-loop system are listed in Table 1 , with the different control parameters values. The procedure of numerical simulation can be described as follows:

Step 1: Choose the values of parameters r, q, p, V s (k + H p );

Step 2: At time k, achieve the optimal control increment u opt (k) by Eq. (9);

Step 3: Add u opt (k) to u(k − 1) to generate the control law u(k) at the current time k;

Step 4: Calculate V (k + δ + 1) according to Eq. (5), in which V (k + δ) and V (k) have already been obtained respectively at the previous times k − 1 and k − δ − 1, and then the output constraint is considered;

Step 5: k + 1 → k; go to Step 2 if the control process is not finished.

First, we fix the controller parameters r and q H p at a pair of constant values, and observe the stability of small-world spreading model with predictive controller when the rewiring probability p is varied. Fixing r = 10 and q H p = 1, we select p = 0.2, p = 0.1 and p = 0.05 respectively. When r = 10, q H p = 1 and p = 0.2, two poles of the closed-loop system are outside of the unit circle as shown in Table 1 . From the theorem, we can judge that the spreading behavior is unstable, and the decision is also proved by the result of simulation, depicted in Fig. 2(a) . We can see that, the predictive controlled small-world spreading model oscillates, and furthermore it is discovered from the simulations that the spreading behavior even diverges if the output constraint is not considered. When r = 10, q H p = 1 and p = 0.1, three roots of polynomial T (z) = 0 are all inside the unit circle, so the closed-loop system is stable as shown in Fig. 2(c) . Further decreasing the rewiring probability p to 0.05 results in a more stable spreading dynamics, which can be found by comparing Fig. 2(c) with Fig. 2(e) . The stability of the predictive controlled small-world spreading model is illustrated in Figs. 2(b), 2(d) and 2(f) when fixing r = 5, q H p = 1 and varying p from 0.2 to 0.1 and then to 0.05. Large simulations are performed and a similar phenomenon is discovered that, with the fixed controller parameters r and q H p , the dynamics of the smallworld spreading model with predictive controller become more and more stable when rewiring probability p decreases from a larger value to a smaller one.

Second, by fixing the parameters p and q H p , we examine the influences of parameter r on the spreading behavior. Comparing Fig. 2(a) with Fig. 2(b), Fig. 2(c) with Fig. 2(d) , and Fig. 2 (e) with Fig. 2(f) , it is easily discovered that decreasing r can help the former unstable oscillation of the infected volume V (k) be convergent to the set value, and bring a more stable spreading dynamics to the former stable system. From the objective function of predictive control illustrated in Eq. (7), we learn that decreasing parameter r can ease the suppression of control increment. And this means that the fluctuations of actions taken by the authorities are allowed be larger, which can certainly make the spreading dynamics more stable.

Third, with the fixed parameters p and r, we increase the parameter q H p to observe the stability of the spreading dynamics. As shown in Figs. 2(g), 2(h) and 2(i), increasing q H p results in the same results as decreasing r does. From Eq. (7) we can find that the increase of parameter q H p can decrease the difference between the infected individuals and the set value.

For some certain values of control parameters r and q H p , the spreading behavior is unstable when the rewiring probability p lies within a certain range of the whole spectrum 0 p 1, with the phenomenon that control performance changes for the worse with the increase of p. However, we can find that the suitable control parameters, for example r = 1, q H p = 1, can lead to the stable dynamics of small-world spreading model even when p varies within the whole spectrum.

In this Letter, we have explored the stability of small-world spreading model when predictive control strategy is applied. The sufficient and necessary stability condition is given, which is closely related to the control parameters r, q H p , and the smallworld rewiring probability p. Decreasing r, increasing q H p , and decreasing p are valid for stabilizing the oscillations of the infected individuals V (k) to the set value. We have discovered that, the epidemic oscillations in predictive-controlled small-world spreading model are avoidable even when p varies within the whole spectrum if the suitable control parameters are applied; and on the contrary, the unsuitable control parameters can lead to spreading oscillations when p lies within a certain range.

How to stabilize the spreading behavior in small-world network is still open because there are many complicated spreading mech- anisms in the real networks and moreover how to translate the advanced control strategies to the practical measures taken by the authorities deserves more explorations. All these problems are our future research directions.

Small Worlds-The Dynamics of Networks Between Order and Randomness

Proceedings of the IEEE International Conference on Networking, Sensing and Control

Predictive Control with Constraints

Discrete-Time Control Systems

The Control Handbook

The authors would like to appreciate the financial support from