# American Institute of Mathematical Sciences

doi: 10.3934/nhm.2018026

## Influence prediction for continuous-time information propagation on networks

 1 School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA 2 Department of Mathematics & Statistics, Georgia State University, Atlanta, GA 30303, USA 3 School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA

* Corresponding author: Xiaojing Ye

Received  November 2017 Revised  June 2018 Published  September 2018

We consider the problem of predicting the time evolution of influence, defined by the expected number of activated (infected) nodes, given a set of initially activated nodes on a propagation network. To address the significant computational challenges of this problem on large heterogeneous networks, we establish a system of differential equations governing the dynamics of probability mass functions on the state graph where each node lumps a number of activation states of the network, which can be considered as an analogue to the Fokker-Planck equation in continuous space. We provides several methods to estimate the system parameters which depend on the identities of the initially active nodes, the network topology, and the activation rates etc. The influence is then estimated by the solution of such a system of differential equations. Dependency of the prediction error on the parameter estimation is established. This approach gives rise to a class of novel and scalable algorithms that work effectively for large-scale and dense networks. Numerical results are provided to show the very promising performance in terms of prediction accuracy and computational efficiency of this approach.

Citation: Shui-Nee Chow, Xiaojing Ye, Hongyuan Zha, Haomin Zhou. Influence prediction for continuous-time information propagation on networks. Networks & Heterogeneous Media, doi: 10.3934/nhm.2018026
##### References:

show all references

