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

Mustafa Hajij, Bei Wang, Carlos Scheidegger, Paul Rosen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

40 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationProceedings - 2018 IEEE Pacific Visualization Symposium, PacificVis 2018
PublisherIEEE Computer Society
Number of pages10
ISBN (Electronic)9781538614242
StatePublished - May 25 2018
Event11th IEEE Pacific Visualization Symposium, PacificVis 2018 - Kobe, Japan
Duration: Apr 10 2018Apr 13 2018

Publication series

NameIEEE Pacific Visualization Symposium
ISSN (Print)2165-8765
ISSN (Electronic)2165-8773


Other11th IEEE Pacific Visualization Symposium, PacificVis 2018


  • event detection
  • graph drawing
  • graph timeline
  • graph visualization
  • persistent homology
  • topological data analysis

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Computer Vision and Pattern Recognition
  • Hardware and Architecture
  • Software


Dive into the research topics of 'Visual Detection of Structural Changes in Time-Varying Graphs Using Persistent Homology'. Together they form a unique fingerprint.

Cite this