Advanced Search
Article Contents
Article Contents

Influence prediction for continuous-time information propagation on networks

  • * Corresponding author: Xiaojing Ye

    * Corresponding author: Xiaojing Ye 
Abstract Full Text(HTML) Figure(4) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 65C40, 65Y10; Secondary: 68U35.


    \begin{equation} \\ \end{equation}
  • 加载中
  • 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] 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.
  • 加载中



Article Metrics

HTML views(829) PDF downloads(280) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint