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

Metrics

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

[Back to Top]