  To capture the inherent geometric features of many community detection
problems, we propose to use a new random graph model of communities that we
call a Geometric Block Model. The geometric block model generalizes the random
geometric graphs in the same way that the well-studied stochastic block model
generalizes the Erdos-Renyi random graphs. It is also a natural extension of
random community models inspired by the recent theoretical and practical
advancement in community detection. While being a topic of fundamental
theoretical interest, our main contribution is to show that many practical
community structures are better explained by the geometric block model. We also
show that a simple triangle-counting algorithm to detect communities in the
geometric block model is near-optimal. Indeed, even in the regime where the
average degree of the graph grows only logarithmically with the number of
vertices (sparse-graph), we show that this algorithm performs extremely well,
both theoretically and practically. In contrast, the triangle-counting
algorithm is far from being optimum for the stochastic block model. We simulate
our results on both real and synthetic datasets to show superior performance of
both the new model as well as our algorithm.
