3 years ago

Community Detection on Euclidean Random Graphs.

Abishek Sankararaman, Francois Baccelli

Motivated by applications in online social networks, we introduce and study the problem of Community Detection on a new class of sparse \emph{spatial} random graphs embedded in the Euclidean space. Our random graph is the planted-partition version of the classical random connection model studied in Stochastic Geometry. Roughly speaking, each node of our graph has an uniform i.i.d. $\{-1,+1\}$ valued community label and a $\mathbb{R}^d$ valued location label given by the support of a homogeneous Poisson point process of intensity $\lambda$. Conditional on the labels, edges are drawn independently at random depending both on the Euclidean distance between the nodes and the community labels on the nodes. We study the Community Detection problem on this random graph which consists in estimating the partition of nodes into communities, based on an observation of the random graph along with the spatial location labels on nodes.

We show that for $d=1$, Community Detection is impossible for any parameters. For $d \geq 2$, we establish a phase-transition based on the intensity $\lambda$ of the point process. In particular, we show that if the intensity $\lambda$ is small, then no algorithm for community detection can beat a random guess for the partitions. We prove this by introducing and analyzing a new problem which we call `Information Flow from Infinity'. On the positive side, we give a novel algorithm that performs Community Detection as long as the intensity $\lambda$ is larger than a sufficiently high constant. Along the way, we establish a \emph{distinguishability} result which says that one can always efficiently infer the existence of a partition given the graph and the spatial locations even when one cannot identify the partition better than at random. This is a surprising new phenomenon not observed thus far in any non-spatial Erd\H{o}s-R\'enyi based planted-partition models.

Publisher URL: http://arxiv.org/abs/1706.09942

DOI: arXiv:1706.09942v3

You might also like
Never Miss Important Research

Researcher is an app designed by academics, for academics. Create a personalised feed in two minutes.
Choose from over 15,000 academics journals covering ten research areas then let Researcher deliver you papers tailored to your interests each day.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.