This was part of Recent Advances in Random Networks

Finding Anomalous Cliques in Inhomogenous Networks using Egonets

Srijan Sengupta, North Carolina State University

Monday, January 12, 2026



Slides
Abstract: We consider the problem of finding an anomalous clique, i.e., a fully connected subgraph, hidden in a large network. There are two parts to this problem: (1) detection, i.e., determining whether an anomalous clique is present, and (2) identification or localization, i.e., given that an anomalous clique is detected in part 1, determining which vertices of the network constitute the clique. This problem has a number of practical applications, such as financial trading networks, brain networks, and online social networks. A rich literature already exists on the detection problem when restricted to homogeneous Erd˝os–R´enyi random graphs. However, currently, no method exists that can solve the detection and identification/localization problems for inhomogeneous networks in finite time. We propose an inferential tool based on egonets to address this gap. The proposed method is computationally efficient and naturally amenable to parallel computing and easily extends to a wide variety of inhomogeneous network models. We establish the theoretical properties of the proposed method and demonstrate its empirical performance through simulation studies.