Markov random geometric graph, MRGG: a growth model for temporal dynamic networks. (English) Zbl 1487.05242

Summary: We introduce Markov Random Geometric Graphs (MRGGs), a growth model for temporal dynamic networks. It is based on a Markovian latent space dynamic: consecutive latent points are sampled on the Euclidean Sphere using an unknown Markov kernel; and two nodes are connected with a probability depending on a unknown function of their latent geodesic distance.
More precisely, at each stamp-time \(k\) we add a latent point \(X_k\) sampled by jumping from the previous one \(X_{k-1}\) in a direction chosen uniformly \(Y_k\) and with a length \(r_k\) drawn from an unknown distribution called the latitude function. The connection probabilities between each pair of nodes are equal to the envelope function of the distance between these two latent points. We provide theoretical guarantees for the non-parametric estimation of the latitude and the envelope functions.
We propose an efficient algorithm that achieves those non-parametric estimation tasks based on an ad-hoc Hierarchical Agglomerative Clustering approach. As a by product, we show how MRGGs can be used to detect dependence structure in growing graphs and to solve link prediction problems.


05C80 Random graphs (graph-theoretic aspects)
62G05 Nonparametric estimation
05C62 Graph representations (geometric and intersection representations, etc.)
60J05 Discrete-time Markov processes on general state spaces
Full Text: DOI arXiv Link


