TopFish - A Viewer for Very Large Graphs

Yehuda Koren, Emden Gansner, Stephen North

Internet router graph (full)	Internet graph (zoomed in TopFish)

BGP graph (random)	BGP graph (majorization)	BGP graph (zoomed in TopFish)

Interactively viewing and exploring very relational structures is a central problem in information visualization. Often raw data has hundreds, thousands, even millions of objects. At the low end of that range, just making a readable layout that can be examined with pan-and-zoom controls and text search is challenging. At the high end, though, it is simply impossible to see that many distinct inividual objects; in some way the data must be reduced; either before or after layout. The question is how to do this in a way that is good for interactive data exploration, and runs fast.

Yehuda Koren, Emden Gansner and Stephen North developed a novel large graph viewer called TopFish. TopFish assumes that a basic full layout is made externally. (This is a separate problem for which practical methods are available.) When TopFish loads the full layout, if it is large, nodes are usually overplotted and hard to distinguish. The TopFish solution is to allow a data analyst to set one or more focus points in the layout. TopFish then shows a very detailed view near a focus, and a simplified, but structurally correct view of the graph further away. The simplified view collapses nodes that are topologically and geometrically close, reducing visual clutter. Foci may be moved interactively. When this happens, some nodes are expanded to explose more detail, while others are collapsed as they become less important. Also, the layout is adjusted radially around foci for more uniform density, making the diagram easier to read. TopFish runs fast, and supports high-interaction exploration of graphs far too large to explore as flat structures.