Trimming the Hairball: Edge Cutting Strategies for Making Dense Graphs Usable

The application of modern NLP and ML techniques to large-scale datasets can generate implicit graphs that are so densely connected as to be unusable when rendered as node-link diagrams. We present a two-stage approach to extracting usable, map-like layouts from large, dense input graphs. This approach uses edge-cutting strategies based on node and edge metrics to reduce a graph to a skeletal structure showing only essential relationships, before filling in the resulting communities to create dense but usable layouts. Through a case study on a 145k-document adversarial health communication dataset, we show that each edge-cutting strategy has advantages and disadvantages, and that the appropriate choice of strategy depends on the data, user, and task.