Persistent Homology Guided Force-Directed Graph Layouts

Graphs are commonly used to encode relationships among entities, yet their abstractness makes them difficult to analyze. Node-link diagrams are popular for drawing graphs, and force-directed layouts provide a flexible method for node arrangements that use local relationships in an attempt to reveal the global shape of the graph. However, clutter and overlap of unrelated structures can lead to confusing graph visualizations. This paper leverages the persistent homology features of an undirected graph as derived information for interactive manipulation of force-directed layouts. We first discuss how to efficiently extract 0-dimensional persistent homology features from both weighted and unweighted undirected graphs. We then introduce the interactive persistence barcode used to manipulate the force-directed graph layout. In particular, the user adds and removes contracting and repulsing forces generated by the persistent homology features, eventually selecting the set of persistent homology features that most improve the layout. Finally, we demonstrate the utility of our approach across a variety of synthetic and real datasets.

Ashley Suh, Mustafa Hajij, Bei Wang, Carlos Scheidegger, and Paul Rosen. Persistent Homology Guided Force-Directed Graph Layouts. IEEE Transactions on Visualization and Computer Graphics (IEEE InfoVis), 2020.

@article{suh2019persistent,
  title = {Persistent Homology Guided Force-Directed Graph Layouts},
  author = {Suh, Ashley and Hajij, Mustafa and Wang, Bei and Scheidegger, Carlos and
    Rosen, Paul},
  journal = {IEEE Transactions on Visualization and Computer Graphics (IEEE InfoVis)},
  year = {2020},
  note = {textit{Presented at InfoVis 2019.}},
  abstract = {Graphs are commonly used to encode relationships among entities, yet their
    abstractness makes them difficult to analyze. Node-link diagrams are popular for drawing
    graphs, and force-directed layouts provide a flexible method for node arrangements that
    use local relationships in an attempt to reveal the global shape of the graph. However,
    clutter and overlap of unrelated structures can lead to confusing graph visualizations.
    This paper leverages the persistent homology features of an undirected graph as derived
    information for interactive manipulation of force-directed layouts. We first discuss how
    to efficiently extract 0-dimensional persistent homology features from both weighted and
    unweighted undirected graphs. We then introduce the interactive persistence barcode used
    to manipulate the force-directed graph layout. In particular, the user adds and removes
    contracting and repulsing forces generated by the persistent homology features,
    eventually selecting the set of persistent homology features that most improve the
    layout. Finally, we demonstrate the utility of our approach across a variety of
    synthetic and real datasets.}
}