Detecting a planted community in an inhomogeneous random graph

Kay Bogerd, Rui M. Castro, Remco van der Hofstad, Nicolas Verzelen

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)

Abstract

We study the problem of detecting whether an inhomogeneous random graph contains a planted community. Specifically, we observe a single realization of a graph. Under the null hypothesis, this graph is a sample from an inhomogeneous random graph, whereas under the alternative, there exists a small subgraph where the edge probabilities are increased by a multiplicative scaling factor. We present a scan test that is able to detect the presence of such a planted community, even when this community is very small and the underlying graph is inhomogeneous. We also derive an information theoretic lower bound for this problem which shows that in some regimes the scan test is almost asymptotically optimal. We illustrate our results through examples and numerical experiments.

Original languageEnglish
Pages (from-to)1159-1188
Number of pages30
JournalBernoulli
Volume27
Issue number2
DOIs
Publication statusPublished - May 2021

Bibliographical note

Funding Information:
The work of RvdH was supported in part by the Netherlands Organisation for Scientific Research (NWO) through the Gravitation NETWORKS grant 024.002.003.

Publisher Copyright:
© 2021 ISI/BS

Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

Keywords

  • Community detection
  • Inhomogeneous random graphs
  • Minimax hypothesis testing
  • Scan statistics

Fingerprint

Dive into the research topics of 'Detecting a planted community in an inhomogeneous random graph'. Together they form a unique fingerprint.

Cite this