×

A random graph of moderate density. (English) Zbl 1483.05152

Summary: We analyse a randomly growing graph model in which the average degree is asymptotically equal to a constant times the square root of the number of vertices, and the clustering coefficient is rather small. In every step, we choose two vertices uniformly at random, check whether they are connected or not, and we either add a new edge or delete one and add a new vertex of degree two to the graph. This dependence on the status of the connection chosen vertices makes the total number of vertices random after \(n\) steps. We prove asymptotic normality for this quantity and also for the degree of a fixed vertex (with normalization \(n^{1/6})\). We also analyse the proportion of vertices with degree greater than a fixed multiple of the average degree, and the maximal degree.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C42 Density (toughness, etc.)
05C07 Vertex degrees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Backhausz Á, Móri TF (2012), Degree distribution in the lower levels of the uniform recursive tree. Ann. Univ. Sci. Budapest Sect. Comput. 36: 53-62. · Zbl 1249.05355
[2] Backhausz Á, Szegedy B, Action convergence of operators and graphs. Canadian Journal of Mathematics (2020), 1-50. https://doi.org/10.4153/S0008414X2000070X · Zbl 1482.05187
[3] Barabási A-L, Albert R (1999), Emergence of scaling in random networks. Science 286(5439): 509-512. · Zbl 1226.05223
[4] Borgs C, Chayes JT, Cohn H, Zhao Y (2018), An \[{L^p}\] theory of sparse graph convergence II: LD convergence, quotients, and right convergence. Ann. Probab. 46(1): 337-396. · Zbl 1386.05099
[5] Deijfen M, Lindholm M (2009), Growing networks with preferential deletion and addition of edges. Physica A: Statistical Mechanics and its Applications, 388(19): 4297-4303. https://doi.org/10.1016/j.physa.2009.06.032
[6] Durrett R (2007), Random graph dynamics. Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge Univ. Press, Cambridge. · Zbl 1116.05001
[7] Fan X, Grama I, Liu Q (2012), Hoeffding’s inequality for supermartingales. Stochastic Process. Appl. 122(10): 3545-3559. · Zbl 1267.60045
[8] Flaxman AD, Frieze AM, Vera J (2007), Adversarial deletion in a scale-free random graph process. Combin. Probab. Comput. 16: 251-270. · Zbl 1123.05084
[9] Frenkel PE (2018), Convergence of graphs with intermediate density. Trans. Amer. Math. Soc. 370(5): 3363-3404. · Zbl 1380.05061
[10] Hall P, Heyde CC (1980) Martingale Limit Theory and Its Application. Academic Press: New York. · Zbl 0462.60045
[11] van der Hofstad R, Random graphs and complex networks (2017). Cambridge series in statistical and probabilistic mathematics, 43. · Zbl 1361.05002
[12] Lovász L (2012), Large networks and graph limits, American Mathematical Society Colloquium Publications, 60, American Mathematical Society, Providence, RI. · Zbl 1292.05001
[13] McDiarmid C (1998), Concentration. In: Habib M et al. (eds.) Probabilistic Methods for Algorithmic Discrete Mathematics, Springer Verlag: Berlin, Heidelberg, 195-248. · Zbl 0927.60027
[14] Móri TF (2005), The maximum degree of the Barabási-Albert random tree. Comb Probab Computing 14: 339-348. · Zbl 1078.05077
[15] Neveu J (1975), Discrete-Parameter Martingales, North-Holland: Amsterdam. · Zbl 0345.60026
[16] Pittel, B (1994), Note on the heights of random recursive trees and random \(m\)-ary search trees. Random Structures Algorithms 5(2): 337-347. · Zbl 0790.05077
[17] Thörnblad E (2015), Asymptotic degree distribution of a duplication-deletion random graph model. Internet Math. 11(3): 289-305. · Zbl 1465.05166
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.