Title: Anomalous clique detection via egonets
Authors: Srijan Sengupta - North Carolina State University (United States) [presenting]
Abstract: Anomaly in networks often implies illegal or disruptive activity by the actors in the network. Networks can be static, where we have a single snapshot of the system, or dynamic, where we have network snapshots at several points in time. Anomalies can have different meanings in these two scenarios. In static networks, anomaly typically means a local anomaly, in the form of a small anomalous subgraph that is significantly different from the rest of the network. Local anomalies are difficult to detect using simple network-level metrics since the anomalous subnetwork might be too small to cause significant changes to network-level metrics, e.g., network degree. Instead, such anomalies might be detectable if we monitor sub-network level metrics, e.g., degrees of all subgraphs. However, that option is computationally infeasible, as it involves computing total degrees for all $O(2^n)$ subgraphs of an n-node network. We propose a novel anomaly detection method by using egonet $p$-values, where the egonet of a node is defined as the sub-network spanned by all neighbors of that node. Since there are exactly $n$ egonets, the number of subgraphs being monitored is n, which is a relatively manageable number. We establish the theoretical properties of the egonet method. We demonstrate its accuracy from simulation studies involving a broad range of statistical network models. We also illustrate the method on several well-studied network datasets.