Influence prediction for continuous-time information propagation on networks

Shui-Nee Chow; Xiaojing Ye; Hongyuan Zha; Haomin Zhou; Shui-Nee Chow; Xiaojing Ye; Hongyuan Zha; Haomin Zhou

doi:10.3934/nhm.2018026

Networks and Heterogeneous Media

2018, Volume 13, Issue 4: 567-583. doi: 10.3934/nhm.2018026

Previous Article Next Article

Influence prediction for continuous-time information propagation on networks

Shui-Nee Chow ^{1
,},
Xiaojing Ye ^{2
,
,},
Hongyuan Zha ^{3
,},
Haomin Zhou ^{1
,}

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

Received: 01 November 2017 Revised: 01 June 2018
Primary: 65C40, 65Y10; Secondary: 68U35

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.
- Propagation network,
- continuous time,
- information propagation,
- Markov process,
- Fokker-Planck equations,
- influence prediction
Citation: Shui-Nee Chow, Xiaojing Ye, Hongyuan Zha, Haomin Zhou. Influence prediction for continuous-time information propagation on networks[J]. Networks and Heterogeneous Media, 2018, 13(4): 567-583. doi: 10.3934/nhm.2018026

Related Papers:

Abstract

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.

References

[1]	The structure and dynamics of multilayer networks. Physics Reports (2014) 544: 1-122.
[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]	Convergence to global equilibrium for fokker-planck equations on a graph and talagrand-type inequalities. Journal of Differential Equations (2016) 261: 2552-2583.
[6]	Fokker-planck equations for a free energy functional or markov process on a graph. Archive for Rational Mechanics and Analysis (2012) 203: 969-1008.
[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]	Moment-closure approximations for discrete adaptive networks. Physica D: Nonlinear Phenomena (2014) 267: 68-80.
[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]	Ricci curvature of finite Markov chains via convexity of the entropy. Arch. Ration. Mech. Anal. (2012) 206: 997-1038.
[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]	Maximizing the spread of influence through a social network. Theory Comput. (2015) 11: 105-147.
[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]	Effective degree network disease models. Journal of mathematical biology (2011) 62: 143-164.
[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]	Epidemic spread in networks: Existing methods and current challenges. Mathematical Modelling of Natural Phenomena (2014) 9: 4-42.
[21]	Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM review (2003) 45: 3-49.
[22]	M. Newman, Networks: An Introduction, Oxford University Press, 2010. doi: 10.1093/acprof:oso/9780199206650.001.0001
[23]	Epidemic processes in complex networks. Reviews of modern physics (2015) 87: 925-979.
[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]	Expokit: A software package for computing matrix exponentials. ACM Transactions on Mathematical Software (TOMS) (1998) 24: 130-156.
[26]	Dijkstra's algorithm revisited: the dynamic programming connexion. Control and cybernetics (2006) 35: 599-620.
[27]	Interdependency and hierarchy of exact and approximate epidemic models on networks. Journal of mathematical biology (2014) 69: 183-211.
[28]	P. Van Mieghem and J. Omic, In-homogeneous virus spread in networks, arXiv preprint, arXiv: 1306.2588.
[29]	Virus spread in networks. Networking, IEEE/ACM Transactions on (2009) 17: 1-14.
[30]	Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery (2012) 25: 545-576.
[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]	Computing exponentials of essentially non-negative matrices entrywise to high relative accuracy. Mathematics of Computation (2013) 82: 1577-1596.

Reader Comments

Your name:*

Email:*
© 2018 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)