Anomaly Detection in Time Series of Dependent Stochastic Block Model Graphs

• Activity Number: 445
• Type: Contributed
• Date/Time: Tuesday, August 2, 2016 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Learning and Data Science
• Author(s): Heng Wang and Albert Liu* and Youngser Park and Carey Priebe
• Companies: Machine Zone and Ward Melville High School and The Johns Hopkins University and The Johns Hopkins University
• Keywords: Anomaly Detection ; Graph Mining ; Temporal Graphs ; Scan statistics ; Social Network

Abstract

The change-point detection problem in a dynamic network is becoming increasingly prevalent in many applications of the emerging discipline of dynamic graph mining. Dynamic network data are often readily observed, with vertices denoting entities and time-evolving edges signifying relationships between entities, and thus considered as a time series of graphs, which is a natural framework for investigation.

In this presentation, we formulate the task as a hypothesis-testing problem in dependent stochastic block model time series. We numerically investigate the power characteristics of two competing scan statistics built on distinct underlying locality statistics. In addition, we consider the effect of errorful vertex correspondence on two competing test statistics. In terms of statistical power dominance and robustness, two scan statistics will be compared under dependency assumption of stochastic block model time series. Our result is a natural extension to a more general stochastic block model time series with both dependency and errorful vertex correspondence assumptions.