×

Critical random graphs and the differential equations technique. (English) Zbl 1384.05137

Summary: Over the last few years a wide array of random graph models have been postulated to understand properties of empirically observed networks. Most of these models come with a parameter \(t\) (usually related to edge density) and a (model dependent) critical time \(t_c\) that specifies when a giant component emerges. There is evidence to support that for a wide class of models, under moment conditions, the nature of this emergence is universal and looks like the classical Erdős-Rényi random graph, in the sense of the critical scaling window and (a) the sizes of the components in this window (all maximal component sizes scaling like \(n^{2/3}\)) and (b) the structure of components (rescaled by \(n^{-1/3}\)) converge to random fractals related to the continuum random tree. The aim of this note is to give a non-technical overview of recent breakthroughs in this area, emphasizing a particular tool in proving such results called the differential equations technique first developed and used extensively in probabilistic combinatorics in the work of N. C. Wormald [Ann. Appl. Probab. 5, No. 4, 1217–1235 (1995; Zbl 0847.05084); in: Lectures on approximation and randomized algorithms. Proceedings of the Berlin-Poznań summer school, Antonin, Poland, September 1997. Warsaw: Polish Scientific Publishers. 73–155 (1999; Zbl 0943.05073)] and developed in the context of critical random graphs by S. Bhamidi et al. [Probab. Theory Relat. Fields 160, No. 3–4, 733–796 (2014; Zbl 1318.60012); Random Struct. Algorithms 46, No. 1, 55–116 (2015; Zbl 1307.05200); “Scaling limits of random graph models at criticality: universality and the basin of attraction of the Erdős-Renyi random graph”, Preprint, arXiv:1411.3417].

MSC:

