Drawing Power Law Networks Using a Local/Global Decomposition

Tuesday, November 8, 2005 - 11:00am - 12:00pm
EE/CS 3-180
It has been noted that many realistic networks have a power law degree distribution
and exhibit the small world phenomenon. We consider graph drawing methods that take
advantage of recent developments in the modeling of such networks.
Our main approach is to partition the edge set of a graph into local edges
and global edges, and to use a force-directed method that emphasizes the local edges.
We show that our drawing method works well for networks that contain underlying geometric graphs
augmented with random edges, and demonstrate the method on a few examples.
We present fast approximation algorithms for the maximum short flow problem, and for testing
whether a short flow of a certain size exists between given vertices.
Using these algorithms, we give a fast approximation algorithm for determining
local subgraphs of a given graph. The drawing algorithm we present can be applied to
general graphs, but is particularly well-suited for numerous small-world networks with power
law degree distribution.

This is a joint work with Reid Andersen and Linyuan Lu.