# American Institute of Mathematical Sciences

July  2014, 19(5): 1335-1354. doi: 10.3934/dcdsb.2014.19.1335

## Latent self-exciting point process model for spatial-temporal networks

 1 USC Information Sciences Institute, Marina del Rey, CA 90292, United States 2 USC Information Sciences Institute, United States 3 University of California, Los Angeles, United States 4 University of California, Irvine, United States

Received  December 2012 Revised  April 2013 Published  April 2014

We propose a latent self-exciting point process model that describes geographically distributed interactions between pairs of entities. In contrast to most existing approaches that assume fully observable interactions, here we consider a scenario where certain interaction events lack information about participants. Instead, this information needs to be inferred from the available observations. We develop an efficient approximate algorithm based on variational expectation-maximization to infer unknown participants in an event given the location and the time of the event. We validate the model on synthetic as well as real-world data, and obtain very promising results on the identity-inference task. We also use our model to predict the timing and participants of future events, and demonstrate that it compares favorably with baseline approaches.
Citation: Yoon-Sik Cho, Aram Galstyan, P. Jeffrey Brantingham, George Tita. Latent self-exciting point process model for spatial-temporal networks. Discrete & Continuous Dynamical Systems - B, 2014, 19 (5) : 1335-1354. doi: 10.3934/dcdsb.2014.19.1335
##### References:
 [1] E. M. Airoldi, D. M. Blei, S. E. Fienberg and E. P. Xing, Mixed membership stochastic blockmodels,, Journal of Machine Learning Research, 9 (2008), 1981. [2] S. Azizpour, K. Giesecke, S. F. Discussions, X. Ding, B. Kim and S. Mudchanatongsuk, Self-exciting corporate defaults: Contagion vs. frailty,, 2008., (). [3] A.-L. Barabási, The origin of bursts and heavy tails in human dynamics,, Nature, 435 (2005), 207. [4] M. Beal and Z. Ghahramani, The variational bayesian em algorithm for incomplete data: With application to scoring graphical model structures,, Bayesian Statistics, 7 (2003), 453. [5] P. Bremaud, Point Processes and Queues : Martingale Dynamics,, Springer series in statistics, (1981). [6] E. Cho, S. A. Myers and J. Leskovec, Friendship and mobility: User movement in location-based social networks,, in Proc. of the KDD'11, (2011), 1082. doi: 10.1145/2020408.2020579. [7] N. Cressie and C. K. Wikle, Statistics for Spatio-Temporal Data,, (Wiley Series in Probability and Statistics) Wiley, (2011). [8] N. Du, L. Song, A. Smola and M. Yuan, Learning Networks of Heterogeneous Influence,, In Advances Neural Information Processing Systems, (2012). [9] E. Errais, K. Giesecke and L. Goldberg, Affine point processes and portfolio credit risk,, SIAM Journal on Financial Mathematics, 1 (2010), 642. doi: 10.1137/090771272. [10] R. Eyal, S. Kraus and A. Rosenfeld, Identifying Missing Node Information in Social Networks,, in AAAI'11, (2011). [11] Y. Fan and C. R. Shelton, Learning continuous-time social network dynamics,, in Proc. of the 25th Conference on Uncertainty in Artificial Intelligence, (2009), 161. [12] M. Gomez-Rodriguez, J. Leskovec and A. Krause, Inferring Networks of Diffusion and Influence,, in ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining (ACM KDD), 16 (2010), 1019. doi: 10.1145/1835804.1835933. [13] M. Gomez-Rodriguez, J. Leskovec and B. Schölkopf, Structure and Dynamics of Information Pathways in Online Media,, in WSDM, 6 (2013), 23. doi: 10.1145/2433396.2433402. [14] M. Gomez-Rodriguez, J. Leskovec and B. Schölkopf, Modeling Information Propagation with Survival Theory,, in ICML, (2013). [15] R. Guimerà and M. Sales-Pardo, Missing and spurious interactions and the reconstruction of complex networks,, PNAS, 106 (2009), 22073. doi: 10.1073/pnas.0908366106. [16] A. Gunawardana, C. Meek and P. Xu, A model for temporal dependencies in event streams,, in Advances in Neural Information Processing Systems, 24 (2011), 1962. [17] S. Hanneke, W. Fu and E. Xing, Discrete temporal models of social networks,, Electronic Journal of Statistics, 4 (2010), 585. doi: 10.1214/09-EJS548. [18] R. Hegemann, E. Lewis and A. Bertozzi, An Estimate & Score Algorithm for simultaneous parameter estimation and reconstruction of incomplete data on social network,, Security Informatics, 2 (2013). doi: 10.1186/2190-8532-2-1. [19] M. Kim and J. Leskovec, The network completion problem: Inferring missing nodes and edges in networks,, in SDM, (2011), 47. doi: 10.1137/1.9781611972818.5. [20] G. Kossinets, Effects of missing data in social networks,, Social Networks, 28 (2006), 247. doi: 10.1016/j.socnet.2005.07.002. [21] D. Liben-Nowell and J. Kleinberg, The link-prediction problem for social networks,, Journal of the American Society for Information Science and Technology, 58 (2007), 1019. [22] G. O. Mohler, M. B. Short, P. J. Brantingham, F. P. Schoenberg and G. E. Tita, Self-exciting point process modeling of crime,, Journal of the American Statistical Association, 106 (2011), 100. doi: 10.1198/jasa.2011.ap09546. [23] P. Netrapalli and S. Sanghavi, Learning the graph of epidemic cascades,, In Procs. of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems, (2012), 211. doi: 10.1145/2254756.2254783. [24] Y. Ogata, Space-time point process models for earthquake occurrences,, Ann. Inst. Statist. Math., 50 (1988), 379. doi: 10.1023/A:1003403601725. [25] D. Pelleg and A. W. Moore, X-means: Extending K-means with Efficient Estimation of the Number of Clusters,, Proceedings of the Seventeenth International Conference on Machine Learning, (2000), 727. [26] P. O. Perry and P. J. Wolfe, Point process modeling for directed interaction networks,, Journal of the Royal Statistical Society, 75 (2013), 821. doi: 10.1111/rssb.12013. [27] P.Lewis and G.Shedler, Simulation of nonhomogenous Poisson processes by thinning,, Naval Research Logistics Quarterly, 26 (1979), 403. doi: 10.1002/nav.3800260304. [28] M. D. Porter and G. White, Self-exciting hurdle models for terrorist activity,, The Annals of Applied Statistics, 6 (2012), 106. doi: 10.1214/11-AOAS513. [29] S. Rajarm, T. Graepel and R. Herbrich, Poisson-networks: A Model for Structured Point Processes,, in Proceedings of the International Workshop on Artificial Intelligence and Statistics, (2005). [30] A. Simma and M. I. Jordan, Modeling Events with Cascades of Poisson Processes,, in Proceedings of the Twenty sixth International Conference on Uncertainty in Artificial Intelligence, (2010). [31] C. Steglich, T. A. B. Snijders and M. Pearson, Dynamic Networks and Behavior: Separating Selection from Influence,, Sociological Methodology, (2010). doi: 10.1111/j.1467-9531.2010.01225.x. [32] J. Stehlé, A. Barrat and G. Bianconi, Dynamical and bursty interactions in social networks,, Phys. Rev. E, 81 (2010). doi: 10.1103/PhysRevE.81.035101. [33] A. Stomakhin, M. B. Short and A. L. Bertozzi, Reconstruction of missing data in social networks based on temporal patterns of interactions,, Inverse Problems, 27 (2011). doi: 10.1088/0266-5611/27/11/115013. [34] G. Tita, J. K. Riley, G. Ridgeway, C. Grammich, A. F. Abrahamse and P. Greenwood, Reducing Gun Violence: Results from an Intervention in East Los Angeles,, RAND Press, (2003). [35] G. Ver Steeg and A. Galstyan, Information Transfer in Social Media,, in Proc. of WWW, (2012). [36] G. Ver Steeg and A. Galstyan, Information-Theoretic Measures of Influence Based on Content Dynamics,, in Proc. of WSDM, (2013). [37] D. Vu, A. U. Asuncion, D. Hunter and P. Smyth, Continuous-time regression models for longitudinal networks,, in NIPS, (2011), 2492. [38] L. Wang, S. Ermon and J. Hopcroft, Feature-enhanced probabilistic models for diffusion network inference,, Lecture Notes in Computer Science, 7524 (2012), 499. doi: 10.1007/978-3-642-33486-3_32.

