Taming a Graph Hairball: Local Exploration in a Global Context

A variety of data sets can be modelled as an underlying reference topology where every vertex has an associated set of attributes or key words that are not necessarily derived from the topology. Blind application of most graph drawing algorithms produces a “hairball” even for modest graph sizes. In this chapter, we explore several intuitive mechanisms to decompose a weighted graph into vertex clusters and edge layers that facilitate user exploration. Our approach minimizes the screen bottleneck by enhancing the graph topology with weights on the given edges that encode their pairwise vertex similarity (avoiding the quadratic pairwise computation of vertex similarity if the given graph topology is sparse). The decompositions are based on graph distance topology clustering coupled with iterative peeling. Information from these decompositions is used to landmark vertices that drive egonet user exploration. These landmarks are vertices of “high diversity” in the decomposition that “dominate” the vertex set in terms of Shannon entropy. We illustrate the usefulness of this decomposition on the On-Line Encyclopaedia of Integer Sequences. Our method can be used as a first step for community detection, graph visualization, and data summarization. These techniques can be applied to situations in business analytics, for example, when studying a network of products frequently purchased together.