Visual Detection of Structural Changes in Time-Varying Graphs Using Persistent Homology

Abstract

Topological data analysis is an emerging area in exploratory data analysis and data mining. Its main tool, persistent homology, has become a popular technique to study the structure of complex, high- dimensional data. In this paper, we propose a novel method using persistent homology to quantify structural changes in time-varying graphs. Specifically, we transform each instance of the time-varying graph into a metric space, extract topological features using persistent homology, and compare those features over time. We provide a visualization that assists in time-varying graph exploration and helps to identify patterns of behavior within the data. To validate our approach, we conduct several case studies on real-world datasets and show how our method can find cyclic patterns, deviations from those patterns, and one-time events in time-varying graphs. We also examine whether a persistence-based similarity measure satisfies a set of well-established, desirable properties for graph metrics.

Downloads

Download the Paper Download the BiBTeX

Citation

Mustafa Hajij, Bei Wang, Carlos Scheidegger, and Paul Rosen. Visual detection of structural changes in time-varying graphs using persistent homology. In Pacific Visualization, 2018.

Bibtex


@inproceedings{Hajij.2018.PVIS,
  title = {Visual Detection of Structural Changes in Time-Varying Graphs Using Persistent Homology},
  author = {Mustafa Hajij and Bei Wang and Carlos Scheidegger and Paul Rosen},
  booktitle = {Pacific Visualization},
  year = {2018},
  abstract = {Topological data analysis is an emerging area in exploratory data analysis and 
   data mining. Its main tool, persistent homology, has become a popular technique to study 
   the structure of complex, high- dimensional data. In this paper, we propose a novel method 
   using persistent homology to quantify structural changes in time-varying graphs. 
   Specifically, we transform each instance of the time-varying graph into a metric space, 
   extract topological features using persistent homology, and compare those features over 
   time. We provide a visualization that assists in time-varying graph exploration and helps to 
   identify patterns of behavior within the data. To validate our approach, we conduct several 
   case studies on real-world datasets and show how our method can find cyclic patterns, 
   deviations from those patterns, and one-time events in time-varying graphs. We also 
   examine whether a persistence-based similarity measure satisfies a set of well-established, 
   desirable properties for graph metrics.}
}