Size of the giant component in a random geometric graph

Ganesan, Ghurumuruhan

Annales de l'I.H.P. Probabilités et statistiques, Tome 49 (2013), p. 1130-1140 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé
Abstract

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 (\cdot)$ dans ${[0, 1]}^{2}$ telle que ${inf}_{x \in {[0, 1]}^{2}} f (x) >$ $0$ . Si $\frac{c_{1}}{n} \leq r_{n}^{2} \leq c_{2} \frac{log n}{n}$ pour des constantes positives $c_{1}$ , $c_{2}$ et $n r_{n}^{2} ⟶ \infty$ quand $n \to \infty$ , nous montrons que la composante principale de $G$ contient au moins $n - o (n)$ nœuds avec probabilité minorée par $1 - e^{- β n r_{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 (\cdot)$ in ${[0, 1]}^{2}$ satisfying ${inf}_{x \in {[0, 1]}^{2}} f (x) >$ $0$ . If $\frac{c_{1}}{n} \leq r_{n}^{2} \leq c_{2} \frac{log n}{n}$ for some positive constants $c_{1}$ , $c_{2}$ and $n r_{n}^{2} ⟶ \infty$ as $n \to \infty$ , we show that the giant component of $G$ contains at least $n - o (n)$ nodes with probability at least $1 - e^{- β n r_{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$ .

Publié le : 2013-01-01

MR 3127916 | Zbl 1283.60017

DOI : https://doi.org/10.1214/12-AIHP498
Classification: 60D05, 60C05

@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},
     volume = {49},
     year = {2013},
     pages = {1130-1140},
     doi = {10.1214/12-AIHP498},
     mrnumber = {3127916},
     zbl = {1283.60017},
     language = {en},
     url = {http://dml.mathdoc.fr/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, Tome 49 (2013) pp. 1130-1140. doi : 10.1214/12-AIHP498. http://gdmltest.u-ga.fr/item/AIHPB_2013__49_4_1130_0/

Bibliographie

[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