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

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.

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.

DOI : https://doi.org/10.1214/12-AIHP498
Classification : 60D05,  60C05
Mots clés : 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},
     pages = {1130--1140},
     publisher = {Gauthier-Villars},
     volume = {49},
     number = {4},
     year = {2013},
     doi = {10.1214/12-AIHP498},
     zbl = {1283.60017},
     mrnumber = {3127916},
     language = {en},
     url = {http://www.numdam.org/articles/10.1214/12-AIHP498/}
}
Ganesan, Ghurumuruhan. Size of the giant component in a random geometric graph. Annales de l'I.H.P. Probabilités et statistiques, Tome 49 (2013) no. 4, pp. 1130-1140. doi : 10.1214/12-AIHP498. http://www.numdam.org/articles/10.1214/12-AIHP498/

[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