2005-43: Interactive Navigation of Power-Law Graphs

DIMACS TR: 2005-43

Interactive Navigation of Power-Law Graphs

Authors: James Abello and Frank van Ham

ABSTRACT
We illustrate how iterated deletion of vertices of degree one, followed by biconnected graph decomposition constitute simple but powerful preprocessing steps that we can use to create suitable hierarchies on a graph. These hierarchies can then aid us substantially in the process of graph layout and navigation. The benefits of this approach are more apparent on sparse power-law graphs when a hierarchy tree is computed for each biconnected component via recursive clustering. Our sample data sets include an Autonomous System-level Internet topology with 11461 vertices and a 43,433 vertex graph detailing the static call dependencies of the Linux core.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-43.ps.gz

DIMACS Home Page