Size of the giant component in a random geometric graph

Ganesan, Ghurumuruhan

doi:10.1214/12-AIHP498

Ganesan, Ghurumuruhan

Annales de l'I.H.P. Probabilités et statistiques, Volume 49 (2013) no. 4, pp. 1130-1140.

Abstract
Résumé

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$ .

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$ .

MR Zbl

DOI: 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},
     pages = {1130--1140},
     publisher = {Gauthier-Villars},
     volume = {49},
     number = {4},
     year = {2013},
     doi = {10.1214/12-AIHP498},
     mrnumber = {3127916},
     zbl = {1283.60017},
     language = {en},
     url = {http://www.numdam.org/articles/10.1214/12-AIHP498/}
}

TY  - JOUR
AU  - Ganesan, Ghurumuruhan
TI  - Size of the giant component in a random geometric graph
JO  - Annales de l'I.H.P. Probabilités et statistiques
PY  - 2013
SP  - 1130
EP  - 1140
VL  - 49
IS  - 4
PB  - Gauthier-Villars
UR  - http://www.numdam.org/articles/10.1214/12-AIHP498/
DO  - 10.1214/12-AIHP498
LA  - en
ID  - AIHPB_2013__49_4_1130_0
ER  -

%0 Journal Article
%A Ganesan, Ghurumuruhan
%T Size of the giant component in a random geometric graph
%J Annales de l'I.H.P. Probabilités et statistiques
%D 2013
%P 1130-1140
%V 49
%N 4
%I Gauthier-Villars
%U http://www.numdam.org/articles/10.1214/12-AIHP498/
%R 10.1214/12-AIHP498
%G en
%F 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/articles/10.1214/12-AIHP498/

References
Cited by

[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

Cited by Sources: