Stochastic Model for Information Propagation in Complex Networks

Dimitri Papadimitriou¹

Most information propagation models in complex networks are probabilistic as they rely on the probability that vertices interact only locally with their neighbors. In this paper, we propose a stochastic propagation model that takes into account uncertainty in drift and diffusion. For this purpose, we consider the motion of information as being driven by an uncontrolled state process {X(t): t > 0}. The probability density function u(x,t) associated to this state process represented by the random variable X(t) satisfies the so-called Fokker-Planck (a.k.a. Kolmogorov forward) equation. The equation governing the information propagation model by combining drift and diffusion collectively defines thus a convective propagation phenomena. Our computational method makes use of polynomial chaos expansions (PCE) that enable to compactly represent the variable of interest as a linear combination of orthogonal polynomials which depend on another continuous random variable z (with known distribution). The latter characterizes uncertainty in model parameters (the drift and diffusion coefficients), input and output variables. The solution u(x,t,z) can thus be represented as a truncated series of orthogonal polynomials multiplied by deterministic coefficients. The dimension of the resulting system of coupled non-linear partial differential equations grows with the order of the polynomial chaos expansion and the dimension of the stochastic input. The resolution of this system of partial differential equations, realized using Matlab produces a propagation pattern that accounts for the convective effects induced by medium- and long-distance interactions (thus, beyond local interactions). Moreover, since various interactions between information yield delays which may alter the propagation dynamics due to the so-called memory effect (future behavior of the state process depends not only on the present but also on former states), we further explore propagation models where the governing equation is formulated by the nonlinear stochastic delay-differential equation (SDDE) also referred to as Stochastic Differential Equations with Memory.