Drawing Power Law Networks Using a Local/Global Decomposition

November 8, 2005
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.