show all references

##### References:
 [1] E. M. Airoldi, D. M. Blei, S. E. Fienberg and E. P. Xing, Mixed membership stochastic blockmodels,, Journal of Machine Learning Research, 9 (2008), 1981. [2] S. Azizpour, K. Giesecke, S. F. Discussions, X. Ding, B. Kim and S. Mudchanatongsuk, Self-exciting corporate defaults: Contagion vs. frailty,, 2008., (). [3] A.-L. Barabási, The origin of bursts and heavy tails in human dynamics,, Nature, 435 (2005), 207. [4] M. Beal and Z. Ghahramani, The variational bayesian em algorithm for incomplete data: With application to scoring graphical model structures,, Bayesian Statistics, 7 (2003), 453. [5] P. Bremaud, Point Processes and Queues : Martingale Dynamics,, Springer series in statistics, (1981). [6] E. Cho, S. A. Myers and J. Leskovec, Friendship and mobility: User movement in location-based social networks,, in Proc. of the KDD'11, (2011), 1082. doi: 10.1145/2020408.2020579. [7] N. Cressie and C. K. Wikle, Statistics for Spatio-Temporal Data,, (Wiley Series in Probability and Statistics) Wiley, (2011). [8] N. Du, L. Song, A. Smola and M. Yuan, Learning Networks of Heterogeneous Influence,, In Advances Neural Information Processing Systems, (2012). [9] E. Errais, K. Giesecke and L. Goldberg, Affine point processes and portfolio credit risk,, SIAM Journal on Financial Mathematics, 1 (2010), 642. doi: 10.1137/090771272. [10] R. Eyal, S. Kraus and A. Rosenfeld, Identifying Missing Node Information in Social Networks,, in AAAI'11, (2011). [11] Y. Fan and C. R. Shelton, Learning continuous-time social network dynamics,, in Proc. of the 25th Conference on Uncertainty in Artificial Intelligence, (2009), 161. [12] M. Gomez-Rodriguez, J. Leskovec and A. Krause, Inferring Networks of Diffusion and Influence,, in ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining (ACM KDD), 16 (2010), 1019. doi: 10.1145/1835804.1835933. [13] M. Gomez-Rodriguez, J. Leskovec and B. Schölkopf, Structure and Dynamics of Information Pathways in Online Media,, in WSDM, 6 (2013), 23. doi: 10.1145/2433396.2433402. [14] M. Gomez-Rodriguez, J. Leskovec and B. Schölkopf, Modeling Information Propagation with Survival Theory,, in ICML, (2013). [15] R. Guimerà and M. Sales-Pardo, Missing and spurious interactions and the reconstruction of complex networks,, PNAS, 106 (2009), 22073. doi: 10.1073/pnas.0908366106. [16] A. Gunawardana, C. Meek and P. Xu, A model for temporal dependencies in event streams,, in Advances in Neural Information Processing Systems, 24 (2011), 1962. [17] S. Hanneke, W. Fu and E. Xing, Discrete temporal models of social networks,, Electronic Journal of Statistics, 4 (2010), 585. doi: 10.1214/09-EJS548. [18] R. Hegemann, E. Lewis and A. Bertozzi, An Estimate & Score Algorithm for simultaneous parameter estimation and reconstruction of incomplete data on social network,, Security Informatics, 2 (2013). doi: 10.1186/2190-8532-2-1. [19] M. Kim and J. Leskovec, The network completion problem: Inferring missing nodes and edges in networks,, in SDM, (2011), 47. doi: 10.1137/1.9781611972818.5. [20] G. Kossinets, Effects of missing data in social networks,, Social Networks, 28 (2006), 247. doi: 10.1016/j.socnet.2005.07.002. [21] D. Liben-Nowell and J. Kleinberg, The link-prediction problem for social networks,, Journal of the American Society for Information Science and Technology, 58 (2007), 1019. [22] G. O. Mohler, M. B. Short, P. J. Brantingham, F. P. Schoenberg and G. E. Tita, Self-exciting point process modeling of crime,, Journal of the American Statistical Association, 106 (2011), 100. doi: 10.1198/jasa.2011.ap09546. [23] P. Netrapalli and S. Sanghavi, Learning the graph of epidemic cascades,, In Procs. of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems, (2012), 211. doi: 10.1145/2254756.2254783. [24] Y. Ogata, Space-time point process models for earthquake occurrences,, Ann. Inst. Statist. Math., 50 (1988), 379. doi: 10.1023/A:1003403601725. [25] D. Pelleg and A. W. Moore, X-means: Extending K-means with Efficient Estimation of the Number of Clusters,, Proceedings of the Seventeenth International Conference on Machine Learning, (2000), 727. [26] P. O. Perry and P. J. Wolfe, Point process modeling for directed interaction networks,, Journal of the Royal Statistical Society, 75 (2013), 821. doi: 10.1111/rssb.12013. [27] P.Lewis and G.Shedler, Simulation of nonhomogenous Poisson processes by thinning,, Naval Research Logistics Quarterly, 26 (1979), 403. doi: 10.1002/nav.3800260304. [28] M. D. Porter and G. White, Self-exciting hurdle models for terrorist activity,, The Annals of Applied Statistics, 6 (2012), 106. doi: 10.1214/11-AOAS513. [29] S. Rajarm, T. Graepel and R. Herbrich, Poisson-networks: A Model for Structured Point Processes,, in Proceedings of the International Workshop on Artificial Intelligence and Statistics, (2005). [30] A. Simma and M. I. Jordan, Modeling Events with Cascades of Poisson Processes,, in Proceedings of the Twenty sixth International Conference on Uncertainty in Artificial Intelligence, (2010). [31] C. Steglich, T. A. B. Snijders and M. Pearson, Dynamic Networks and Behavior: Separating Selection from Influence,, Sociological Methodology, (2010). doi: 10.1111/j.1467-9531.2010.01225.x. [32] J. Stehlé, A. Barrat and G. Bianconi, Dynamical and bursty interactions in social networks,, Phys. Rev. E, 81 (2010). doi: 10.1103/PhysRevE.81.035101. [33] A. Stomakhin, M. B. Short and A. L. Bertozzi, Reconstruction of missing data in social networks based on temporal patterns of interactions,, Inverse Problems, 27 (2011). doi: 10.1088/0266-5611/27/11/115013. [34] G. Tita, J. K. Riley, G. Ridgeway, C. Grammich, A. F. Abrahamse and P. Greenwood, Reducing Gun Violence: Results from an Intervention in East Los Angeles,, RAND Press, (2003). [35] G. Ver Steeg and A. Galstyan, Information Transfer in Social Media,, in Proc. of WWW, (2012). [36] G. Ver Steeg and A. Galstyan, Information-Theoretic Measures of Influence Based on Content Dynamics,, in Proc. of WSDM, (2013). [37] D. Vu, A. U. Asuncion, D. Hunter and P. Smyth, Continuous-time regression models for longitudinal networks,, in NIPS, (2011), 2492. [38] L. Wang, S. Ermon and J. Hopcroft, Feature-enhanced probabilistic models for diffusion network inference,, Lecture Notes in Computer Science, 7524 (2012), 499. doi: 10.1007/978-3-642-33486-3_32.
 [1] Hui Meng, Fei Lung Yuen, Tak Kuen Siu, Hailiang Yang. Optimal portfolio in a continuous-time self-exciting threshold model. Journal of Industrial & Management Optimization, 2013, 9 (2) : 487-504. doi: 10.3934/jimo.2013.9.487 [2] Aniello Raffaele Patrone, Otmar Scherzer. On a spatial-temporal decomposition of optical flow. Inverse Problems & Imaging, 2017, 11 (4) : 761-781. doi: 10.3934/ipi.2017036 [3] Raimund Bürger, Gerardo Chowell, Pep Mulet, Luis M. Villada. Modelling the spatial-temporal progression of the 2009 A/H1N1 influenza pandemic in Chile. Mathematical Biosciences & Engineering, 2016, 13 (1) : 43-65. doi: 10.3934/mbe.2016.13.43 [4] Daniil Kazantsev, William M. Thompson, William R. B. Lionheart, Geert Van Eyndhoven, Anders P. Kaestner, Katherine J. Dobson, Philip J. Withers, Peter D. Lee. 4D-CT reconstruction with unified spatial-temporal patch-based regularization. Inverse Problems & Imaging, 2015, 9 (2) : 447-467. doi: 10.3934/ipi.2015.9.447 [5] Jiao-Yan Li, Xiao Hu, Zhong Wan. An integrated bi-objective optimization model and improved genetic algorithm for vehicle routing problems with temporal and spatial constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-18. doi: 10.3934/jimo.2018200 [6] Baolan Yuan, Wanjun Zhang, Yubo Yuan. A Max-Min clustering method for $k$-means algorithm of data clustering. Journal of Industrial & Management Optimization, 2012, 8 (3) : 565-575. doi: 10.3934/jimo.2012.8.565 [7] William Chad Young, Adrian E. Raftery, Ka Yee Yeung. A posterior probability approach for gene regulatory network inference in genetic perturbation data. Mathematical Biosciences & Engineering, 2016, 13 (6) : 1241-1251. doi: 10.3934/mbe.2016041 [8] Shi Yan, Jun Liu, Haiyang Huang, Xue-Cheng Tai. A dual EM algorithm for TV regularized Gaussian mixture model in image segmentation. Inverse Problems & Imaging, 2019, 13 (3) : 653-677. doi: 10.3934/ipi.2019030 [9] Mohammad Afzalinejad, Zahra Abbasi. A slacks-based model for dynamic data envelopment analysis. Journal of Industrial & Management Optimization, 2019, 15 (1) : 275-291. doi: 10.3934/jimo.2018043 [10] Joanna Tyrcha, John Hertz. Network inference with hidden units. Mathematical Biosciences & Engineering, 2014, 11 (1) : 149-165. doi: 10.3934/mbe.2014.11.149 [11] Tieliang Gong, Qian Zhao, Deyu Meng, Zongben Xu. Why curriculum learning & self-paced learning work in big/noisy data: A theoretical perspective. Big Data & Information Analytics, 2016, 1 (1) : 111-127. doi: 10.3934/bdia.2016.1.111 [12] Jiangchuan Fan, Xinyu Guo, Jianjun Du, Weiliang Wen, Xianju Lu, Brahmani Louiza. Analysis of the clustering fusion algorithm for multi-band color image. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1233-1249. doi: 10.3934/dcdss.2019085 [13] Jiangtao Mo, Liqun Qi, Zengxin Wei. A network simplex algorithm for simple manufacturing network model. Journal of Industrial & Management Optimization, 2005, 1 (2) : 251-273. doi: 10.3934/jimo.2005.1.251 [14] Jiang Xie, Junfu Xu, Celine Nie, Qing Nie. Machine learning of swimming data via wisdom of crowd and regression analysis. Mathematical Biosciences & Engineering, 2017, 14 (2) : 511-527. doi: 10.3934/mbe.2017031 [15] Mostafa Karimi, Noor Akma Ibrahim, Mohd Rizam Abu Bakar, Jayanthi Arasan. Rank-based inference for the accelerated failure time model in the presence of interval censored data. Numerical Algebra, Control & Optimization, 2017, 7 (1) : 107-112. doi: 10.3934/naco.2017007 [16] Aiwan Fan, Qiming Wang, Joyati Debnath. A high precision data encryption algorithm in wireless network mobile communication. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1327-1340. doi: 10.3934/dcdss.2019091 [17] Débora A. F. Albanez, Maicon J. Benvenutti. Continuous data assimilation algorithm for simplified Bardina model. Evolution Equations & Control Theory, 2018, 7 (1) : 33-52. doi: 10.3934/eect.2018002 [18] Pawan Lingras, Farhana Haider, Matt Triff. Fuzzy temporal meta-clustering of financial trading volatility patterns. Big Data & Information Analytics, 2017, 2 (5) : 1-20. doi: 10.3934/bdia.2017018 [19] Umberto Mosco. Impulsive motion on synchronized spatial temporal grids. Discrete & Continuous Dynamical Systems - A, 2017, 37 (12) : 6069-6098. doi: 10.3934/dcds.2017261 [20] Shi'an Wang, N. U. Ahmed. Optimum management of the network of city bus routes based on a stochastic dynamic model. Journal of Industrial & Management Optimization, 2019, 15 (2) : 619-631. doi: 10.3934/jimo.2018061

2018 Impact Factor: 1.008