  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.
