4 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
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • 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.