摘要：Random geometric graph (Gilbert, 1961) is a basic model of random graphs for spatial networks proposed shortly after the introduction of the Erdös-Rényi random graphs. The geometric block model (GBM) is a probabilistic model for community detection defined over random geometric graphs (RGG) similar in spirit to the popular stochastic block model which is defined over Erdös-Rényi random graphs. The GBM naturally inherits many desirable properties of RGGs such as transitivity ("friends having common friends') and has been shown to model many real-world networks better than the stochastic block model. Analyzing the properties of a GBM requires new tools and perspectives to handle correlation in edge formation. In this paper, we study the necessary and sufficient conditions for community recovery over GBM in the connectivity regime. We provide efficient algorithms that recover the communities exactly with high probability and match the lower bound within a small constant factor. This requires us to prove new connectivity results for vertex-random graphs or random annulus graphs which are natural generalizations of random geometric graphs. A vertex-random graph is a model of random graphs where the randomness lies in the vertices as opposed to an Erdös-Rényi random graph where the randomness lies in the edges. A vertex-random graph G(n, [r_1, r_2]), 0 <=r_1 0 vs when r_1=0 (RGG). We then extend the connectivity results to high dimensions. These results play a crucial role in analyzing the GBM.
关键词：random graphs; geometric graphs; community detection; block model
