×

The structure of typical clusters in large sparse random configurations. (English) Zbl 1168.82028

Summary: The initial purpose of this work is to provide a probabilistic explanation of recent results on a version of Smoluchowski’s coagulation equations in which the number of aggregations is limited. The latter models the deterministic evolution of concentrations of particles in a medium where particles coalesce pairwise as time passes and each particle can only perform a given number of aggregations. Under appropriate assumptions, the concentrations of particles converge as time tends to infinity to some measure which bears a striking resemblance with the distribution of the total population of a Galton-Watson process started from two ancestors.
Roughly speaking, the configuration model is a stochastic construction which aims at producing a typical graph on a set of vertices with pre-described degrees. Specifically, one attaches to each vertex a certain number of stubs, and then join pairwise the stubs uniformly at random to create edges between vertices.
In this work, we use the configuration model as the stochastic counterpart of Smoluchowski’s coagulation equations with limited aggregations. We establish a hydrodynamical type limit theorem for the empirical measure of the shapes of clusters in the configuration model when the number of vertices tends to \(\infty \). The limit is given in terms of the distribution of a Galton-Watson process started with two ancestors.

MSC:

82D60 Statistical mechanics of polymers
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aldous, D.J.: Brownian excursions, critical random graphs and the multiplicative coalescence. Ann. Probab. 25, 812–854 (1997) · Zbl 0877.60010 · doi:10.1214/aop/1024404421
[2] Aldous, D.J.: Deterministic and stochastic models for coalescence (aggregation, coagulation): a review of the mean-field theory for probabilists. Bernoulli 5, 3–48 (1999) · Zbl 0930.60096 · doi:10.2307/3318611
[3] Bender, E., Canfield, E.: The asymptotic number of labelled graphs with given degree sequences. J. Comb. Theory, Ser. A 24, 296–307 (1978) · Zbl 0402.05042 · doi:10.1016/0097-3165(78)90059-6
[4] Bertoin, J.: Random Fragmentation and Coagulation Processes. Cambridge University Press, Cambridge (2006) · Zbl 1107.60002
[5] Bertoin, J.: Two solvable systems of coagulation equations with limited aggregations. Ann. Inst. Henri Poincaré, Anal. Non Linéaire (2009, to appear). doi: 10.1016/j.anihpc.2008.10.007
[6] Bertoin, J., Sidoravicius, V., Vares, M.E.: A system of grabbing particles related to Galton-Watson trees. 0804.0726 · Zbl 1209.60048
[7] Bollobás, B., Janson, S.: Riordan, O. The phase transition in inhomogeneous random graphs. Random Struct. Algorithms 31, 3–122 (2007) · Zbl 1123.05083 · doi:10.1002/rsa.20168
[8] Bollobás, B.: A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur. J. Comb. 1, 311–316 (1980) · Zbl 0457.05038
[9] Britton, T., Deijfen, M., Martin-Löf, A.: Generating simple random graphs with prescribed degree distribution. J. Stat. Phys. 124, 1377–1397 (2006) · Zbl 1106.05086 · doi:10.1007/s10955-006-9168-x
[10] Durrett, R.: Random Graph Dynamics. Cambridge University Press, Cambridge (2007) · Zbl 1116.05001
[11] Dwass, M.: The total progeny in a branching process. J. Appl. Probab. 6, 682–686 (1969) · Zbl 0192.54401 · doi:10.2307/3212112
[12] Haas, B., Pitman, J., Winkel, M.: Spinal partitions and invariance under re-rooting of continuum random trees. Ann. Probab. (2009, to appear). 0705.3602 · Zbl 1181.60128
[13] Janson, J., Luczak, M.J.: A new approach to the giant component problem. Random Struct. Algorithms 34, 197–216 (2009) · Zbl 1177.05110 · doi:10.1002/rsa.20231
[14] Molloy, M., Reed, B.: A critical point for random graphs with a given degree sequence. Random Struct. Algorithms 6, 161–179 (1995) · Zbl 0823.05050 · doi:10.1002/rsa.3240060204
[15] Molloy, M., Reed, B.: The size of the giant component of a random graphs with a given degree sequence. Comb. Probab. Comput. 7, 295–305 (1998) · Zbl 0916.05064 · doi:10.1017/S0963548398003526
[16] Newman, M.E.J.: The structure and function of complex networks. SIAM Rev. 45, 167–256 (2003) · Zbl 1029.68010 · doi:10.1137/S003614450342480
[17] Newman, M.E.J., Strogatz, S., Watts, D.: Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64, 026118 (2001) · doi:10.1103/PhysRevE.64.026118
[18] Norris, J.R.: Smoluchowski’s coagulation equation: uniqueness, non-uniqueness and hydrodynamic limit for the stochastic coalescent. Ann. Appl. Probab. 9, 78–109 (1999) · Zbl 0944.60082 · doi:10.1214/aoap/1029962598
[19] Pitman, J.: Combinatorial stochastic processes. In: École d’été de Probabilités de St-Flour. Lect. Notes in Maths, vol. 1875. Springer, Berlin (2006). http://stat-www.berkeley.edu/users/pitman/
[20] Riordan, O.: The k-core and branching processes. Comb. Probab. Comput. 17, 111–136 (2008) · Zbl 1136.05071 · doi:10.1017/S0963548307008589
[21] van den Esker, H., van der Hofstad, R., Hooghiemstra, G.: Universality for the distance in finite variance random graphs. J. Stat. Phys. 133, 169–202 (2008) · Zbl 1152.82008 · doi:10.1007/s10955-008-9594-z
[22] van der Hofstad, R., Hooghiemstra, G., van Mieghem, P.: Distances in random graphs with finite variance degrees. Random Struct. Algorithms 26, 76–123 (2005) · Zbl 1074.05083
[23] van der Hofstad, R., Hooghiemstra, G., Znamenski, D.: Distances in random graphs with finite mean and infinite variance degrees. Electron. J. Probab. 12, 703–766 (2007) · Zbl 1126.05090
[24] Wormald, N.C.: Some problems in the enumeration of labelled graphs. Doctoral thesis, Newcastle University (1978) · Zbl 0386.05034
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.