To capture inherent geometric features of many community detection problems,
we propose to use a new random graph model of communities that we call a
\emph{Geometric Block Model}. The geometric block model builds on the
\emph{random geometric graphs} (Gilbert, 1961), one of the basic models of
random graphs for spatial networks, in the same way that the well-studied
stochastic block model builds on the Erd\H{o}s-R\'{en}yi random graphs. It is
also a natural extension of random community models inspired by the recent
theoretical and practical advancements in community detection. To analyze the
geometric block model, we first provide new connectivity results for
\emph{random annulus graphs} which are generalizations of random geometric
graphs. The connectivity properties of geometric graphs have been studied since
their introduction, and analyzing them has been difficult due to correlated
edge formation.
We then use the connectivity results of random annulus graphs to provide
necessary and sufficient conditions for efficient recovery of communities for
the geometric block model. We show that a simple triangle-counting algorithm to
detect communities in the geometric block model is near-optimal. For this we
consider two regimes of graph density.
In the regime where the average degree of the graph grows logarithmically
with number of vertices, we show that our algorithm performs extremely well,
both theoretically and practically. In contrast, the triangle-counting
algorithm is far from being optimum for the stochastic block model in the
logarithmic degree regime. We also look at the regime where the average degree
of the graph grows linearly with the number of vertices $n$, and hence to store
the graph one needs $\Theta(n^2)$ memory. We show that our algorithm needs to
store only $O(n \log n)$ edges in this regime to recover the latent
communities.

使用新的随机图模型 —— 几何块模型，基于随机几何图，拓展了社区检测模型，提供了新的连通性结果和效率条件，引入简单的三角形计数算法检测成功恢复潜在社区。

几何块模型中的社区恢复

Community Recovery in the Geometric Block Model

The geometric block model is a recently proposed generative model for random
graphs that is able to capture the inherent geometric properties of many
community detection problems, providing more accurate characterizations of
practical community structures compared with the popular stochastic block
model. Galhotra et al. recently proposed a motif-counting algorithm for
unsupervised community detection in the geometric block model that is proved to
be near-optimal. They also characterized the regimes of the model parameters
for which the proposed algorithm can achieve exact recovery. In this work, we
initiate the study of active learning in the geometric block model. That is, we
are interested in the problem of exactly recovering the community structure of
random graphs following the geometric block model under arbitrary model
parameters, by possibly querying the labels of a limited number of chosen
nodes. We propose two active learning algorithms that combine the idea of
motif-counting with two different label query policies. Our main contribution
is to show that sampling the labels of a vanishingly small fraction of nodes
(sub-linear in the total number of nodes) is sufficient to achieve exact
recovery in the regimes under which the state-of-the-art unsupervised method
fails. We validate the superior performance of our algorithms via numerical
simulations on both real and synthetic datasets.

本文研究了几何块模型中的主动学习问题，提出了两个结合不同标签查询策略的主动学习算法。我们的主要贡献在于展示了在一些场景下，取极少量的节点标签进行样本探索就能精确恢复社区结构，并在真实和合成数据集上验证了我们算法的卓越性能。

几何块模型中的主动学习

Active learning in the geometric block model

We provide new connectivity results for {\em vertex-random graphs} or {\em
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\H{o}s-R\'{en}yi 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\H{o}s-R\'{en}yi 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 {\em 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 {\em stochastic block model}, which is defined over an
Erd\H{o}s-R\'{en}yi 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.

本研究提出了一种简单高效的算法，通过连接随机环图和探究其连接性来确定几何块模型的社群检测问题，解决了相关性问题以及使用了更好的社区划分模型。

随机圆环图中的连通性和几何块模型

Connectivity in Random Annulus Graphs and the Geometric Block Model

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.

提出一种称为几何块模型（Geometric Block Model）的新随机图模型来捕捉许多社区检测问题的内在几何特征，并证明在这个模型中使用简单的三角计数算法是近乎最优的。