Small Worlds and Rapid Mixing with a Little More Randomness on Random Geometric Graphs

Abstract : We theoretically and experimentally analyze the process of adding sparse random links to a random wireless networks modeled as a random geometric graph. While this process has been previously proposed, we are the first to (i) theoretically consider sparse new-wiring (with asymptotically less than constant fraction of nodes allowed very small constant new wired edges), (ii) prove bounds for any new-wiring process upon random geometric graphs, and (iii) consider the effect of such sparse new-wiring upon the spectral gap of the resultant normalized Laplacian. In particular, we consider the following models of adding new wired edges: Divide the normalized space into bins of length $k\frac{r}{2\sqrt 2} \times k\frac{r}{2\sqrt 2}$, given that the radius is on the order required to guarantee asymptotic connectivity. For each bin, choose a bin-leader. Let the G1 new wiring be such that we form a random cubic graph amongst the bin-leaders and superimpose this upon the random geometric graph. Let the G2 new wiring be such that we form a random 1-out graph amongst the bin-leaders and superimpose this upon the random geometric graph. We prove that the diameter for G1 is O(k + log(n)) with high probability, and the diameter for G2 is O(k log(n)) with high probability, both of which exponentially improve the $\Theta(\sqrt \frac{n}{\log n})$ diameter of the random geometric graph, thus also inducing small-world characteristics as the high clustering remains unchanged. Further, we theoretically motivate and experimentally demonstrate that the spectral gap for both G1 and G2 are significantly greater than that of the original random geometric graph. These results further motivate future hybrid networks and advances in the use of directional antennas.
Type de document :
Communication dans un congrès
Jordi Domingo-Pascual; Pietro Manzoni; Sergio Palazzo; Ana Pont; Caterina Scoglio. 10th IFIP Networking Conference (NETWORKING), May 2011, Valencia, Spain. Springer, Lecture Notes in Computer Science, LNCS-6640 (Part I), pp.281-293, 2011, NETWORKING 2011. 〈10.1007/978-3-642-20757-0_22〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01583418
Contributeur : Hal Ifip <>
Soumis le : jeudi 7 septembre 2017 - 11:58:03
Dernière modification le : vendredi 9 mars 2018 - 13:54:02

Fichier

978-3-642-20757-0_22_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Gunes Ercal. Small Worlds and Rapid Mixing with a Little More Randomness on Random Geometric Graphs. Jordi Domingo-Pascual; Pietro Manzoni; Sergio Palazzo; Ana Pont; Caterina Scoglio. 10th IFIP Networking Conference (NETWORKING), May 2011, Valencia, Spain. Springer, Lecture Notes in Computer Science, LNCS-6640 (Part I), pp.281-293, 2011, NETWORKING 2011. 〈10.1007/978-3-642-20757-0_22〉. 〈hal-01583418〉

Partager

Métriques

Consultations de la notice

22

Téléchargements de fichiers

9