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) no. 4, pp. 1130-1140.

Abstract (VO)

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\in {[0,1]}^2}f\left(x\right)>$ $0$. If $\frac{c_1}{n}\le r_n^2\le c_2\frac{logn}{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-\mathrm{o}\left(n\right)$ nodes with probability at least $1-{\mathrm{e}}^{-\beta n{r}_n^2}$ for all $n$ and for some positive constant $\beta$. We also obtain estimates on the diameter and number of the non-giant components of $G$.

Résumé

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\in {[0,1]}^2}f\left(x\right)>$ $0$. Si $\frac{c_1}{n}\le r_n^2\le c_2\frac{logn}{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-\mathrm{o}\left(n\right)$ nœuds avec probabilité minorée par $1-{\mathrm{e}}^{-\beta n{r}_n^2}$ pour tout $n$ et pour une constante positive $\beta$. Nous obtenons aussi des estimations sur les diamètres et sur le nombre des plus petites composantes de $G$.

Détail

DOI : 10.1214/12-AIHP498

Classification : 60D05, 60C05
Keywords: random geometric graphs, Size of giant component, number of components

Bibliographie

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

[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

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

[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

[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

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