Title: Change detection and clustering in temporal graphs
Authors: Fabrice Rossi - Universite Paris Dauphine (France) [presenting]
Pierre Latouche - Sorbonne university (France)
Marco Corneli - Universite Cote d Azur (France)
Abstract: Graphs are commonly used to represent interactions between entities, interactions which can be repeated and happen at specific times. This leads naturally to the concept of temporal graphs. In general, those graphs are represented as a time series of static graphs using a crude time quantization technique: the data analyst chooses a timescale and disregards temporal information at a finer scale. For instance, one can produce daily interaction graphs. While this approach can produce interesting results, it cannot adapt to more complex schemes where a single time scale cannot capture the full temporal dynamic of the interactions. An alternative generative model is described that models directly the temporal structure of the dynamic graph. The model is based on the principle of the stochastic block model and extends the static setting to a temporal one by describing interactions between two classes of vertices via a non homogeneous Poisson point process (NHPPP). The complexity of those NHPPPs will be controlled by enforcing a piecewise constant structure on the intensity functions, with globally shared intervals. As a consequence, the estimation of the model will provide both a clustering structure for the vertices and time intervals in which all the NHPPPs will have constant but distinct intensities. This latter structure could be used to produce a time series of graphs with stationary interaction structure, leading to an automated local time scale analysis.