  One of the fundamental task in graph data mining is to find a planted
community(dense subgraph), which has wide application in biology, finance, spam
detection and so on. For a real network data, the existence of a dense subgraph
is generally unknown. Statistical tests have been devised to testing the
existence of dense subgraph in a homogeneous random graph. However, many
networks present extreme heterogeneity, that is, the degrees of nodes or
vertexes don't concentrate on a typical value. The existing tests designed for
homogeneous random graph are not straightforwardly applicable to the
heterogeneous case. Recently, scan test was proposed for detecting a dense
subgraph in heterogeneous(inhomogeneous) graph(\cite{BCHV19}). However, the
computational complexity of the scan test is generally not polynomial in the
graph size, which makes the test impractical for large or moderate networks. In
this paper, we propose a polynomial-time test that has the standard normal
distribution as the null limiting distribution. The power of the test is
theoretically investigated and we evaluate the performance of the test by
simulation and real data example.
