Galhotra, Sainyam ;
Mazumdar, Arya ;
Pal, Soumyabrata ;
Saha, Barna
Connectivity of Random Annulus Graphs and the Geometric Block Model
Abstract
Random geometric graph (Gilbert, 1961) is a basic model of random graphs for spatial networks proposed shortly after the introduction of the ErdösRé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ösRé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 realworld 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 vertexrandom graphs or random annulus graphs which are natural generalizations of random geometric graphs.
A vertexrandom graph is a model of random graphs where the randomness lies in the vertices as opposed to an ErdösRényi random graph where the randomness lies in the edges. A vertexrandom graph G(n, [r_1, r_2]), 0 <=r_1 <r_2 <=1 with n vertices is defined by assigning a real number in [0,1] randomly and uniformly to each vertices and adding an edge between two vertices if the "distance" between the corresponding two random numbers is between r_1 and r_2. For the special case of r_1=0, this corresponds to random geometric graph in one dimension. We can extend this model naturally to higher dimensions; these higher dimensional counterparts are referred to as random annulus graphs. Random annulus graphs appear naturally whenever the wellknown Goldilocks principle ("not too close, not too far') holds in a network. In this paper, we study the connectivity properties of such graphs, providing both necessary and sufficient conditions. We show a surprising long edge phenomena for vertexrandom graphs: the minimum gap for connectivity between r_1 and r_2 is significantly less when 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.
BibTeX  Entry
@InProceedings{galhotra_et_al:LIPIcs:2019:11268,
author = {Sainyam Galhotra and Arya Mazumdar and Soumyabrata Pal and Barna Saha},
title = {{Connectivity of Random Annulus Graphs and the Geometric Block Model}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {53:153:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11268},
URN = {urn:nbn:de:0030drops112682},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.53},
annote = {Keywords: random graphs, geometric graphs, community detection, block model}
}
17.09.2019
Keywords: 

random graphs, geometric graphs, community detection, block model 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Issue date: 

2019 
Date of publication: 

17.09.2019 