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]

Xin Guo, Lei Shi. Preface of the special issue on analysis in data science: Methods and applications. Mathematical Foundations of Computing, 2020, 3 (4) : i-ii. doi: 10.3934/mfc.2020026

[2]

Laurence Cherfils, Stefania Gatti, Alain Miranville, Rémy Guillevin. Analysis of a model for tumor growth and lactate exchanges in a glioma. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020457

[3]

Chao Xing, Jiaojiao Pan, Hong Luo. Stability and dynamic transition of a toxin-producing phytoplankton-zooplankton model with additional food. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020275

[4]

Hai-Feng Huo, Shi-Ke Hu, Hong Xiang. Traveling wave solution for a diffusion SEIR epidemic model with self-protection and treatment. Electronic Research Archive, , () : -. doi: 10.3934/era.2020118

[5]

Yining Cao, Chuck Jia, Roger Temam, Joseph Tribbia. Mathematical analysis of a cloud resolving model including the ice microphysics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 131-167. doi: 10.3934/dcds.2020219

[6]

A. M. Elaiw, N. H. AlShamrani, A. Abdel-Aty, H. Dutta. Stability analysis of a general HIV dynamics model with multi-stages of infected cells and two routes of infection. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020441

[7]

Qiang Fu, Yanlong Zhang, Yushu Zhu, Ting Li. Network centralities, demographic disparities, and voluntary participation. Mathematical Foundations of Computing, 2020, 3 (4) : 249-262. doi: 10.3934/mfc.2020011

[8]

Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320

[9]

Alberto Bressan, Wen Shen. A posteriori error estimates for self-similar solutions to the Euler equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 113-130. doi: 10.3934/dcds.2020168

[10]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443

[11]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[12]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

[13]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[14]

Qianqian Han, Xiao-Song Yang. Qualitative analysis of a generalized Nosé-Hoover oscillator. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020346

[15]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020446

[16]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[17]

Haixiang Yao, Ping Chen, Miao Zhang, Xun Li. Dynamic discrete-time portfolio selection for defined contribution pension funds with inflation risk. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020166

[18]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[19]

Justin Holmer, Chang Liu. Blow-up for the 1D nonlinear Schrödinger equation with point nonlinearity II: Supercritical blow-up profiles. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020264

[20]

Laurent Di Menza, Virginie Joanne-Fabre. An age group model for the study of a population of trees. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020464

2019 Impact Factor: 1.27

Metrics

  • PDF downloads (51)
  • HTML views (0)
  • Cited by (10)

[Back to Top]