##### References:
Influence prediction on small sized network (when our matlab implementation of $\texttt{FPE-dist}$ still takes short time in computing). Left two: Erdős-Rényi's network of size $K = 16, 32$. Right: Small-world network $K = 32$. Average degree $(1/K)\sum_i|N_i^{{\rm out}}| = 4$
Influence prediction on Left: Erdős-Rényi's network, Middle: small-world network, and Right: scale-free network. All have size $K = 1024$ and average degree are $(1/K)\sum_i|N_i^{{\rm out}}| = 8, 6, 6$ respectively
Left: Influence prediction on dense Erdős-Rényi's random network with $K = 1024$ and $(1/K)\sum_i|N_i^{{\rm out}}| = 32, 64,128$ respectively. Middle: Influence prediction on the same Kronecker network of size $1024$ using three different choices of source set $S_1, S_2, S_3$ ($|S_i| = 10$ in all three cases). Right: Comparison with the state-of-the-arts learning-based ConTinEst method
Top row: $\hat q_k$ estimated in $\texttt{FPE-dist}$ and $q_k(t)$ shown by ground truth (MCMC simulation) for $k = 10, 70,130,190$ using a dense Erdős-Rényi's network of size $K = 300$ and average degree $150$. Bottom row from left to right: $|\hat\rho_k(t)-\rho_k(t)|/\rho_k(t)$; $|\hat\mu(t)-\mu(t)|/\mu(t)$ and plot of $\mu(t)$ and $\hat\mu(t)$ for this $K = 300$ network; and CPU time (in seconds) of $\texttt{FPE-dist}$ using Runge-Kutta 4th order ODE solver on networks with $K$ range from $10^4$ to $10^8$
 [1] Shui-Nee Chow, Wuchen Li, Haomin Zhou. Entropy dissipation of Fokker-Planck equations on graphs. Discrete & Continuous Dynamical Systems - A, 2018, 38 (10) : 4929-4950. doi: 10.3934/dcds.2018215 [2] John W. Barrett, Endre Süli. Existence of global weak solutions to Fokker-Planck and Navier-Stokes-Fokker-Planck equations in kinetic models of dilute polymers. Discrete & Continuous Dynamical Systems - S, 2010, 3 (3) : 371-408. doi: 10.3934/dcdss.2010.3.371 [3] Sylvain De Moor, Luis Miguel Rodrigues, Julien Vovelle. Invariant measures for a stochastic Fokker-Planck equation. Kinetic & Related Models, 2018, 11 (2) : 357-395. doi: 10.3934/krm.2018017 [4] Michael Herty, Christian Jörres, Albert N. Sandjo. Optimization of a model Fokker-Planck equation. Kinetic & Related Models, 2012, 5 (3) : 485-503. doi: 10.3934/krm.2012.5.485 [5] Marco Torregrossa, Giuseppe Toscani. On a Fokker-Planck equation for wealth distribution. Kinetic & Related Models, 2018, 11 (2) : 337-355. doi: 10.3934/krm.2018016 [6] José Antonio Alcántara, Simone Calogero. On a relativistic Fokker-Planck equation in kinetic theory. Kinetic & Related Models, 2011, 4 (2) : 401-426. doi: 10.3934/krm.2011.4.401 [7] Michael Herty, Lorenzo Pareschi. Fokker-Planck asymptotics for traffic flow models. Kinetic & Related Models, 2010, 3 (1) : 165-179. doi: 10.3934/krm.2010.3.165 [8] Margarita Arias, Juan Campos, Cristina Marcelli. Fastness and continuous dependence in front propagation in Fisher-KPP equations. Discrete & Continuous Dynamical Systems - B, 2009, 11 (1) : 11-30. doi: 10.3934/dcdsb.2009.11.11 [9] Luisa Malaguti, Cristina Marcelli, Serena Matucci. Continuous dependence in front propagation of convective reaction-diffusion equations. Communications on Pure & Applied Analysis, 2010, 9 (4) : 1083-1098. doi: 10.3934/cpaa.2010.9.1083 [10] Helge Dietert, Josephine Evans, Thomas Holding. Contraction in the Wasserstein metric for the kinetic Fokker-Planck equation on the torus. Kinetic & Related Models, 2018, 11 (6) : 1427-1441. doi: 10.3934/krm.2018056 [11] Andreas Denner, Oliver Junge, Daniel Matthes. Computing coherent sets using the Fokker-Planck equation. Journal of Computational Dynamics, 2016, 3 (2) : 163-177. doi: 10.3934/jcd.2016008 [12] Roberta Bosi. Classical limit for linear and nonlinear quantum Fokker-Planck systems. Communications on Pure & Applied Analysis, 2009, 8 (3) : 845-870. doi: 10.3934/cpaa.2009.8.845 [13] Ioannis Markou. Hydrodynamic limit for a Fokker-Planck equation with coefficients in Sobolev spaces. Networks & Heterogeneous Media, 2017, 12 (4) : 683-705. doi: 10.3934/nhm.2017028 [14] Giuseppe Toscani. A Rosenau-type approach to the approximation of the linear Fokker-Planck equation. Kinetic & Related Models, 2018, 11 (4) : 697-714. doi: 10.3934/krm.2018028 [15] Charles L. Epstein, Leslie Greengard, Thomas Hagstrom. On the stability of time-domain integral equations for acoustic wave propagation. Discrete & Continuous Dynamical Systems - A, 2016, 36 (8) : 4367-4382. doi: 10.3934/dcds.2016.36.4367 [16] Piermarco Cannarsa, Marco Mazzola, Carlo Sinestrari. Global propagation of singularities for time dependent Hamilton-Jacobi equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4225-4239. doi: 10.3934/dcds.2015.35.4225 [17] Fabio Camilli, Elisabetta Carlini, Claudio Marchi. A flame propagation model on a network with application to a blocking problem. Discrete & Continuous Dynamical Systems - S, 2018, 11 (5) : 825-843. doi: 10.3934/dcdss.2018051 [18] Ludovic Dan Lemle. $L^1(R^d,dx)$-uniqueness of weak solutions for the Fokker-Planck equation associated with a class of Dirichlet operators. Electronic Research Announcements, 2008, 15: 65-70. doi: 10.3934/era.2008.15.65 [19] Linghua Chen, Espen R. Jakobsen. L1 semigroup generation for Fokker-Planck operators associated to general Lévy driven SDEs. Discrete & Continuous Dynamical Systems - A, 2018, 38 (11) : 5735-5763. doi: 10.3934/dcds.2018250 [20] Benoît Perthame, P. E. Souganidis. Front propagation for a jump process model arising in spacial ecology. Discrete & Continuous Dynamical Systems - A, 2005, 13 (5) : 1235-1246. doi: 10.3934/dcds.2005.13.1235

2017 Impact Factor: 1.187

## Tools

Article outline

Figures and Tables