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:
[1]

S. BoccalettiG. BianconiR. CriadoC. I. Del GenioJ. Gómez-GardeñesM. RomanceI. Sendiña-NadalZ. Wang and M. Zanin, The structure and dynamics of multilayer networks, Physics Reports, 544 (2014), 1-122. doi: 10.1016/j.physrep.2014.07.001.

[2]

W. Bock, T. Fattler, I. Rodiah and O. Tse, An analytic method for agent-based modeling of spatially inhomogeneous disease dynamics, in AIP Conference Proceedings, vol. 1871, AIP Publishing, 2017, 1–11.

[3]

M. Boguná and R. Pastor-Satorras, Epidemic spreading in correlated complex networks, Physical Review E, 66 (2002), 047104.

[4]

E. Cator and P. Van Mieghem, Second-order mean-field susceptible-infected-susceptible epidemic threshold, Physical review E, 85 (2012), 056111.

[5]

R. CheW. HuangY. Li and P. Tetali, Convergence to global equilibrium for fokker-planck equations on a graph and talagrand-type inequalities, Journal of Differential Equations, 261 (2016), 2552-2583. doi: 10.1016/j.jde.2016.05.003.

[6]

S.-N. ChowW. HuangY. Li and H. Zhou, Fokker-planck equations for a free energy functional or markov process on a graph, Archive for Rational Mechanics and Analysis, 203 (2012), 969-1008. doi: 10.1007/s00205-011-0471-6.

[7]

E. Cohen, D. Delling, T. Pajor and R. F. Werneck, Timed influence: Computation and maximization, arXiv preprint, arXiv: 1410.6976.

[8]

P. Cui, S. Jin, L. Yu, F. Wang, W. Zhu and S. Yang, Cascading outbreak prediction in networks: A data-driven approach, in Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2013,901–909.

[9]

G. DemirelF. VazquezG. Böhme and T. Gross, Moment-closure approximations for discrete adaptive networks, Physica D: Nonlinear Phenomena, 267 (2014), 68-80. doi: 10.1016/j.physd.2013.07.003.

[10]

N. Du, Y. Liang, M.-F. Balcan and L. Song, Influence function learning in information diffusion networks, in International Conference on Machine Learning, 2014, 2016–2024.

[11]

N. Du, L. Song, M. Gomez-Rodriguez and H. Zha, Scalable influence estimation in continuoustime diffusion networks, in Advances in Neural Information Processing Systems, 2013, 3147– 3155.

[12]

M. Erbar and J. Maas, Ricci curvature of finite Markov chains via convexity of the entropy, Arch. Ration. Mech. Anal., 206 (2012), 997-1038. doi: 10.1007/s00205-012-0554-z.

[13]

M. Gomez Rodriguez, B. Schölkopf, L. J. Pineau et al., Influence maximization in continuous time diffusion networks, in 29th International Conference on Machine Learning (ICML 2012), International Machine Learning Society, 2012, 1–8.

[14]

D. KempeJ. Kleinberg and É. Tardos, Maximizing the spread of influence through a social network, Theory Comput., 11 (2015), 105-147. doi: 10.4086/toc.2015.v011a004.

[15]

J. O. Kephart and S. R. White, Directed-graph epidemiological models of computer viruses, in Research in Security and Privacy, 1991. Proceedings., 1991 IEEE Computer Society Symposium on, IEEE, 1991,343–359.

[16]

J. Leskovec, L. Backstrom and J. Kleinberg, Meme-tracking and the dynamics of the news cycle, in Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2009,497–506.

[17]

J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen and N. Glance, Cost-effective outbreak detection in networks, in Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, 2007,420–429.

[18]

J. LindquistJ. MaP. Van den Driessche and F. H. Willeboordse, Effective degree network disease models, Journal of mathematical biology, 62 (2011), 143-164. doi: 10.1007/s00285-010-0331-2.

[19]

V. Marceau, P.-A. Noël, L. Hébert-Dufresne, A. Allard and L. J. Dubé, Adaptive networks: Coevolution of disease and topology, Physical Review E, 82 (2010), 036116, 10pp. doi: 10.1103/PhysRevE.82.036116.

[20]

J. C. Miller and I. Z. Kiss, Epidemic spread in networks: Existing methods and current challenges, Mathematical Modelling of Natural Phenomena, 9 (2014), 4-42. doi: 10.1051/mmnp/20149202.

[21]

C. Moler and C. Van Loan, Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM review, 45 (2003), 3-49. doi: 10.1137/S00361445024180.

[22]

