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.   Google Scholar

[2]

S. Azizpour, K. Giesecke, S. F. Discussions, X. Ding, B. Kim and S. Mudchanatongsuk, Self-exciting corporate defaults: Contagion vs. frailty,, 2008., ().   Google Scholar

[3]

A.-L. Barabási, The origin of bursts and heavy tails in human dynamics,, Nature, 435 (2005), 207.   Google Scholar

[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.   Google Scholar

[5]

P. Bremaud, Point Processes and Queues : Martingale Dynamics,, Springer series in statistics, (1981).   Google Scholar

[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.  Google Scholar

[7]

N. Cressie and C. K. Wikle, Statistics for Spatio-Temporal Data,, (Wiley Series in Probability and Statistics) Wiley, (2011).   Google Scholar

[8]

N. Du, L. Song, A. Smola and M. Yuan, Learning Networks of Heterogeneous Influence,, In Advances Neural Information Processing Systems, (2012).   Google Scholar

[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.  Google Scholar

[10]

R. Eyal, S. Kraus and A. Rosenfeld, Identifying Missing Node Information in Social Networks,, in AAAI'11, (2011).   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

M. Gomez-Rodriguez, J. Leskovec and B. Schölkopf, Modeling Information Propagation with Survival Theory,, in ICML, (2013).   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

G. Kossinets, Effects of missing data in social networks,, Social Networks, 28 (2006), 247.  doi: 10.1016/j.socnet.2005.07.002.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[24]

Y. Ogata, Space-time point process models for earthquake occurrences,, Ann. Inst. Statist. Math., 50 (1988), 379.  doi: 10.1023/A:1003403601725.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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).   Google Scholar

[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).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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).   Google Scholar

[35]

G. Ver Steeg and A. Galstyan, Information Transfer in Social Media,, in Proc. of WWW, (2012).   Google Scholar

[36]

G. Ver Steeg and A. Galstyan, Information-Theoretic Measures of Influence Based on Content Dynamics,, in Proc. of WSDM, (2013).   Google Scholar

[37]

D. Vu, A. U. Asuncion, D. Hunter and P. Smyth, Continuous-time regression models for longitudinal networks,, in NIPS, (2011), 2492.   Google Scholar

[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.  Google Scholar

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.   Google Scholar

[2]

S. Azizpour, K. Giesecke, S. F. Discussions, X. Ding, B. Kim and S. Mudchanatongsuk, Self-exciting corporate defaults: Contagion vs. frailty,, 2008., ().   Google Scholar

[3]

A.-L. Barabási, The origin of bursts and heavy tails in human dynamics,, Nature, 435 (2005), 207.   Google Scholar

[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.   Google Scholar

[5]

P. Bremaud, Point Processes and Queues : Martingale Dynamics,, Springer series in statistics, (1981).   Google Scholar

[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.  Google Scholar

[7]

N. Cressie and C. K. Wikle, Statistics for Spatio-Temporal Data,, (Wiley Series in Probability and Statistics) Wiley, (2011).   Google Scholar

[8]

N. Du, L. Song, A. Smola and M. Yuan, Learning Networks of Heterogeneous Influence,, In Advances Neural Information Processing Systems, (2012).   Google Scholar

[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.  Google Scholar

[10]

R. Eyal, S. Kraus and A. Rosenfeld, Identifying Missing Node Information in Social Networks,, in AAAI'11, (2011).   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

M. Gomez-Rodriguez, J. Leskovec and B. Schölkopf, Modeling Information Propagation with Survival Theory,, in ICML, (2013).   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

G. Kossinets, Effects of missing data in social networks,, Social Networks, 28 (2006), 247.  doi: 10.1016/j.socnet.2005.07.002.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[24]

Y. Ogata, Space-time point process models for earthquake occurrences,, Ann. Inst. Statist. Math., 50 (1988), 379.  doi: 10.1023/A:1003403601725.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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).   Google Scholar

[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).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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).   Google Scholar

[35]

G. Ver Steeg and A. Galstyan, Information Transfer in Social Media,, in Proc. of WWW, (2012).   Google Scholar

[36]

G. Ver Steeg and A. Galstyan, Information-Theoretic Measures of Influence Based on Content Dynamics,, in Proc. of WSDM, (2013).   Google Scholar

[37]

D. Vu, A. U. Asuncion, D. Hunter and P. Smyth, Continuous-time regression models for longitudinal networks,, in NIPS, (2011), 2492.   Google Scholar

[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.  Google Scholar

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

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

Umberto Mosco. Impulsive motion on synchronized spatial temporal grids. Discrete & Continuous Dynamical Systems - A, 2017, 37 (12) : 6069-6098. doi: 10.3934/dcds.2017261

2018 Impact Factor: 1.008

Metrics

  • PDF downloads (7)
  • HTML views (0)
  • Cited by (4)

[Back to Top]