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

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

MR Zbl

DOI : 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},
     mrnumber = {3127916},
     zbl = {1283.60017},
     language = {en},
     url = {https://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  - https://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 https://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, Tome 49 (2013) no. 4, pp. 1130-1140. doi : 10.1214/12-AIHP498. https://www.numdam.org/articles/10.1214/12-AIHP498/

Bibliographie
Cité par

[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

Barthelemy, Marc Proximity Graphs, Spatial Networks (2022), p. 295 | DOI:10.1007/978-3-030-94106-2_15
Ganesan, Ghurumuruhan Stretch and Diameter in Random Geometric Graphs, Algorithmica, Volume 80 (2018) no. 1, p. 300 | DOI:10.1007/s00453-016-0253-5
Janssen, Jeannette; Mehrabian, Abbas Rumors Spread Slowly in a Small-World Spatial Network, SIAM Journal on Discrete Mathematics, Volume 31 (2017) no. 4, p. 2414 | DOI:10.1137/16m1083256
Ganesan, Ghurumuruhan Infection Spread in Random Geometric Graphs, Advances in Applied Probability, Volume 47 (2015) no. 1, p. 164 | DOI:10.1239/aap/1427814586
Janssen, Jeannette; Mehrabian, Abbas Rumours Spread Slowly in a Small World Spatial Network, Algorithms and Models for the Web Graph, Volume 9479 (2015), p. 107 | DOI:10.1007/978-3-319-26784-5_9
Fagnani, Fabio; Fosson, Sophie M.; Ravazzi, Chiara Some Introductory Notes on Random Graphs, Mathematical Foundations of Complex Networked Information Systems, Volume 2141 (2015), p. 1 | DOI:10.1007/978-3-319-16967-5_1
Liu, Junbiao; Jin, Xinyu; Jiang, Lurong; Xia, Yongxiang; Ouyang, Bo; Dong, Fang; Lang, Yicong; Zhang, Wenping Threshold for the Outbreak of Cascading Failures in Degree-Degree Uncorrelated Networks, Mathematical Problems in Engineering, Volume 2015 (2015), p. 1 | DOI:10.1155/2015/752893
Jiang, Lurong; Jin, Xinyu; Xia, Yongxiang; Ouyang, Bo; Wu, Duanpo; Chen, Xi A Scale-Free Topology Construction Model for Wireless Sensor Networks, International Journal of Distributed Sensor Networks, Volume 10 (2014) no. 8, p. 764698 | DOI:10.1155/2014/764698

Cité par 8 documents. Sources : Crossref