M. Newman, Networks: An Introduction, Oxford University Press, 2010. doi: 10.1093/acprof:oso/9780199206650.001.0001.

[23]

R. Pastor-SatorrasC. CastellanoP. Van Mieghem and A. Vespignani, Epidemic processes in complex networks, Reviews of modern physics, 87 (2015), 925-979. doi: 10.1103/RevModPhys.87.925.

[24]

H. Ryu, M. Lease and N. Woodward, Finding and exploring memes in social media, in Proceedings of the 23rd ACM conference on Hypertext and social media, ACM, 2012,295–304.

[25]

R. B. Sidje, Expokit: A software package for computing matrix exponentials, ACM Transactions on Mathematical Software (TOMS), 24 (1998), 130-156.

[26]

M. Sniedovich, Dijkstra's algorithm revisited: the dynamic programming connexion, Control and cybernetics, 35 (2006), 599-620.

[27]

T. J. Taylor and I. Z. Kiss, Interdependency and hierarchy of exact and approximate epidemic models on networks, Journal of mathematical biology, 69 (2014), 183-211. doi: 10.1007/s00285-013-0699-x.

[28]

P. Van Mieghem and J. Omic, In-homogeneous virus spread in networks, arXiv preprint, arXiv: 1306.2588.

[29]

P. Van MieghemJ. Omic and R. Kooij, Virus spread in networks, Networking, IEEE/ACM Transactions on, 17 (2009), 1-14.

[30]

C. WangW. Chen and Y. Wang, Scalable influence maximization for independent cascade model in large-scale social networks, Data Mining and Knowledge Discovery, 25 (2012), 545-576. doi: 10.1007/s10618-012-0262-1.

[31]

Y. Wang, D. Chakrabarti, C. Wang and C. Faloutsos, Epidemic spreading in real networks: An eigenvalue viewpoint, in Reliable Distributed Systems, 2003. Proceedings. 22nd International Symposium on, IEEE, 2003, 25–34.

[32]

J. Xue and Q. Ye, Computing exponentials of essentially non-negative matrices entrywise to high relative accuracy, Mathematics of Computation, 82 (2013), 1577-1596. doi: 10.1090/S0025-5718-2013-02677-4.

show all references

References:
[1]

S. BoccalettiG. BianconiR. CriadoC. I. Del GenioJ. Gómez-GardeñesM. RomanceI. Sendiña-NadalZ. Wang and M. Zanin, The structure and dynamics of multilayer networks, Physics Reports, 544 (2014), 1-122. doi: 10.1016/j.physrep.2014.07.001.

[2]

W. Bock, T. Fattler, I. Rodiah and O. Tse, An analytic method for agent-based modeling of spatially inhomogeneous disease dynamics, in AIP Conference Proceedings, vol. 1871, AIP Publishing, 2017, 1–11.

[3]

M. Boguná and R. Pastor-Satorras, Epidemic spreading in correlated complex networks, Physical Review E, 66 (2002), 047104.

[4]

E. Cator and P. Van Mieghem, Second-order mean-field susceptible-infected-susceptible epidemic threshold, Physical review E, 85 (2012), 056111.

[5]

R. CheW. HuangY. Li and P. Tetali, Convergence to global equilibrium for fokker-planck equations on a graph and talagrand-type inequalities, Journal of Differential Equations, 261 (2016), 2552-2583. doi: 10.1016/j.jde.2016.05.003.

[6]

S.-N. ChowW. HuangY. Li and H. Zhou, Fokker-planck equations for a free energy functional or markov process on a graph, Archive for Rational Mechanics and Analysis, 203 (2012), 969-1008. doi: 10.1007/s00205-011-0471-6.

[7]

E. Cohen, D. Delling, T. Pajor and R. F. Werneck, Timed influence: Computation and maximization, arXiv preprint, arXiv: 1410.6976.

[8]

P. Cui, S. Jin, L. Yu, F. Wang, W. Zhu and S. Yang, Cascading outbreak prediction in networks: A data-driven approach, in Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2013,901–909.

[9]

G. DemirelF. VazquezG. Böhme and T. Gross, Moment-closure approximations for discrete adaptive networks, Physica D: Nonlinear Phenomena, 267 (2014), 68-80. doi: 10.1016/j.physd.2013.07.003.

[10]

N. Du, Y. Liang, M.-F. Balcan and L. Song, Influence function learning in information diffusion networks, in International Conference on Machine Learning, 2014, 2016–2024.

[11]

N. Du, L. Song, M. Gomez-Rodriguez and H. Zha, Scalable influence estimation in continuoustime diffusion networks, in Advances in Neural Information Processing Systems, 2013, 3147– 3155.

