Motif Estimation via Subgraph Sampling: The Fourth-Moment Phenomenon

• Activity Number: 265 - Recent Advances in Statistical Network Analysis
• Type: Invited
• Date/Time: Wednesday, August 11, 2021 : 1:30 PM to 3:20 PM
• Sponsor: International Indian Statistical Association
• Author(s): Bhaswar Bikram Bhattacharya* and Sayan Das and Sumit Mukherjee
• Companies: Department of Statistics, University of Pennsylvania and Departments of Mathematics, Columbia University and Columbia University
• Keywords: Network analysis; Asymptotic Inference; Stein's method ; Random graphs

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. In this talk 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.