Law of large numbers for the largest component in a hyperbolic model of complex networks. (English) Zbl 1387.05236

Fountoulakis, Nikolaos; Müller, Tobias

Ann. Appl. Probab. 28, No. 1, 607-650 (2018).

Summary: We consider the component structure of a recent model of random graphs on the hyperbolic plane that was introduced by D. Krioukov et al. [“Hyperbolic geometry of complex networks”, Phys. Rev. E (3) 82, No. 3, Article ID 036106, 18 p. (2010; doi:10.1103/PhysRevE.82.036106)]. The model exhibits a power law degree sequence, small distances and clustering, features that are associated with so-called complex networks. The model is controlled by two parameters \(\alpha\) and \(\nu\) where, roughly speaking, \(\alpha\) controls the exponent of the power law and \(\nu\) controls the average degree. Refining earlier results, we are able to show a law of large numbers for the largest component. That is, we show that the fraction of points in the largest component tends in probability to a constant \(c\) that depends only on \(\alpha,\nu\), while all other components are sublinear. We also study how \(c\) depends on \(\alpha,\nu\). To deduce our results, we introduce a local approximation of the random graph by a continuum percolation model on \(\mathbb{R}^{2}\) that may be of independent interest.

MSC:

05C80	Random graphs (graph-theoretic aspects)
05C82	Small world graphs, complex networks (graph-theoretic aspects)
60D05	Geometric probability and stochastic geometry
82B43	Percolation

Keywords:

random graphs; hyperbolic plane; giant component; law of large numbers

References:

[1]	Aizenman, M. and Newman, C. M. (1986). Discontinuity of the percolation density in one-dimensional \(1/\vert x-y\vert^2\) percolation models. Comm. Math. Phys.107 611-647. · Zbl 0613.60097 · doi:10.1007/BF01205489
[2]	Albert, R. and Barabási, A.-L. (2002). Statistical mechanics of complex networks. Rev. Modern Phys.74 47-97. · Zbl 1205.82086
[3]	Bode, M., Fountoulakis, N. and Müller, T. (2015). On the largest component of a hyperbolic model of complex networks. Electron. J. Combin.22 Paper 3.24, 46. · Zbl 1327.05301
[4]	Bode, M., Fountoulakis, N. and Müller, T. (2016). The probability of connectivity in a hyperbolic model of complex networks. Random Structures Algorithms 49 65-94. · Zbl 1344.05123
[5]	Bollobás, B. (2001). Random Graphs, 2nd ed. Cambridge Studies in Advanced Mathematics 73. Cambridge Univ. Press, Cambridge.
[6]	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
[7]	Bollobás, B. and Riordan, O. (2004). The diameter of a scale-free random graph. Combinatorica 24 5-34. · Zbl 1047.05038
[8]	Bollobás, B., Riordan, O., Spencer, J. and Tusnády, G. (2001). The degree sequence of a scale-free random graph process. Random Structures Algorithms 18 279-290. · Zbl 0985.05047
[9]	Candellero, E. and Fountoulakis, N. (2016). Clustering and the hyperbolic geometry of complex networks. Internet Math.12 2-53. · Zbl 1335.60180 · doi:10.1080/15427951.2015.1067848
[10]	Chung, F. and Lu, L. (2002). The average distances in random graphs with given expected degrees. Proc. Natl. Acad. Sci. USA 99 15879-15882. · Zbl 1064.05137
[11]	Chung, F. and Lu, L. (2002). Connected components in random graphs with given expected degree sequences. Ann. Comb.6 125-145. · Zbl 1009.05124
[12]	Chung, F. and Lu, L. (2006). Complex Graphs and Networks. CBMS Regional Conference Series in Mathematics 107. Amer. Math. Soc., Providence, RI. · Zbl 1114.90071
[13]	Dorogovtsev, S. N. (2010). Lectures on Complex Networks. Oxford Master Series in Physics 20. Oxford Univ. Press, Oxford. · Zbl 1200.94003
[14]	Erdős, P. and Rényi, A. (1959). On random graphs. I. Publ. Math. Debrecen 6 290-297. · Zbl 0092.15705
[15]	Fountoulakis, N. (2015). On a geometrization of the Chung-Lu model for complex networks. J. Complex Netw.3 361-387. · Zbl 1397.05173
[16]	Grimmett, G. (1999). Percolation, 2nd ed. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 321. Springer, Berlin. · Zbl 0926.60004
[17]	Gugelmann, L., Panagiotou, K. and Peter, U. (2012). Random hyperbolic graphs: Degree sequence and clustering. In Proceedings of the 39 th International Colloquium Conference on Automata, Languages, and Programming—Volume Part II, ICALP’12 573-585. Springer, Berlin. · Zbl 1369.68270
[18]	Janson, S., Łuczak, T. and Rucinski, A. (2000). Random Graphs. Wiley-Interscience, New York. · Zbl 0968.05003
[19]	Kingman, J. F. C. (1993). Poisson Processes. Oxford Studies in Probability 3. Oxford Univ. Press, New York. · Zbl 0771.60001
[20]	Kiwi, M. and Mitsche, D. (2015). A bound for the diameter of random hyperbolic graphs. In 2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) 26-39. SIAM, Philadelphia, PA. · Zbl 1391.60022
[21]	Krioukov, D., Kitsak, M., Sinkovits, R. S., Rideout, D., Meyer, D. and Boguñá, M. (2012). Network cosmology. Nature 2 793.
[22]	Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A. and Boguñá, M. (2010). Hyperbolic geometry of complex networks. Phys. Rev. E (3) 82 036106, 18.
[23]	Meester, R. and Roy, R. (1996). Continuum Percolation. Cambridge Tracts in Mathematics 119. Cambridge Univ. Press, Cambridge. · Zbl 0858.60092
[24]	Mood, A. M. (1974). Introduction to the Theory of Statistics. McGraw-Hill, New York. · Zbl 0277.62002
[25]	Penrose, M. (2003). Random Geometric Graphs. Oxford Studies in Probability 5. Oxford Univ. Press, Oxford. · Zbl 1029.60007
[26]	Stillwell, J. (1992). Geometry of Surfaces. Springer, New York. · Zbl 0752.53002
[27]	van den Berg, J.