[12]

M. Erbar and J. Maas, Ricci curvature of finite Markov chains via convexity of the entropy, Arch. Ration. Mech. Anal., 206 (2012), 997-1038. doi: 10.1007/s00205-012-0554-z.

[13]

M. Gomez Rodriguez, B. Schölkopf, L. J. Pineau et al., Influence maximization in continuous time diffusion networks, in 29th International Conference on Machine Learning (ICML 2012), International Machine Learning Society, 2012, 1–8.

[14]

D. KempeJ. Kleinberg and É. Tardos, Maximizing the spread of influence through a social network, Theory Comput., 11 (2015), 105-147. doi: 10.4086/toc.2015.v011a004.

[15]

J. O. Kephart and S. R. White, Directed-graph epidemiological models of computer viruses, in Research in Security and Privacy, 1991. Proceedings., 1991 IEEE Computer Society Symposium on, IEEE, 1991,343–359.

[16]

J. Leskovec, L. Backstrom and J. Kleinberg, Meme-tracking and the dynamics of the news cycle, in Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2009,497–506.

[17]

J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen and N. Glance, Cost-effective outbreak detection in networks, in Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, 2007,420–429.

[18]

J. LindquistJ. MaP. Van den Driessche and F. H. Willeboordse, Effective degree network disease models, Journal of mathematical biology, 62 (2011), 143-164. doi: 10.1007/s00285-010-0331-2.

[19]

V. Marceau, P.-A. Noël, L. Hébert-Dufresne, A. Allard and L. J. Dubé, Adaptive networks: Coevolution of disease and topology, Physical Review E, 82 (2010), 036116, 10pp. doi: 10.1103/PhysRevE.82.036116.

[20]

J. C. Miller and I. Z. Kiss, Epidemic spread in networks: Existing methods and current challenges, Mathematical Modelling of Natural Phenomena, 9 (2014), 4-42. doi: 10.1051/mmnp/20149202.

[21]

C. Moler and C. Van Loan, Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM review, 45 (2003), 3-49. doi: 10.1137/S00361445024180.

[22]

M. Newman, Networks: An Introduction, Oxford University Press, 2010. doi: 10.1093/acprof:oso/9780199206650.001.0001.

[23]

R. Pastor-SatorrasC. CastellanoP. Van Mieghem and A. Vespignani, Epidemic processes in complex networks, Reviews of modern physics, 87 (2015), 925-979. doi: 10.1103/RevModPhys.87.925.

[24]

H. Ryu, M. Lease and N. Woodward, Finding and exploring memes in social media, in Proceedings of the 23rd ACM conference on Hypertext and social media, ACM, 2012,295–304.

[25]

R. B. Sidje, Expokit: A software package for computing matrix exponentials, ACM Transactions on Mathematical Software (TOMS), 24 (1998), 130-156.

[26]

M. Sniedovich, Dijkstra's algorithm revisited: the dynamic programming connexion, Control and cybernetics, 35 (2006), 599-620.

[27]

T. J. Taylor and I. Z. Kiss, Interdependency and hierarchy of exact and approximate epidemic models on networks, Journal of mathematical biology, 69 (2014), 183-211. doi: 10.1007/s00285-013-0699-x.

[28]

P. Van Mieghem and J. Omic, In-homogeneous virus spread in networks, arXiv preprint, arXiv: 1306.2588.

[29]

P. Van MieghemJ. Omic and R. Kooij, Virus spread in networks, Networking, IEEE/ACM Transactions on, 17 (2009), 1-14.

[30]

C. WangW. Chen and Y. Wang, Scalable influence maximization for independent cascade model in large-scale social networks, Data Mining and Knowledge Discovery, 25 (2012), 545-576. doi: 10.1007/s10618-012-0262-1.

[31]

Y. Wang, D. Chakrabarti, C. Wang and C. Faloutsos, Epidemic spreading in real networks: An eigenvalue viewpoint, in Reliable Distributed Systems, 2003. Proceedings. 22nd International Symposium on, IEEE, 2003, 25–34.

[32]

J. Xue and Q. Ye, Computing exponentials of essentially non-negative matrices entrywise to high relative accuracy, Mathematics of Computation, 82 (2013), 1577-1596. doi: 10.1090/S0025-5718-2013-02677-4.

Figure 1.  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$
Figure 2.  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
Figure 3.  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
Figure 4.  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

Metrics

  • PDF downloads (3)
  • HTML views (28)
  • Cited by (0)

[Back to Top]