Change-point methods on a sequence of graphs

Abstract

Given a finite sequence of graphs, e.g. coming from technological, biological, and social networks, the paper proposes a methodology to identify possible changes in stationarity in the stochastic process that generated such graphs. We consider a general family of attributed graphs for which both topology (vertices and edges) and associated attributes are allowed to change over time, without violating the stationarity hypothesis. Novel Change-Point Methods (CPMs) are proposed that map graphs onto vectors, apply a suitable statistical test in vector space and detect changes –if any– according to a user-defined confidence level; an estimate for the change point is provided as well. In particular, we propose two multivariate CPMs: one designed to detect shifts in the mean, the other to address more complex changes affecting the distribution. We ground our methods on theoretical results that show how the inference in the numerical vector space is related to the one in graph domain, and vice-versa. We also extend the methodology to handle multiple changes occurring in a single sequence. Results show the effectiveness of what proposed in relevant application scenarios.