Test dense subgraphs in sparse uniform hypergraph

Mingao Yuan and Yehong Nan

Communications in Statistics - Theory and Methods, 2021, vol. 50, issue 20, 4743-4762

Abstract: In network data analysis, one of the fundamental data mining tasks is to find dense subgraphs, which has wide applications in biology, finance, graph compression and so on. In practice, given network data, it’s unknown whether a dense subgraph exists or not. Statistically, this problem can be formulated as a hypothesis testing problem: under the null distribution, there is no dense subgraph while under the alternative hypothesis, a dense subgraph exists. In the graph regime, this problem has been well studied. However, in the hypergraph case, to our knowledge, it’s still open. In this paper, we study the problem in the context of uniform hypergraphs. Specifically, we propose a test statistic, derive its asymptotic distributions under the null and alternative hypothesis, and show the power may approach one when the sample size goes to infinity. Then we use simulation and real data to evaluate the finite sample performance of our test.

Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/03610926.2020.1723637 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:lstaxx:v:50:y:2021:i:20:p:4743-4762

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/lsta20

DOI: 10.1080/03610926.2020.1723637

Access Statistics for this article

Communications in Statistics - Theory and Methods is currently edited by Debbie Iscoe

More articles in Communications in Statistics - Theory and Methods from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().