Change-Point Detection in Time Series of Attributed Graphs

• Activity Number: 133
• Type: Contributed
• Date/Time: Monday, August 2, 2010 : 8:30 AM to 10:20 AM
• Sponsor: IMS
• Author(s): Lucy F. Robinson*+ and Carey E. Priebe and Nam Lee
• Companies: The Johns Hopkins University and The Johns Hopkins University and The Johns Hopkins University
• Keywords: networks ; change point ; random graphs

Abstract

We introduce a class of latent process models for time series of attributed graphs that is amenable to change point detection. Our goal is to detect a subpopulation of vertices exhibiting a change in behavior over time. Each edge has a location in continuous time and an attribute (e.g. the time and topic of an email message). We model the probability of edges and their attributes through time using a latent-space stochastic process associated with each vertex. A random dot product model is used to describe the dependency structure of the graph. We wish to detect shifts from homogeneity across vertices to a mixed population exhibiting anomalous behavior in a subset of vertices. The anomalous vertices' change is exhibited in altered behavior in both probability of interconnection and attribute distribution. Change point inference is performed using a modified likelihood ratio test.