Optimal filtering and control of network information epidemics

1 Introduction

Information epidemics describe the diffusion of pathogen-like information in population [1] and play a vital role in various scenarios, e. g., campaigning, viral marketing, and rumor spreading [2], [3], [4]. The relevant research topics, such as the modeling, analysis, and control of information epidemics, have attracted wide attention in the fields of information science, social networks, and group psychology [5].

The information epidemic models, used to depict the evolvement of epidemics, are generally recognized as compartmental models that categorize the population into different compartments, e. g., susceptible (S) and infected (I) [6]. In the context of information diffusion, these compartments may respectively refer to unawareness and awareness of the information, or people’s willingness to refuse or adopt the information. A representative and widely-studied epidemic model is the Susceptible-Infected-Susceptible (SIS) model which depicts the dynamics of the population in terms of the bidirectional transitions between compartments S and I. In addition, the networked information epidemic models with heterogeneous transition rates [7], [8] have recently gained more value than the earlier homogeneous-structure-based scalar models [9], due to the advantage of better depicting the structural and behavioral heterogeneity of social networks. Here, by homogeneous we mean that the population is well-mixed, i. e., the individuals in the network have the same chances to interact with others, while by heterogeneous we allow various individual properties. Apparently, the heterogeneous models are more flexible to be generalized to solve practical problems than the homogeneous ones. Therefore, the networked SIS model has been widely applied to popular research topics including innovation diffusion, epidemic spreading, and new technology adoption [10], [11]. To this end, we focus on the networked SIS model with heterogeneous transition rates as a representative information epidemic model.

As a fundamental research issue, control of information epidemics has obtained increasingly more concerns in recent years [12]. However, with the particular interests of the previous work on the noise-free models, there have been very few results on the control of noisy epidemics, although noise is ubiquitous in practical information diffusion processes [13]. Here, noise is a generic notion to depict both the exogenous stochastic uncertainties and the inherent random properties of the epidemic models, such as the information loss through the network (due to imperfect conveyance) and the understanding discrepancies among the individuals (due to various languages, culture, gender, or education background). When these factors affect the information epidemics, we formulate them as stochastic processes in the model and refer to the former as the process noise and the latter as the observation noise. Due to the involvement of the stochastic noise, the conventional deterministic control schemes cannot be applied, since explicit state-feedback is not available. Instead, the design of the controller should be based on the precise reconstruction of system states. Conventionally, the modeling noise in innovation diffusion is introduced as white noise with Gaussian properties [9], which motivates us to seek for an optimal controller for noisy epidemics based on optimal state filtering. Nevertheless, both the inherent nonlinearity of information epidemics and the strong coupling in the network render great challenges to such a control scheme which are still not overcome by the conventional filtering-and-control solutions [14], [15], [16], [17], [18], [19]. Filling this gap is the major focus of our work.

The main contribution of this article is, for the first time, to develop an optimal-filtering-based optimal control scheme for network information epidemic models, considering both the process and observation noises. As a representative information epidemics model, the networked SIS model with heterogeneous transition rates is taken into consideration. Specifically, the optimal filtering is concerned with the minimum quadratic estimation errors, which ensures precise estimation with respect to the second-order stochastic moments of the system states, and the optimal control aims at maximizing the information diffusion taking into account the input consumption. The optimality of both the state estimation and feedback control is guaranteed by a separation principle. Based on this, we are able to solve a series of problems that are concerned with the stochastic properties of information epidemics, such as innovation diffusion, rumor mitigation, and viral marketing with unmodeled uncertainties. From a general perspective, the optimal filtering and control developed in this article can be extended to a wide range of stochastic nonlinear network systems, such as the smart grid system affected by random environmental factors.

The remainder of this article is organized as follows: In Section 2, the network SIS epidemic model with process noise and observation noise is introduced. We then formulate the problem to be solved in this article. The optimal filter and the optimal control law are respectively presented in Section 3 and Section 4. Numerical experiments are conducted in Section 5 to illustrate the effectiveness of the proposed results. Finally, we conclude this article in Section 6.

2 Problem formulation

