EUVIMEDEUVIMED entdecken
Crossref

Community detection on Euclidean random graphs

Emmanuel Abbe, François Baccelli, Abishek Sankararaman

Information and Inference: A Journal of the IMA · 16.03.2021 · 10 (1) · 109-160

DOI: 10.1093/imaiai/iaaa009 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Information and Inference: A Journal of the IMA, online erschienen am 25.05.2020. Verfasst von Emmanuel Abbe und 2 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 48 Literaturangaben. Gefördert von: National Science Foundation, Simons Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the problem of community detection on Euclidean random geometric graphs where each vertex has two latent variables: a binary community label and a $\mathbb{R}^d$ valued location label which forms the support of a Poisson point process of intensity $\lambda $. A random graph is then drawn with edge probabilities dependent on both the community and location labels. In contrast to the stochastic block model (SBM) that has no location labels, the resulting random graph contains many more short loops due to the geometric embedding. We consider the recovery of the community labels, partial and exact, using the random graph and the location labels. We establish phase transitions for both sparse and logarithmic degree regimes and provide bounds on the location of the thresholds, conjectured to be tight in the case of exact recovery. We also show that the threshold of the distinguishability problem, i.e., the testing between our model and the null model without community labels exhibits no phase transition and in particular, does not match the weak recovery threshold (in contrast to the SBM).

Förderung

  • National Science Foundation
  • Simons Foundation

Zitieren

APA

Abbe, E., Baccelli, F., & Sankararaman, A. (2021). Community detection on Euclidean random graphs. Information and Inference: A Journal of the IMA, 10(1), 109-160. https://doi.org/10.1093/imaiai/iaaa009

Vancouver

Abbe E, Baccelli F, Sankararaman A. Community detection on Euclidean random graphs. Information and Inference: A Journal of the IMA. 2021;10(1):109-160. doi:10.1093/imaiai/iaaa009

BibTeX
@article{Abbe2021,
  author = {Abbe, Emmanuel and Baccelli, François and Sankararaman, Abishek},
  title = {Community detection on Euclidean random graphs},
  journal = {Information and Inference: A Journal of the IMA},
  year = {2021},
  volume = {10},
  number = {1},
  pages = {109--160},
  doi = {10.1093/imaiai/iaaa009}
}
Kostenlos starten →