A Triclustering Approach for Time Evolving Graphs

Abstract

This paper introduces a novel technique to track structures in time evolving graphs. The method is based on a parameter free approach for three-dimensional co-clustering of the source vertices, the target vertices and the time. All these features are simultaneously segmented in order to build time segments and clusters of vertices whose edge distributions are similar and evolve in the same way over the time segments. The main novelty of this approach lies in that the time segments are directly inferred from the evolution of the edge distribution between the vertices, thus not requiring the user to make an a priori discretization. Experiments conducted on a synthetic dataset illustrate the good behaviour of the technique, and a study of a real-life dataset shows the potential of the proposed approach for exploratory data analysis.

References in corpus (3)

• Mixed membership stochastic blockmodels
• A state-space mixed membership blockmodel for dynamic network tomography
• Role models for complex networks

Cited by in corpus (8)

• Exact ICL maximization in a non-stationary temporal extension of the stochastic block model for dynamic networks
• Discovering Patterns in Time-Varying Graphs: A Triclustering Approach
• Block modelling in dynamic networks with non-homogeneous Poisson processes and exact ICL
• Exact ICL maximization in a non-stationary time extension of the latent block model for dynamic networks
• Co-Clustering Network-Constrained Trajectory Data
• Modelling time evolving interactions in networks through a non stationary extension of stochastic block models
• A Study of the Spatio-Temporal Correlations in Mobile Calls Networks
• An Information-theoretic Framework for the Lossy Compression of Link Streams