Discovering patterns in time-varying graphs: a triclustering approach

DOI10.1007/S11634-015-0218-6zbMATH Open1416.62375arXiv1608.07929OpenAlexW3099506693MaRDI QIDQ1630871FDOQ1630871

Authors: Romain Guigourès, Marc Boullé, Fabrice Rossi 

Publication date: 5 December 2018

Published in: Advances in Data Analysis and Classification. ADAC (Search for Journal in Brave)

Abstract: This paper introduces a novel technique to track structures in time varying graphs. The method uses a maximum a posteriori approach for adjusting a three-dimensional co-clustering of the source vertices, the destination vertices and the time, to the data under study, in a way that does not require any hyper-parameter tuning. The three dimensions are simultaneously segmented in order to build clusters of source vertices, destination vertices and time segments where the edge distributions across clusters of vertices follow the same evolution 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 any a priori quantization. Experiments conducted on artificial data illustrate the good behavior of the technique, and a study of a real-life data set shows the potential of the proposed approach for exploratory data analysis.

Full work available at URL: https://arxiv.org/abs/1608.07929

Recommendations

• scientific article; zbMATH DE number 6781370
• Model-based clustering of time-evolving networks through temporal exponential-family random graph models
• Components in time-varying graphs
• Clustering, Visualizing, and Navigating for Large Dynamic Graphs
• A novel evolutionary clustering via the first-order varying information for dynamic networks

zbMATH Keywords

model selectionco-clusteringgraph miningtime-varying graph

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Multivariate analysis (62H99) Learning and adaptive systems in artificial intelligence (68T05)

Cites Work

• Latent block model for contingency table
• Estimation and Prediction for Stochastic Blockstructures
• Elements of Information Theory
• A survey of statistical network models
• A Mathematical Theory of Communication
• Machine learning. A probabilistic perspective
• Title not available (Why is that?)
• Graph clustering
• 10.1162/153244303321897735
• Three-mode partitioning
• Two-mode clustering methods: astructuredoverview
• Divergence measures based on the Shannon entropy
• Variable neighborhood search: Principles and applications
• A state-space mixed membership blockmodel for dynamic network tomography
• Classification of Text Documents
• Information Theoretic Comparison of Stochastic Graph Models: Some Experiments

Cited In (3)

• Title not available (Why is that?)
• Dynamic stochastic block models: parameter estimation and detection of changes in community structure
• The dynamic stochastic topic block model for dynamic networks with textual edges

Uses Software

• PMTK
• GraphScope

This page was built for publication: Discovering patterns in time-varying graphs: a triclustering approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1630871)