Heterogeneous Dense Subhypergraph Detection
This work addresses a theoretical problem in hypergraph analysis, with potential applications in network science, but it is incremental as it builds on existing detection frameworks.
The paper tackles the problem of detecting a heterogeneous dense subhypergraph in random hypergraphs, establishing detection boundaries and constructing an asymptotically powerful test for known edge probabilities, along with an adaptive test that does not require this knowledge.
We study the problem of testing the existence of a heterogeneous dense subhypergraph. The null hypothesis corresponds to a heterogeneous Erdös-Rényi uniform random hypergraph and the alternative hypothesis corresponds to a heterogeneous uniform random hypergraph that contains a dense subhypergraph. We establish detection boundaries when the edge probabilities are known and construct an asymptotically powerful test for distinguishing the hypotheses. We also construct an adaptive test which does not involve edge probabilities, and hence, is more practically useful.