Fred Hohman
/ CSE Ph.D. Student at GT

Large Graph Exploration via Subgraph Discovery and Decomposition

James Abello, Fred Hohman, Varun Bezzam , Duen Horng Chau

The Graph Playground user interface. Graph Playground is composed of three main views: the 3D Overview (left), the Graph Ribbon (middle), and the Layers view (right). The Graph Ribbon that splits the display can be dragged left and right to adjust the visible screen real estate that either the Overview or Layers view shows. In the figure, the vertex "caeciliidae" is selected, coloring it blue in both the Overview and Layers view. Here we see "caeciliidae" (a worm-like amphibian) in layer 30 bridges two quasi-cliques (families of birds and families of sea snails) together, while its clone in layer 25 participates in another single quasi-clique (families of land creatures).

Abstract

We are developing an interactive graph exploration system called Graph Playground for making sense of large graphs. Graph Playground offers a fast and scalable edge decomposition algorithm, based on iterative vertex-edge peeling, to decompose million-edge graphs in seconds. Graph Playground introduces a novel graph exploration approach and a 3D representation framework that simultaneously reveals (1) peculiar subgraph structure discovered through the decomposition’s layers, (e.g., quasi-cliques), and (2) possible vertex roles in linking such subgraph patterns across layers.

Materials

PDF | BibTeX

Citation

Large Graph Exploration via Subgraph Discovery and Decomposition
James Abello, Fred Hohman, Varun Bezzam, Duen Horng Chau
arXiv:1808.04414. Aug 13, 2018.
Site | PDF | BibTeX

BibTeX

@article{hohman2018playground,
  title={Large Graph Exploration via Subgraph Discovery and Decomposition},
  author={Abello, James and Hohman, Fred and Bezzam, Varun and Chau, Duen Horng},
  journal={arXiv preprint arXiv:1808.04414},
  year={2018}
}