# 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 and 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-2014. [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-211. [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-464. [5] P. Bremaud, Point Processes and Queues : Martingale Dynamics, Springer series in statistics, Springer-Verlag, New York, 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-1090. 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-665. 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-168. [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-1028. 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-32. 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-22078. 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-1970. [17] S. Hanneke, W. Fu and E. Xing, Discrete temporal models of social networks, Electronic Journal of Statistics, 4 (2010), 585-605. 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, SIAM / Omnipress, (2011), 47-58. doi: 10.1137/1.9781611972818.5. [20] G. Kossinets, Effects of missing data in social networks, Social Networks, 28 (2006), 247-268. 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-1031. [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-108. 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-222. doi: 10.1145/2254756.2254783. [24] Y. Ogata, Space-time point process models for earthquake occurrences, Ann. Inst. Statist. Math., 50 (1988), 379-402. 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, ICML '00, Morgan Kaufmann Publishers Inc., San Francisco, (2000), 727-734. [26] P. O. Perry and P. J. Wolfe, Point process modeling for directed interaction networks, Journal of the Royal Statistical Society, Series B, 75 (2013), 821-849. 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-413. 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-124. 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), 035101. 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), 115013. 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-2500. [38] L. Wang, S. Ermon and J. Hopcroft, Feature-enhanced probabilistic models for diffusion network inference, Lecture Notes in Computer Science, 7524 (2012), 499-514. 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-2014. [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-211. [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-464. [5] P. Bremaud, Point Processes and Queues : Martingale Dynamics, Springer series in statistics, Springer-Verlag, New York, 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-1090. 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-665. 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-168. [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-1028. 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-32. 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-22078. 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-1970. [17] S. Hanneke, W. Fu and E. Xing, Discrete temporal models of social networks, Electronic Journal of Statistics, 4 (2010), 585-605. 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, SIAM / Omnipress, (2011), 47-58. doi: 10.1137/1.9781611972818.5. [20] G. Kossinets, Effects of missing data in social networks, Social Networks, 28 (2006), 247-268. 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-1031. [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-108. 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-222. doi: 10.1145/2254756.2254783. [24] Y. Ogata, Space-time point process models for earthquake occurrences, Ann. Inst. Statist. Math., 50 (1988), 379-402. 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, ICML '00, Morgan Kaufmann Publishers Inc., San Francisco, (2000), 727-734. [26] P. O. Perry and P. J. Wolfe, Point process modeling for directed interaction networks, Journal of the Royal Statistical Society, Series B, 75 (2013), 821-849. 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-413. 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-124. 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), 035101. 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), 115013. 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-2500. [38] L. Wang, S. Ermon and J. Hopcroft, Feature-enhanced probabilistic models for diffusion network inference, Lecture Notes in Computer Science, 7524 (2012), 499-514. 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 and Management Optimization, 2013, 9 (2) : 487-504. doi: 10.3934/jimo.2013.9.487 [2] Wei Wang, Yang Shen, Linyi Qian, Zhixin Yang. Hedging strategy for unit-linked life insurance contracts with self-exciting jump clustering. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021072 [3] Zhouchao Wei, Fanrui Wang, Huijuan Li, Wei Zhang. Jacobi stability analysis and impulsive control of a 5D self-exciting homopolar disc dynamo. Discrete and Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021263 [4] Aniello Raffaele Patrone, Otmar Scherzer. On a spatial-temporal decomposition of optical flow. Inverse Problems and Imaging, 2017, 11 (4) : 761-781. doi: 10.3934/ipi.2017036 [5] 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 [6] 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 and Imaging, 2015, 9 (2) : 447-467. doi: 10.3934/ipi.2015.9.447 [7] Zhun Gou, Nan-jing Huang, Ming-hui Wang, Yao-jia Zhang. A stochastic optimal control problem governed by SPDEs via a spatial-temporal interaction operator. Mathematical Control and Related Fields, 2021, 11 (2) : 291-312. doi: 10.3934/mcrf.2020037 [8] 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 and Management Optimization, 2020, 16 (3) : 1203-1220. doi: 10.3934/jimo.2018200 [9] Baolan Yuan, Wanjun Zhang, Yubo Yuan. A Max-Min clustering method for $k$-means algorithm of data clustering. Journal of Industrial and Management Optimization, 2012, 8 (3) : 565-575. doi: 10.3934/jimo.2012.8.565 [10] Shi Yan, Jun Liu, Haiyang Huang, Xue-Cheng Tai. A dual EM algorithm for TV regularized Gaussian mixture model in image segmentation. Inverse Problems and Imaging, 2019, 13 (3) : 653-677. doi: 10.3934/ipi.2019030 [11] 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 [12] Mohammad Afzalinejad, Zahra Abbasi. A slacks-based model for dynamic data envelopment analysis. Journal of Industrial and Management Optimization, 2019, 15 (1) : 275-291. doi: 10.3934/jimo.2018043 [13] Jiangchuan Fan, Xinyu Guo, Jianjun Du, Weiliang Wen, Xianju Lu, Brahmani Louiza. Analysis of the clustering fusion algorithm for multi-band color image. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1233-1249. doi: 10.3934/dcdss.2019085 [14] Marc Bocquet, Julien Brajard, Alberto Carrassi, Laurent Bertino. Bayesian inference of chaotic dynamics by merging data assimilation, machine learning and expectation-maximization. Foundations of Data Science, 2020, 2 (1) : 55-80. doi: 10.3934/fods.2020004 [15] Joanna Tyrcha, John Hertz. Network inference with hidden units. Mathematical Biosciences & Engineering, 2014, 11 (1) : 149-165. doi: 10.3934/mbe.2014.11.149 [16] Qianqian Wang, Minan Tang, Aimin An, Jiawei Lu, Yingying Zhao. Parameter optimal identification and dynamic behavior analysis of nonlinear model for the solution purification process of zinc hydrometallurgy. Journal of Industrial and Management Optimization, 2022, 18 (1) : 693-712. doi: 10.3934/jimo.2021159 [17] Tao Zheng, Yantao Luo, Xinran Zhou, Long Zhang, Zhidong Teng. Spatial dynamic analysis for COVID-19 epidemic model with diffusion and Beddington-DeAngelis type incidence. Communications on Pure and Applied Analysis, , () : -. doi: 10.3934/cpaa.2021154 [18] Francesco Sanna Passino, Nicholas A. Heard. Modelling dynamic network evolution as a Pitman-Yor process. Foundations of Data Science, 2019, 1 (3) : 293-306. doi: 10.3934/fods.2019013 [19] Jiangtao Mo, Liqun Qi, Zengxin Wei. A network simplex algorithm for simple manufacturing network model. Journal of Industrial and Management Optimization, 2005, 1 (2) : 251-273. doi: 10.3934/jimo.2005.1.251 [20] Richard Archibald, Hoang Tran. A dictionary learning algorithm for compression and reconstruction of streaming data in preset order. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 655-668. doi: 10.3934/dcdss.2021102

2020 Impact Factor: 1.327