Estimating Community Boundaries in Geometric Random Graphs

Abstract

The unit square $I=[0,1{]}^2$ is divided into two rectangles by the vertical line $x=p$, where $p\in (0,1)$. Consider $N$ independent uniformly distributed points on $I$, which we interpret as a population of individuals, with the line $x=p$ representing a community boundary that separates the population into two communities. Whether a pair of individuals share a connection depends on their locations in $I$ and on whether they belong to the same community. Specifically, two individuals in the same community are connected if they are within distance $R_N$ of each other, while two individuals in different communities are connected if they are within distance $R_N^{\prime }$ of each other, giving rise to a geometric variant of the so-called \emph{stochastic block model}. A statistician observes the adjacency matrix of the resulting graph together with the geometric locations of the individuals and is tasked with estimating the boundary location $p$. Depending on how $R_N$ and $R_N^{\prime }$ scale as $N\to \infty$, we establish necessary and sufficient conditions for consistent estimation of $p$. Whenever consistent estimation is possible, we devise an estimator that converges to $p$ as $N\to \infty$ and provide explicit bounds on its estimation error.

19 pages, 2 figures; comments welcome