Name
Abstract | ||
|---|---|---|
Random geometric graphs are the simplest, and perhaps the earliest possible random graph model of spatial networks, introduced by Gilbert in 1961. In the most basic setting, a random geometric graph $G(n,r)$ has $n$ vertices. Each vertex of the graph is assigned a real number in $[0,1]$ randomly and uniformly. There is an edge between two vertices if the corresponding two random numbers differ by at most $r$ (to mitigate the boundary effect, let us consider the Lee distance here, $d_L(u,v) = min{|u-v|, 1-|u-v|}$). It is well-known that the connectivity threshold regime for random geometric graphs is at $r approx frac{log n}{n}$. In particular, if $r = frac{alog n}{n}$, then a random geometric graph is connected with high probability if and only if $a u003e 1$. Consider $G(n,frac{(1+epsilon)log{n}}{n})$ for any $epsilon u003e0$ to satisfy the connectivity requirement and delete half of its edges which have distance at most $frac{log{n}}{2n}$. It is natural to believe that the resultant graph will be disconnected. Surprisingly, we show that the graph still remains connected! Formally, generalizing random geometric graphs, we define a random annulus graph $G(n, [r_1, r_2]), r_1 frac12$ and $a u003e1$. That is $G(n, [0,frac{0.99log n}{n}])$ is not connected but $G(n,[frac{0.50 log n}{n},frac{1+epsilon log n}{n}])$ is. This result is then used to give improved lower and upper bounds on the recovery threshold of the geometric block model. |
Year | Venue | Field |
|---|---|---|
2018 | APPROX-RANDOM | Discrete mathematics,Binary logarithm,Lee distance,Combinatorics,Random graph,Approx,Vertex (geometry),Generalization,Random geometric graph,Real number,Mathematics |
DocType | Volume | Citations |
Journal | abs/1804.05013 | 1 |
PageRank | References | Authors |
0.35 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sainyam Galhotra | 1 | 107 | 10.96 |
| Arya Mazumdar | 2 | 307 | 41.81 |
| Soumyabrata Pal | 3 | 2 | 3.76 |
| Barna Saha | 4 | 626 | 37.56 |