Abstract
We provide new connectivity results for vertex-random graphs or random annulus graphs which are significant generalizations of random geometric graphs. Random geometric graphs (RGG) are one of the most basic models of random graphs for spatial networks proposed by Gilbert in 1961, shortly after the introduction of the Erdős-Rényi random graphs. They resemble social networks in many ways (e.g. by spontaneously creating cluster of nodes with high modularity). The connectivity properties of RGG have been studied since its introduction, and analyzing them has been significantly harder than their Erdős-Rényi counterparts due to correlated edge formation. Our next contribution is in using the connectivity of random annulus graphs to provide necessary and sufficient conditions for efficient recovery of communities for the geometric block model (GBM). The GBM is a probabilistic model for community detection defined over an RGG in a similar spirit as the popular stochastic block model, which is defined over an Erdős-Rényi random graph. The geometric block model inherits the transitivity properties of RGGs and thus models communities better than a stochastic block model. However, analyzing them requires fresh perspectives as all prior tools fail due to correlation in edge formation. We provide a simple and efficient algorithm that can recover communities in GBM exactly with high probability in the regime of connectivity.
Introduction
Most classical random graph theory, such as the Erdős-Rényi model, assumes that edges form independently. However, real-world networks—social, biological, or wireless—are often embedded in physical space, where edge formation is highly correlated. If Alice is near Bob, and Bob is near Charlie, Alice is likely near Charlie.
The Random Geometric Graph (RGG) models this by placing nodes in space and connecting them if their distance is below a threshold $r$. This paper addresses two major gaps in this field:
- Generalizing the Geometry: Investigating Random Annulus Graphs (RAG), where edges only form at a specific range of distances. This models scenarios like wireless networks where interference prevents very close connections and signal decay prevents distant ones.
- Community Detection: Analyzing the Geometric Block Model (GBM), which incorporates spatial transitivity into community detection, a feature missing from the standard Stochastic Block Model (SBM).
Connectivity Thresholds in Random Annulus Graphs
The authors derive "zero-one laws" for graph connectivity in both 1D (on a circle) and high-dimensional spaces (on a $t$-dimensional unit sphere). A key finding is the Long Edge Phenomenon. In a 1D RGG, connectivity requires a threshold of $a > 1$. Surprisingly, in a RAG where short edges (below distance $b$) are removed, the graph remains connected as long as $a - b > 0.5$. This suggests that "long" edges are disproportionately effective at maintaining global connectivity by bridging distant parts of the graph in fewer hops.
In high dimensions, the authors use Vapnik-Chervonenkis (VC) dimension arguments to handle the uncountably infinite orientations of nodes, proving that "covers" and "poles"—nodes connected to all others in a specific region—exist with high probability.
Community Detection in the Geometric Block Model
The GBM inherits the transitivity of RGGs, making it a more realistic model for communities. However, the correlated edge structure makes analysis difficult. The authors propose a Triangle-Counting Algorithm based on the intuition that intra-community edges participate in significantly more triangles than inter-community edges.
By setting specific thresholds, the algorithm prunes "inter-cluster" edges while keeping "intra-cluster" components connected. The paper proves that exact recovery is impossible if $a - b < 0.5$ or $a < 1$. In the connectivity regime, their algorithm achieves exact recovery with high probability.
Conclusion and Future Work
This work provides the first necessary and sufficient conditions for exact community recovery in the GBM. While the 1D results are tight, a gap remains for high-dimensional annulus graphs. Future research could explore non-uniform node distributions and scenarios where model parameters $a$ and $b$ are unknown.
Summary updated