We make the first steps towards generalizing the theory of stochastic block
models, in the sparse regime, towards a model where the discrete community
structure is replaced by an underlying geometry. We consider a geometric random
graph over a homogeneous metric space where the probability of two vertices to
be connected is an arbitrary function of the distance. We give sufficient
conditions under which the locations can be recovered (up to an isomorphism of
the space) in the sparse regime. Moreover, we define a geometric counterpart of
the model of flow of information on trees, due to Mossel and Peres, in which
one considers a branching random walk on a sphere and the goal is to recover
the location of the root based on the locations of leaves. We give some
sufficient conditions for percolation and for non-percolation of information in
this model.

本研究提出了一种新模型 —— 基于度量空间的几何随机图，用于替代传统的离散社区结构模型，并讨论了在稀疏情况下对该模型的位置恢复问题，同时对一种树的信息流模型进行了改进和定理研究。

几何设置下的社区检测与信息渗透

Community detection and percolation of information in a geometric  setting

We propose and analyze the problems of \textit{community goodness-of-fit and
two-sample testing} for stochastic block models (SBM), where changes arise due
to modification in community memberships of nodes. Motivated by practical
applications, we consider the challenging sparse regime, where expected node
degrees are constant, and the inter-community mean degree ($b$) scales
proportionally to intra-community mean degree ($a$). Prior work has sharply
characterized partial or full community recovery in terms of a "signal-to-noise
ratio" ($\mathrm{SNR}$) based on $a$ and $b$. For both problems, we propose
computationally-efficient tests that can succeed far beyond the regime where
recovery of community membership is even possible. Overall, for large changes,
$s \gg \sqrt{n}$, we need only $\mathrm{SNR}= O(1)$ whereas a na\"ive test
based on community recovery with $O(s)$ errors requires $\mathrm{SNR}=
\Theta(\log n)$. Conversely, in the small change regime, $s \ll \sqrt{n}$, via
an information-theoretic lower bound, we show that, surprisingly, no algorithm
can do better than the na\"ive algorithm that first estimates the community up
to $O(s)$ errors and then detects changes. We validate these phenomena
numerically on SBMs and on real-world datasets as well as Markov Random Fields
where we only observe node data rather than the existence of links.

针对随机块模型 (SBM) 中的社区适配性和两样本检验问题以及稀疏模式、信息理论下限等问题，我们提出了计算效率高、能够成功解决这些问题的测试方法。

随机块模型中社群变化的测试

Testing Changes in Communities for the Stochastic Block Model

We study random graphs with possibly different edge probabilities in the
challenging sparse regime of bounded expected degrees. Unlike in the dense
case, neither the graph adjacency matrix nor its Laplacian concentrate around
their expectations due to the highly irregular distribution of node degrees. It
has been empirically observed that simply adding a constant of order $1/n$ to
each entry of the adjacency matrix substantially improves the behavior of
Laplacian. Here we prove that this regularization indeed forces Laplacian to
concentrate even in sparse graphs. As an immediate consequence in network
analysis, we establish the validity of one of the simplest and fastest
approaches to community detection -- regularized spectral clustering, under the
stochastic block model. Our proof of concentration of regularized Laplacian is
based on Grothendieck's inequality and factorization, combined with paving
arguments.

本文研究了具有可能不同边缘概率的随机图，位于期望度数有限的稀疏区域。通过在邻接矩阵的每个条目中添加数量级为 1/n 的常数，达到正则化的效果，证明了其集中作用，从而证实了在随机块模型下基于正则化谱聚类的一种最简单和最快速的社区检测方法的有效性。