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

Part 6: Network ScienceInternational audienceWe 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