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

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.

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.

@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.}
}