Change-point methods on a sequence of graphs
Zambon, D; Alippi, C; Livi, L
Date: 6 December 2019
Journal
IEEE Transactions on Signal Processing
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Publisher DOI
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 ...
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.
Computer Science
Faculty of Environment, Science and Economy
Item views 0
Full item downloads 0