Consider an n-node strongly connected weighted directed graph G=(V,E,A) where V={1,2,…,n} and E⊆V×V are the set of labeled vertices and the set of edges, respectively. A=[aij] is the nonnegative adjacency matrix where a nonzero entry aij corresponds to an edge (j,i), i. e., node i can influence node j. The continuous-time network SIS model on the graph G reads

for all i∈V, where xi(t)∈R is the infection probability of node i. Another interpretation of xi, from the perspective of meta-population, is the infection proportion of i-th group (e.g, a city or a state). βi(t),γi(t)∈R are respectively the time-varying infection rate and curing rate of node i at time instant t. In accordance with previous literature, the infection process is considered to be proactive while the curing process is passive [8], [20]. In this article, we consider both process noise and observation noise in the information epidemics. From this perspective, the SIS model with stochastic noise is formulated as

where ei(t)∈R is a scalar coefficient and ωi(t)∈R is a standard Wiener process defined on a probability space (S,F,P), such that E(ωi)=0 and E(ωi2)=t. The compact form of (2) reads

where xt=[x1,x2,…,xn]⊤, βt=[β1,β2,…,βn]⊤, γt=[γ1,γ2,…,γn]⊤, ωt=[ω1,ω2,…,ωn]⊤, Xt=diag(xt), and Et=diag([e1,e2,…,en]). Note that we use xt to represent the state vector and define xi as its i-th element. Ambiguity is avoided since t∈R≥0 and i∈V belong to different domains. The system state xt is not directly measurable, but hidden by the following observation process

where Ht,Ft∈Rn×n are time-dependent matrices, and yt∈Rn, yt=Yt is the result of an observation, and vt=[v1,v2,…,vn]⊤∈Rn is a n-dimensional stochastic process. For each i=1,2,⋯,n, vi is a standard Wiener process defined on (S,F,P), and E(vi)=0, E(vi2)=t. Therefore, dωt and dvt denote Gaussian white noise processes whose covariance matrices are respectively constant matrices Ωδ(t) and Vδ(t), where Ω,V∈Rn×n are constants assumed to be known a-priori and δ(t)∈R is the Dirac delta function.

In this article, we are targeting to solving following problem.

3 Optimal filtering

In this section, we design the optimal filter for the network information epidemic model in (3). For brevity, we represent the system dynamics (3) as

where ft=I−XtAXtβt−Xtγt is the deterministic nonlinear process function. It is known from [21] that the optimal estimation xˆt of the system state xt with observation Yt, with respect to the estimation criterion (5) is

with an estimation variance Pt=E(xt−xˆt)(xt−xˆt)⊤Yt, and (8) renders an unbiased estimation, i. e., E(xˆt)=E(xt). In the follows, we continue to use the notation ·ˆ=E(·|Yt) as (8) to represent the conditional expectations. According to [21], the optimal estimation xˆt is formulated as follows

with the estimation variance

where (·)i is the i-th element of a vector and (·)ij is the element of a matrix at the i-th row and j-th column. For the estimation xˆt, we propose the following assumption.

Based on Assumption 1, the following theorem guarantees the optimality of the proposed optimal filter.

4 Optimal controller design

Now, let us investigate the optimal control solution for Problem 1-(2). It is known that, for linear systems, the filter and controller can be designed independently while guaranteeing the stability of the closed-loop dynamics, which is referred to as the separation principle. For nonlinear systems, however, only a few types of them ensure similar properties [28]. To justify the feasibility of the independent design of the filter and the controller in this article, it is necessary to investigate the existence of the separation principle for the network SIS model (3) with the corresponding optimal criterion (6).

It is known that the optimal state reconstruction (12) renders an unbiased estimation, i. e., E(xˆt)=E(xt), from which we have

where

is the control criterion that only depends on the estimated state xˆt dominated by the following dynamics,

which is the deterministic part of (12a), since the term PtHt⊤(FtVFt⊤)−1(dYt−Htxˆtdt) in (12a) is a Gaussian white noise [29]. This indicates that the optimal stochastic control law ut(xt) for system (3) with respect to the criteria (6) is equivalent to the deterministic one ut(xˆt) for the deterministic dynamics (14) and the cost criterion (13), which formulates the separation principle for the information epidemic models (3). Having this, we are ready to propose the optimal control solution for Problem 1-(2).

