Graph Waves

We present efficient algorithmic mechanisms to partition graphs with up to 1.8 billion edges into subgraphs which are fixed points of degree peeling. Similarly to, we are able to process graphs with tens of millions of edges in seconds and hundreds of millions of edges in minutes. For fixed points that turn out to be larger than a desired interactivity parameter we further decompose them with a novel (to our knowledge) linear algorithm into what we call “graph waves and fragments”. This decomposition is used to create spanning views of fixed points that we call “DAG Covers”. We illustrate these decompositions by presenting intuitive and interactive visualizations of the meta-structures of a variety of publicly available data sets including social, web, and citation networks.