Driving Interactive Graph Exploration Using 0-Dimensional Persistent Homology Features

Abstract

Graphs are commonly used to encode relationships among entities, yet, their abstractness makes them incredibly difficult to analyze. Node-link diagrams are a popular method for drawing graphs. Classical techniques for the node-link diagrams include various layout methods that rely on derived information to position points, which often lack interactive exploration functionalities; and force-directed layouts, which ignore global structures of the graph. This paper addresses the graph drawing challenge by leveraging topological features of a graph as derived information for interactive graph drawing. We first discuss extracting topological features from a graph using persistent homology. We then introduce an interactive persistence barcodes to study the substructures of a force-directed graph layout; in particular, we add contracting and repulsing forces guided by the 0-dimensional persistent homology features. Finally, we demonstrate the utility of our approach across three datasets.

Downloads

Download the Paper Download the BiBTeX

Citation

Ashley Suh, Mustafa Hajij, Bei Wang, Carlos Scheidegger, and Paul  Rosen. Driving interactive graph exploration using 0-dimensional persistent homology features. arXiv preprint arXiv:1712.05548, 2017.

Bibtex


@article{Suh.2017.ARXIV,
  title = {Driving Interactive Graph Exploration Using 0-Dimensional Persistent Homology Features},
  author = {Ashley Suh and Mustafa Hajij and Bei Wang and Carlos Scheidegger and Paul Rosen},
  journal = {arXiv preprint arXiv:1712.05548},
  year = {2017},
  abstract = {Graphs are commonly used to encode relationships among entities, yet, 
   their abstractness makes them incredibly difficult to analyze. Node-link diagrams are 
   a popular method for drawing graphs. Classical techniques for the node-link diagrams 
   include various layout methods that rely on derived information to position points, 
   which often lack interactive exploration functionalities; and force-directed layouts, 
   which ignore global structures of the graph. This paper addresses the graph drawing 
   challenge by leveraging topological features of a graph as derived information for 
   interactive graph drawing. We first discuss extracting topological features from a graph 
   using persistent homology. We then introduce an interactive persistence barcodes to 
   study the substructures of a force-directed graph layout; in particular, we add 
   contracting and repulsing forces guided by the 0-dimensional persistent homology 
   features. Finally, we demonstrate the utility of our approach across three datasets.}
}