Characterization of L1-norm statistic for anomaly detection in Erdos Renyi graphs

Kadavankandy, Arun; Cottatellucci, Laura; Avrachenkov, Konstantin
CDC 2016, 55th IEEE Conference on Decision and Control, December 12-14, 2016, Las Vegas, USA

We describe a test statistic based on the L^1-norm of the eigenvectors of a modularity matrix to detect the presence of an embedded Erdos-Renyi (ER) subgraph inside a larger ER random graph. We make use of the properties of the asymptotic distribution of eigenvectors of random graphs to derive the distribution of the test statistic under certain conditions on the subgraph size and edge probabilities. We show that the distributions differ sufficiently for well defined ranges of subgraph sizes and edge probabilities of the background graph and the subgraph. This method can have applications where it is sufficient to know whether there is an anomaly in a given graph without the need to infer its location. The results we derive on the distribution of the components of the eigenvector may also be useful to detect the subgraph nodes.

Las Vegas
Systèmes de Communication
Eurecom Ref:
© 2016 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.