Size of the giant component in a random geometric graph
Annales de l'I.H.P. Probabilités et statistiques, Volume 49 (2013) no. 4, p. 1130-1140

In this paper, we study the size of the giant component C G in the random geometric graph G=G(n,r n ,f) of n nodes independently distributed each according to a certain density f(·) in [0,1] 2 satisfying inf x[0,1] 2 f(x)> 0. If c 1 nr n 2 c 2 logn n for some positive constants c 1 , c 2 and nr n 2 as n, we show that the giant component of G contains at least n-o(n) nodes with probability at least 1-e -βnr n 2 for all n and for some positive constant β. We also obtain estimates on the diameter and number of the non-giant components of G.

Dans cet article nous étudions la composante principale C G dans le graphe géométrique aléatoire G=G(n,r n ,f) avec n nœuds indépendants, chacun étant distribué selon une densité f(·) dans [0,1] 2 telle que inf x[0,1] 2 f(x)> 0. Si c 1 nr n 2 c 2 logn n pour des constantes positives c 1 , c 2 et nr n 2 quand n, nous montrons que la composante principale de G contient au moins n-o(n) nœuds avec probabilité minorée par 1-e -βnr n 2 pour tout n et pour une constante positive β. Nous obtenons aussi des estimations sur les diamètres et sur le nombre des plus petites composantes de G.

DOI : https://doi.org/10.1214/12-AIHP498
Classification:  60D05,  60C05
Keywords: random geometric graphs, Size of giant component, number of components
@article{AIHPB_2013__49_4_1130_0,
     author = {Ganesan, Ghurumuruhan},
     title = {Size of the giant component in a random geometric graph},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     publisher = {Gauthier-Villars},
     volume = {49},
     number = {4},
     year = {2013},
     pages = {1130-1140},
     doi = {10.1214/12-AIHP498},
     zbl = {1283.60017},
     mrnumber = {3127916},
     language = {en},
     url = {http://www.numdam.org/item/AIHPB_2013__49_4_1130_0}
}
Ganesan, Ghurumuruhan. Size of the giant component in a random geometric graph. Annales de l'I.H.P. Probabilités et statistiques, Volume 49 (2013) no. 4, pp. 1130-1140. doi : 10.1214/12-AIHP498. http://www.numdam.org/item/AIHPB_2013__49_4_1130_0/

[1] B. Bollobas and O. Riordan. Percolation. Cambridge Univ. Press, New York, 2006. | MR 2283880

[2] M. Franceschetti, O. Dousse, D. N. C. Tse and P. Thiran. Closing gap in the capacity of wireless networks via percolation theory. IEEE Trans. Inform. Theory 53 (2007) 1009-1018. | MR 2302808

[3] G. Grimmett. Percolation, 2nd edition. Grundlehren der Mathematischen Wissenschaften 321. Springer, Berlin, 1999. | MR 1707339

[4] P. Gupta and P. R. Kumar. Critical power for asymptotic connectivity in wireless networks. In Stochastic Analysis, Control, Optimization and Applications 547-566. Systems Control Found. Appl. Birkhäuser, Boston, MA, 1999. | MR 1702981

[5] S. Muthukrishnan and G. Pandurangan. The bin-covering technique for thresholding random geometric graph properties. In Proc. SODA 989-998. ACM, New York, 2005. | MR 2298358

[6] M. Penrose. Random Geometric Graphs. Oxford Studies in Probability 5. Oxford Univ. Press, Oxford, 2003. | MR 1986198