05C80 Random graphs (graph-theoretic aspects)
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Abraham, J.-F. Delmas and E Hoscheit, A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces, Electron. J. Probab., 18(14) (2013), 1-21. · Zbl 1285.60004
[2] D. Achlioptas, R. M. D’Souza and J. Spencer, Explosive percolation in random networks, Science, 323(5920) (2009), 1453. · Zbl 1226.05221 · doi:10.1126/science.1167782
[3] L. Addario-Berry, N. Broutin and C. Goldschmidt, The continuum limit of critical random graphs, Probability Theory and Related Fields, 152(3-4) (2012), 367-406. · Zbl 1239.05165 · doi:10.1007/s00440-010-0325-4
[4] L. Addario-Berry, N. Broutin, C. Goldschmidt and G. Miermont, The scaling limit of the minimum spanning tree of the complete graph, arXivpreprint arXiv:1301.1664 (2013). · Zbl 1407.60013
[5] Aldous, D., The continuum random tree, i, 1-28 (1991) · Zbl 0722.60013
[6] D. Aldous, The continuum random tree ii: An overview, Stochastic analysis, 167 (1991), 23-70. · Zbl 0791.60008 · doi:10.1017/CBO9780511662980.003
[7] Aldous, D., The continuum random tree iii, 248-289 (1993) · Zbl 0791.60009
[8] D. Aldous, Brownian excursions, critical random graphs and the multiplicative coalescent, Ann. Probab., 25(2) (1997), 812-854. MR1434128. · Zbl 0877.60010 · doi:10.1214/aop/1024404421
[9] E. A. Bender and E. R. Canfield, The asymptotic number of labeled graphs with given degree sequences, J. Combinatorial Theory Ser. A, 24(3) (1978), 296-307. MR0505796 (58 #21793). · Zbl 0402.05042 · doi:10.1016/0097-3165(78)90059-6
[10] S. Bhamidi, N. Broutin, S. Sen and X. Wang, Scaling limits of random graph models at criticality: Universality and the basin of attraction of the Erdos-Renyi random graph, (2014), arXiv preprint arXiv:1411.3417.
[11] S. Bhamidi, A. Budhiraja and X. Wang, The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs, Probability Theory and Related Fields, 160(3-4) (2014), 733-796. · Zbl 1318.60012 · doi:10.1007/s00440-013-0540-x
[12] S. Bhamidi, A. Budhiraja and X. Wang, Aggregation models with limited choice and the multiplicative coalescent, Random Structures and Algorithms, 46(1) (2015), 55-116. · Zbl 1307.05200 · doi:10.1002/rsa.20493
[13] S. Bhamidi, S. Sen and X. Wang, Continuum limit of critical inhomogeneous random graphs, arXiv preprint arXiv:1404.4118(2014).
[14] T. Bohman and A. Frieze, Avoiding a giant component, Random Structures and Algorithms, 19(1) (2001), 75-85. · Zbl 0986.05091 · doi:10.1002/rsa.1019
[15] B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European J. Combin., 1(4) (1980), 311-316. MR595929 (82i:05045). · Zbl 0457.05038 · doi:10.1016/S0195-6698(80)80030-8
[16] B. Bollobás, The evolution of random graphs, Transactions of the American Mathematical Society, 286(1) (1984), 257-274. · Zbl 0579.05046 · doi:10.2307/1999405
[17] B. Bollobás, Random graphs, Second, Cambridge studies in advanced mathematics, 73, Cambridge University Press, Cambridge, 2001. MR1864966. · Zbl 0979.05003 · doi:10.1017/CBO9780511814068
[18] B. Bollobás, S. Janson and O. Riordan, The phase transition in inhomogeneous random graphs, Random Structures Algorithms, 31(1) (2007), 3-122. MR2337396 (2008e:05124). · Zbl 1123.05083 · doi:10.1002/rsa.20168
[19] B. Bollobás and O. Riordan, Percolation, Cambridge University Press, 2006. · Zbl 1118.60001 · doi:10.1017/CBO9781139167383
[20] Bollobás, B.; Riordan, O., The phase transition in the Erdös-rényi random graph process, 59-110 (2013) · Zbl 1293.05351 · doi:10.1007/978-3-642-39286-3_3
[21] Burago, D.; Burago, Y.; Ivanov, S., A course in metric geometry (2001) · Zbl 0981.51016
[22] R. W. R. Darling and J. R. Norris, Differential equation approximations for Markov chains, Probab. Surveys, 5 (2008), 37-79. · Zbl 1189.60152 · doi:10.1214/07-PS121
[23] S. Dhara, R. van der Hofstad, J. S. van Leeuwaarden and S. Sen, Critical window for the configuration model: Finite third moment degrees, arXiv preprint arXiv:1605.02868 (2016). · Zbl 1387.60016
[24] R. Durrett, Random graph dynamics, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2010. MR2656427. · Zbl 1223.05002
[25] E. Erdös and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl., 5 (1960), 17-61. MR0125031. · Zbl 0103.16301
[26] S. N Ethier and T. G Kurtz, Markov processes: Characterization and convergence, 282, John Wiley and Sons, 2009. · Zbl 0592.60049
[27] S. N. Evans, Probability and real trees, lecture notes in mathematics, 1920, Springer, Berlin, 2008. Lectures from the 35th Summer School on Probability Theory held in Saint-Flour, July 6-23, 2005. MR2351587 (2009d:60014).
[28] S. N Evans, J. Pitman and A. Winter, Rayleigh processes, real trees, and root growth with re-grafting, Probability Theory and Related Fields, 134(1) (2006), 81-126. · Zbl 1086.60050 · doi:10.1007/s00440-004-0411-6
[29] N. Fountoulakis, Percolation on sparse random graphs with given degree sequence, Internet Mathematics, 4(4) (2007), 329-356. · Zbl 1206.68234 · doi:10.1080/15427951.2007.10129148
[30] Grimmett, G., Percolation and disordered systems, 153-300 (1997) · Zbl 0884.60089 · doi:10.1007/BFb0092620
[31] S. Janson, Brownian excursion area, Wright’s constants in graph enumeration, and other Brownian areas, Probab. Surv., 4 (2007), 80-145. MR2318402. · Zbl 1189.60147 · doi:10.1214/07-PS104
[32] S. Janson, On percolation in random graphs with given vertex degrees, Electron. J. Probab., 14(5) (2009), 87-118. MR2471661 (2010b:60023). · Zbl 1189.60179
[33] S. Janson, D. E Knuth, T. Łuczak and B. Pittel, The birth of the giant component, Random Structures and Algorithms, 4(3) (1993), 233-358. · Zbl 0795.05127 · doi:10.1002/rsa.3240040303
[34] S. Janson and M. J. Luczak, A new approach to the giant component problem, Random Structures and Algorithms, 34(2) (2009), 197-216. · Zbl 1177.05110 · doi:10.1002/rsa.20231
[35] S. Janson, T. Łuczak and A. Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR1782847. · Zbl 0968.05003 · doi:10.1002/9781118032718
[36] S. Janson and J. Spencer, Phase transitions for modified erdös-rényi processes, Arkiv för Matematik, 50(2) (2012), 305-329. · Zbl 1255.05175 · doi:10.1007/s11512-011-0157-1
[37] A. Joseph, The component sizes of a critical random graph with given degree sequence, The Annals of Applied Probability, 24(6) (2014), 2560-2594. · Zbl 1318.60015 · doi:10.1214/13-AAP985
[38] T. G. Kurtz, Strong approximation theorems for density dependent Markov chains, Stochastic Processes Appl., 6(3) (1977/78), 223-240. MR0464414 (574-344). · Zbl 0373.60085 · doi:10.1016/0304-4149(78)90020-0
[39] J.-F. Le Gall, Random trees and applications, Probab. Surv., 2 (2005), 245-311. MR2203728 (2007h:60078). · Zbl 1189.60161 · doi:10.1214/154957805100000140
[40] T. Łuczak, Component behavior near the critical point of the random graph process, Random Structures Algorithms, 1(3) (1990), 287-310. MR1099794. · Zbl 0745.05048 · doi:10.1002/rsa.3240010305
[41] M. Molloy and B. Reed, The size of the giant component of a random graph with a given degree sequence, Combin. Probab. Comput., 7(3) (1998), 295-305. MR1664335 (2000c:05130). · Zbl 0916.05064 · doi:10.1017/S0963548398003526
[42] A. Nachmias and Y. Peres, Critical percolation on random regular graphs, Random Structures and Algorithms, 36(2) (2010), 111-148. · Zbl 1209.05228 · doi:10.1002/rsa.20277
[43] O. Riordan, The phase transition in the configuration model, Combinatorics, Probability and Computing, 21(1-2) (2012), 265-299. · Zbl 1241.05134 · doi:10.1017/S0963548311000666
[44] O. Riordan and L. Warnke, Explosive percolation is continuous, Science, 333(6040) (2011), 322-324. · doi:10.1126/science.1206241
[45] O. Riordan and L. Warnke, Achlioptas process phase transitions are continuous, The Annals of Applied Probability, 22(4) (2012), 1450-1464. · Zbl 1255.05176 · doi:10.1214/11-AAP798
[46] O. Riordan and L. Warnke, The evolution of subcritical Achlioptas processes, Random Structures and Algorithms, 47(1) (2015), 174-203. · Zbl 1332.05130 · doi:10.1002/rsa.20530
[47] S. Sen, On the largest component in the subcritical regime of the Bohman-Frieze process, arXiv preprint arXiv:1307.2041 (2013). · Zbl 1346.60006
[48] J. Spencer, The giant component: The golden anniversary, Notices of the AMS, 57(6) (2010), 720-724. · Zbl 1195.01083
[49] J. Spencer and N. Wormald, Birth control for giants, Combinatorica, 27(5) (2007), 587-628. · Zbl 1164.05062 · doi:10.1007/s00493-007-2163-2
[50] J. M. Steele, Probability theory and combinatorial optimization, CBMS-NSF Regional Conference Series in Applied Mathematics, 69, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR1422018. · Zbl 0916.90233
[51] R. van der Hofstad, Random graphs and complex networks, Available on http://www.win.tue.nl/rhofstad/NotesRGCN.pdf (2009), 11.
[52] Wormald, N. C., Differential equations for random processes and random graphs, 1217-1235 (1995) · Zbl 0847.05084
[53] Wormald, N. C., The differential equation method for random graph processes and greedy algorithms, 73-155 (1999) · Zbl 0943.05073
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.