EcoSta 2022: Start Registration
View Submission - EcoSta2022
A0694
Title: Motif estimation via subgraph sampling: The fourth-moment phenomenon Authors:  Bhaswar Bhattacharya - University of Pennsylvania (United States) [presenting]
Sayan Das - Columbia University (India)
Sumit Mukherjee - Columbia University (United States)
Abstract: Network sampling has emerged as an indispensable tool for understanding features of large-scale complex networks where it is practically impossible to search/query over all the nodes. Examples include social networks, biological networks, internet and communication networks, and socio-economic networks, among others. We will discuss a unified framework for statistical inference for counting motifs, such as edges, triangles, and wedges, in the widely used subgraph sampling model. In particular, we will provide precise conditions for the consistency and the asymptotic normality of the natural Horvitz-Thompson (HT) estimator, which can be used for constructing confidence intervals and hypothesis testing for the motif counts. As a consequence, an interesting fourth-moment phenomenon for the asymptotic normality of the HT estimator and connections to fundamental results in random graph theory will emerge.