Until now, (12), (15a) and (15b) formulate the optimal filtering-and-control framework for the stochastic perturbed information epidemics (3) with respect to the optimality criteria (5) and (6). Note that (12) and (15b) are respectively differential equations with an initial condition and a terminal condition. Thus, we resort to the forward-backward sweep method in [8] to solve the numerical solution governed by these equations.

5 Simulation

In this section, we conduct a numerical experiment to evaluate the performance of the proposed optimal filtering-and-control framework for network information epidemics. The simulation is set up on a real-world scenario, a high-school social network in Illinois which describes the friendships between the school boys [30]. We construct a 67-node graph by selecting the largest strongly connected component of the network and consider the information spreading through this graph, which corresponds to the model in (3). The information propagating through this network can be the latest news of a soccer star or a recent base-ball match. Therefore, corresponding to the epidemics model (3), the state of the individuals represents to what probability the boys are aware of or adopt the information. For brevity, all model parameters are determined as constant. Specifically, we set βt=β∈(0.1,0.15)n, γt=γ∈(0.2,0.25)n, Et=Ft=Ht=In, tf=50, and pt=ψ=1n. Note that Rt is configured as a fixed diagonal matrix whose i-th diagonal entry is proportional to the number of the in-neighbors of node i with coefficient 0.2. dω and dv are generated as Gaussian white noise with zero means and variance 0.01. The initial condition of dynamics (3) is randomly chosen in the set xt∈(0,13)n. The evolvement of the information epidemics without control (βt=β) is illustrated in Fig. 1a. It is shown that, in this situation, the aware probabilities of all individuals decay to zero, which is not a satisfactory results for our intention of information diffusion.

Therefore, for this networked epidemics model, we solve the optimal filter xˆt and the optimal controller βt=ut(xˆt) according to the differential equations (12) and (15b). The initial condition of the estimated system (12a) is randomly chosen in xˆ0=(0,13)n, and P0 is set as a positive definite matrix with Pij∈(0,10−6) at the initial time instant t0. The optimal filter (12) and the optimal controller (15) are solved using the forward-backward sweep method in [8]. By applying the optimal filter-and-control solution to the information epidemic model, we obtain the controlled results shown in Fig. 1b. As it is manifested, the proposed optimal control drives xt to an average infection probability around 0.6. This indicates that the aware probabilities of all the individuals are brought to a comparably high level (very likely to be aware of the information), which reflects the success of the proposed information diffusion control. The estimated system state xˆt and the estimation error xt−xˆt are respectively shown in Fig. 1c and Fig. 1d. It is noticed that the estimation error converges to zero as time increases, which confirms the precision of the optimal filter. Therefore, this simulation reveals the effectiveness of the proposed optimal filter and optimal control for network information epidemics. Since the simulation is conducted on a real-world data set, the evaluation results are quite promising to serve as a reference for the practical policy design.

Figure 1

Performance of the proposed optimal filter and optimal control for network SIS model on a 67-node network. (a) and (b): By introducing the optimal control in (15a) the awareness of the information increases drastically. (c) and (d): The estimation of xt obtained by using the optimal filter in (12) approaches to the real value.

6 Conclusion

The main focus of this paper is on solving the optimal control problem for network information epidemics with process and observation noises. The main challenge of this work lies in the handling of the nonlinearity and deep coupling brought up by the networked structure. In this paper, we overcome this challenge by independently designing an optimal filter and an optimal controller based on a proposed separation principle for the information epidemics model. By applying the proposed framework, for the first time, we are able to influence the infection rates to maximize information diffusion and minimize the effort consumption on an epidemics network, even with stochastic uncertainties on both structure and observation. From a general perspective, this framework is also promising to be applied to a wider range of network nonlinear systems that are perturbed with stochastic uncertainties, such as the networked power grid system with current perturbation. For the future work, we will be dedicated to applying the proposed methods to solving practical problems. For example, analysis and prediction of the evolution of epidemics and robust control of large-scale power grid will be our most preferred interests.