×

Large deviation principles for empirical measures of colored random graphs. (English) Zbl 1213.60054

A random graph on n vertices has vertex colors chosen independently according to a common color distribution on a finite color set. Conditional on the vertex colors, edges are independently attached to the unordered vertex pairs with connection probability depending on n and the connected vertex colors. Empirical counting measures are considered for the number of vertices of each color, the number of edges between each pair of colors, and the number of vertices of each color with specified numbers of neighbors of each color. Large deviation principles are given for these measures, and their rate functions are expressed in terms of relative entropies. As a special case, a large deviation principle is stated for the degree distribution of a Bernoulli graph with expected degree converging to a constant.

MSC:

60F10 Large deviations
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Biggins, J. D. (2004). Large deviations for mixtures. Electron. Comm. Probab. 9 60-71 (electronic). · Zbl 1060.60026
[2] Biggins, J. D. and Penman, D. B. (2009). Large deviations in randomly coloured random graphs. Electron. Comm. Probab. 14 290-301. · Zbl 1185.05125
[3] Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31 3-122. · Zbl 1123.05083 · doi:10.1002/rsa.20168
[4] Boucheron, S., Gamboa, F. and Léonard, C. (2002). Bins and balls: Large deviations of the empirical occupancy process. Ann. Appl. Probab. 12 607-636. · Zbl 1013.60017 · doi:10.1214/aoap/1026915618
[5] Cannings, C. and Penman, D. B. (2003). Models of random graphs and their applications. In Stochastic Processes : Modelling and Simulation. Handbook of Statist. 21 51-91. North-Holland, Amsterdam. · Zbl 1025.05055
[6] Dembo, A., Mörters, P. and Sheffield, S. (2005). Large deviations of Markov chains indexed by random trees. Ann. Inst. H. Poincaré Probab. Statist. 41 971-996. · Zbl 1078.60020 · doi:10.1016/j.anihpb.2004.09.005
[7] Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications , 2nd ed. Applications of Mathematics ( New York ) 38 . Springer, New York. · Zbl 0896.60013
[8] den Hollander, F. (2000). Large Deviations. Fields Institute Monographs 14 . Amer. Math. Soc., Providence, RI. · Zbl 0949.60001
[9] Doku-Amponsah, K. (2006). Large deviations and basic information theory for hierarchical and networked data structures. Ph.D. thesis, Univ. Bath. · Zbl 1318.60086
[10] Eichelsbacher, P. and Schmock, U. (2002). Large deviations of U -empirical measures in strong topologies and applications. Ann. Inst. H. Poincaré Probab. Statist. 38 779-797. · Zbl 1033.60033 · doi:10.1016/S0246-0203(02)01116-0
[11] Feller, V. (1967). An Introduction to Probability Theory and Its Applications , Vol. 1, 3rd ed. Wiley, New York. · Zbl 0158.34902
[12] O’Connell, N. (1998). Some large deviation results for sparse random graphs. Probab. Theory Related Fields 110 277-285. · Zbl 0927.60041 · doi:10.1007/s004400050149
[13] Penman, D. B. (1998). Random graphs with correlation structure. Ph.D. thesis, Univ. Sheffield.
[14] Söderberg, B. (2002). General formalism for inhomogeneous random graphs. Phys. Rev. E (3) 66 066121, 6.
[15] van der Hofstad, R. (2009). Critical behavior in inhomogeneous random graphs. Preprint. Available at . · Zbl 1269.05101
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.