Graphs representing relationships between entities change over time, often through a smooth evolution as, e.g., social relationships evolve, and sometimes rapidly and in a striking, anomalous, way. Our project explores developing a statistical, model-based approach to anomaly detection in time-varying graphs. The approach fuses two new methodologies from researchers at AT&T Labs. The first is a principled and model-based approach to representation of dynamic graphs by communities of interest (COI). The COI representation is an approximation to the full dynamic graph that is shown to be efficient in handling massive data and supports efficient computations across multiple domains of application. The second methodology is a general empirical Bayesian approach to anomaly detection in a cross-classified data stream by a Kalman Filter for Contingency tables (KFC). The Bayesian approach compares observations with model-based expectations that are dynamically updated, and is efficient for modeling large arrays. The two methodologies come together in a providing a model-based approach to anomaly detection on dynamic graphs.
Document last modified on August 17, 2007.