Article Contents
Article Contents

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

• 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.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

 Citation:

•  [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.