Visual Detection Of Structural Changes In Time-Varying Graphs Using Persistent Homology

Visual Detection Of Structural Changes In Time-Varying Graphs Using Persistent Homology
Mustafa Hajij, Bei Wang, Carlos Scheidegger, and Paul Rosen
IEEE Pacific Visualization Symposium, 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.

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. IEEE Pacific Visualization Symposium, 2018.

Bibtex


@inproceedings{hajij2018visual,
  title = {Visual Detection of Structural Changes in Time-Varying Graphs Using Persistent
    Homology},
  author = {Hajij, Mustafa and Wang, Bei and Scheidegger, Carlos and Rosen, Paul},
  booktitle = {IEEE Pacific Visualization Symposium},
  series = {PacificVis},
  pages = {125--134},
  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.}
}