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

Yoon-Sik Cho; Aram Galstyan; P. Jeffrey Brantingham; George Tita

doi:10.3934/dcdsb.2014.19.1335

Article Contents

2014, Volume 19, Issue 5: 1335-1354. Doi: 10.3934/dcdsb.2014.19.1335

This issue Previous Article Mean field games with nonlinear mobilities in pedestrian dynamics Next Article Rethinking centrality: The role of dynamical processes in social network analysis

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

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

Received: November 30, 2012

Revised: March 31, 2013

Published: June 2014

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Related Papers

Cited by

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.