[1] Araya, E. and De Castro, Y. (2019). Latent Distance Estimation for Random Geometric Graphs. In Advances in Neural Information Processing Systems 8721-8731.
[2] Arlot, S. (2019). Minimal penalties and the slope heuristics: a survey. Journal de la société française de statistique 160 1-106. · Zbl 1437.62121
[3] Backstrom, L., Huttenlocher, D., Kleinberg, J. and Lan, X. (2006). Group formation in large social networks: membership, growth, and evolution. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining 44-54.
[4] Bandeira, A. S. and van Handel, R. (2016). Sharp nonasymptotic bounds on the norm of random matrices with independent entries. Ann. Probab. 44 2479-2506. · Zbl 1372.60004 · doi:10.1214/15-AOP1025
[5] Bhatia, R. (1996). Matrix Analysis. Graduate Texts in Mathematics. Springer New York. · Zbl 0863.15001
[6] Bubeck, S., Ding, J., Eldan, R. and Rácz, M. Z. (2016). Testing for high-dimensional geometry in random graphs. Random Structures & Algorithms 49 503-532. · Zbl 1349.05315 · doi:10.1002/rsa.20633
[7] De Castro, Y., Lacour, C. and Ngoc, T. M. P. (2020). Adaptive Estimation of Nonparametric Geometric Graphs. Mathematical Statistics and Learning.
[8] Clementi, A. E. F., Pasquale, F., Monti, A. and Silvestri, R. (2009). Information spreading in stationary Markovian evolving graphs. 2009 IEEE International Symposium on Parallel & Distributed Processing. · Zbl 1159.90327 · doi:10.1109/ipdps.2009.5160986
[9] Dai, F. and Xu, Y. (2013). Approximation theory and harmonic analysis on spheres and balls. Springer. · Zbl 1275.42001
[10] Duchemin, Q., de Castro, Y. and Lacour, C. (2020). Concentration inequality for U-statistics of order two for uniformly ergodic Markov chains.
[11] Durante, D. and Dunson, D. (2014). Bayesian logistic gaussian process models for dynamic networks. In Artificial Intelligence and Statistics 194-201. PMLR.
[12] Díaz, J., Mitsche, D. and Pérez-Giménez, X. (2008). On the connectivity of dynamic random geometric graphs. · Zbl 1192.05100
[13] Fan, J., Jiang, B. and Sun, Q. (2018). Hoeffding’s lemma for Markov Chains and its applications to statistical learning.
[14] Ferré, D., Hervé, L. and Ledoux, J. (2012). Limit theorems for stationary Markov processes with L2-spectral gap. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques 48 396-423. · Zbl 1245.60068 · doi:10.1214/11-aihp413
[15] Gilles, P. (1989). The volume of convex bodies and Banach space geometry. Cambridge University Press. · Zbl 0698.46008
[16] Higham, D. J., Rašajski, M. and Pržulj, N. (2008). Fitting a geometric graph to a protein-protein interaction network. Bioinformatics 24 1093-1099. · doi:10.1093/bioinformatics/btn079
[17] Hoff, P. D., Raftery, A. E. and Handcock, M. S. (2002). Latent Space Approaches to Social Network Analysis. Journal of the American Statistical Association 97 1090-1098. · Zbl 1041.62098 · doi:10.1198/016214502388618906
[18] Jiang, B., Sun, Q. and Fan, J. (2018). Bernstein’s inequality for general Markov Chains.
[19] Jin, E. M., Girvan, M. and Newman, M. E. (2001). Structure of growing social networks. Physical review E 64 046132.
[20] Klopp, O., Tsybakov, A. B. and Verzelen, N. (2017). Oracle inequalities for network models and sparse graphon estimation. The Annals of Statistics 45 316-354. · Zbl 1367.62090 · doi:10.1214/16-aos1454
[21] Koltchinskii, V. and Giné, E. (2000). Random Matrix Approximation of Spectra of Integral Operators. Bernoulli 6. · Zbl 0949.60078 · doi:10.2307/3318636
[22] Lo, C., Cheng, J. and Leskovec, J. (2017). Understanding Online Collection Growth Over Time: A Case Study of Pinterest. In Proceedings of the 26th International Conference on World Wide Web Companion. WWW ’17 Companion 545-554. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE. · doi:10.1145/3041021.3054189
[23] Lovász, L. (2012). Large Networks and Graph Limits. American Mathematical Society. · Zbl 1292.05001
[24] Matias, C. and Miele, V. (2017). Statistical clustering of temporal networks through a dynamic Stochastic Block Model. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 79 1119-1141. · Zbl 1373.62312
[25] Meyn, S. and Tweedie, R. (1993). Markov Chains and Stochastic Stability 92. · Zbl 0925.60001 · doi:10.2307/2965732
[26] Penrose, M. (2003). Random Geometric Graphs. · Zbl 1029.60007 · doi:10.1093/acprof:oso/9780198506263.001.0001
[27] Roberts, G. O. and Rosenthal, J. S. (2004). General state space Markov chains and MCMC algorithms. Probability Surveys 1 20-71. · Zbl 1189.60131
[28] Rossetti, G. and Cazabet, R. (2018). Community discovery in dynamic networks: a survey. ACM Computing Surveys (CSUR) 51 1-37.
[29] Staples, R. S. G. S. (2009). Dynamic Geometric Graph Processes: Adjacency Operator Approach.
[30] Tang, M., Sussman, D. L. and Priebe, C. E. (2013). Universally consistent vertex classification for latent positions graphs. The Annals of Statistics 41 1406-1430. · Zbl 1273.62147 · doi:10.1214/13-aos1112
[31] Ugander, J., Backstrom, L., Marlow, C. and Kleinberg, J. (2012). Structural diversity in social contagion. Proceedings of the National Academy of Sciences 109 5962-5966.
[32] Xu, K. S. and Hero, A. O. (2014). Dynamic Stochastic Blockmodels for Time-Evolving Social Networks. IEEE Journal of Selected Topics in Signal Processing 8 552-562. · doi:10.1109/JSTSP.2014.2310294
[33] Yang, S. and Koeppl, H. (2018). Dependent Relational Gamma Process Models for Longitudinal Networks. In Proceedings of the 35th International Conference on Machine Learning (J. Dy and A. Krause, eds.). Proceedings of Machine Learning Research 80 5551-5560. PMLR.
[34] Yu, Y., Wang, T. and Samworth, R. J. (2014). A useful variant of the Davis-Kahan theorem for statisticians. Biometrika 102 315-323. · Zbl 1452.15010 · doi:10.1093/biomet/asv008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.