 |
Center for Nonlinear Studies |
Anomaly detection on graphs of social or communication networks has important security applications. However, learning the network structure of a large graph is computationally demanding, and dynamically monitoring the network over time for any changes in structure threatens to be more challenging still. This talk presents a two-stage method for anomaly detection in dynamic graphs: the first stage uses simple, conjugate Bayesian models for counting processes to track the pairwise links of all nodes in the graph to assess normality of behaviour; the second stage applies standard network inference tools on a greatly reduced subset of potentially anomalous nodes identified in the first stage. Two alternative methods are considered for monitoring communications (stage 1). The first method aggregates the data into discrete time periods and fits a probability model to the communication counts. Outlying counts according to this probability model then define the anomalies. Such a procedure is computationally very fast, but there are also limitations which will be discussed. The second method assumes communications to be event times from an inhomogeneous Poisson process with piecewise constant intensity. There, anomalous behaviour is defined by a recent change in intensity. This more flexible modelling framework does not carry the limitations of the first method but also adds an extra computational challenge; to address this, a novel sequential Monte Carlo algorithm is introduced which allows the rapid inference required.
Host: Garrett Kenyon, gkenyon@lanl.gov, 7-1900