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