Small Worlds and Rapid Mixing with a Little More Randomness on Random Geometric Graphs - Archive ouverte HAL Access content directly
Conference Papers Year : 2011

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

(1)
1
Gunes Ercal
  • Function : Author
  • PersonId : 1015769

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.
Fichier principal
Vignette du fichier
978-3-642-20757-0_22_Chapter.pdf (199.91 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01583418 , version 1 (07-09-2017)

Licence

Attribution - CC BY 4.0

Identifiers

Cite

Gunes Ercal. Small Worlds and Rapid Mixing with a Little More Randomness on Random Geometric Graphs. 10th IFIP Networking Conference (NETWORKING), May 2011, Valencia, Spain. pp.281-293, ⟨10.1007/978-3-642-20757-0_22⟩. ⟨hal-01583418⟩
29 View
57 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More