Strong couplings for static locally tree-like random graphs. (English) Zbl 1503.05110
Summary: We provide a general purpose result for the coupling of exploration processes of random graphs, both undirected and directed, with their local weak limits when this limit is a marked Galton-Watson process. This class includes in particular the configuration model and the family of inhomogeneous random graphs with rank-1 kernel. Vertices in the graph are allowed to have attributes on a general separable metric space and can potentially influence the construction of the graph itself. The coupling holds for any fixed depth of a breadth-first exploration process.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 60J80 | Branching processes (Galton-Watson, birth-and-death, etc.) |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
Keywords:
random graphs; complex networks; Galton-Watson processes; configuration model; inhomogeneous random graph; local-weak limitsReferences:
| [1] | Aldous, D. and Lyons, R. (2007). Processes on unimodular random networks. Electron. J. Prob.12, 1454-1508. · Zbl 1131.60003 |
| [2] | Aldous, D. and Steele, J. M. (2004). The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures, ed. H. Kesten. Springer, New York, pp. 1-72. · Zbl 1037.60008 |
| [3] | Benjamini, I. and Schramm, O. (2011). Recurrence of distributional limits of finite planar graphs. In Selected Works of Oded Schramm, eds I. Benjamini and O.Häggström. Springer, New York, pp. 533-545. |
| [4] | Bollobás, B. (1980). A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Europ. J. Combinatorics1, 311-316. · Zbl 0457.05038 |
| [5] | Bollobás, B. (2001). Random Graphs. Cambridge University Press. · Zbl 0979.05003 |
| [6] | Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms31, 3-122. · Zbl 1123.05083 |
| [7] | Britton, T., Deijfen, M. and Martin-Läf, A. (2006). Generating simple random graphs with prescribed degree distribution. J. Statist. Phys.124, 1377-1397. · Zbl 1106.05086 |
| [8] | Chaintron, L.-P. and Diez, A. (2021). Propagation of chaos: A review of models, methods and applications. Preprint, arXiv:2106.14812. |
| [9] | Chen, N., Livtak, N. and Olvera-Cravioto, M. (2017). Generalized PageRank on directed configuration networks. Random Structures Algorithms51, 237-274. · Zbl 1370.05199 |
| [10] | Chen, N. and Olvera-Cravioto, M. (2013). Directed random graphs with given degree distributions. Stoch. Syst.3, 147-186. · Zbl 1297.05212 |
| [11] | Chung, F. and Lu, L. (2002). Connected components in random graphs with given expected degree sequences. Ann. Combinatorics6, 125-145. · Zbl 1009.05124 |
| [12] | Durrett, R. (2007). Random Graph Dynamics. Cambridge University Press. · Zbl 1116.05001 |
| [13] | Erdős, P. E. and Rényi, A. (1959). On random graphs. Publicationes Mathematicae (Debrecen)6, 290-297. · Zbl 0092.15705 |
| [14] | Fraiman, N., Lin, T. and Olvera-Cravioto, M. (2021). Stochastic recursions on directed random graphs. Preprint, arXiv:2010.09596. |
| [15] | Garavaglia, A., Van Der Hofstad, R. and Litvak, N. (2020). Local weak convergence for PageRank. Ann. Appl. Prob.30, 40-79. · Zbl 1434.60027 |
| [16] | Lacker, D., Ramanan, K. and Wu, R. (2020). Local weak convergence and propagation of ergodicity for sparse networks of interacting processes. Preprint, arXiv:1904.02585. |
| [17] | Lacker, D., Ramanan, K. and Wu, R. (2020). Marginal dynamics of interacting diffusions on unimodular galton-watson trees. Preprint, arXiv:2009.11667. |
| [18] | Lee, J. and Olvera-Cravioto, M. (2020). PageRank on inhomogeneous random digraphs. Stoch. Process. Appl.130, 1-57. |
| [19] | Norros, I. and Reittu, H. (2006). On a conditionally Poissonian graph process. Adv. Appl. Prob.38, 59-75. · Zbl 1096.05047 |
| [20] | Olvera-Cravioto, M. (2021). PageRank’s behavior under degree correlations. Ann. Appl. Prob.1, 1403-1442. · Zbl 1477.05173 |
| [21] | Van Der Hofstad, R. (2017). Random Graphs and Complex Networks, Vol. 1. Cambridge University Press. · Zbl 1361.05002 |
| [22] | Van Der Hofstad, R. (2021). Random Graphs and Complex Networks, Vol. 2. Cambridge University Press. |
| [23] | Van Der Hofstad, R., Hooghiemstra, G. and Van Mieghem, P. (2005). Distances in random graphs with finite variance degrees. Random Structures Algorithms27, 76-123. · Zbl 1074.05083 |
| [24] | Villani, C. (2009). Optimal Transport, Old and New. Springer, New York. · Zbl 1156.53003 |
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.
