Fast and Readable Layered Network Visualizations Using Large Neighborhood Search

Layered network visualizations assign each node to one of several parallel axes. They can convey sequence or flow data, hierarchies, or multiple data classes, but edge crossings and long edges often impair readability. Layout algorithms can reduce edge crossings and shorten edges using quick heuristics or optimal methods that prioritize human readability over computation speed. This work uses an optimization metaheuristic to provide the best of both worlds: high-quality layouts within a predetermined execution time. Our adaptation of the large neighborhood search (LNS) metaheuristic repeatedly selects fixed-sized subgraphs to lay out optimally. We conducted a computational evaluation using 450 synthetic networks to compare five ways of selecting candidate nodes, four ways of selecting their neighboring subgraph, and three criteria for determining subgraph size. LNS generally halved the number of crossings versus the barycentric heuristic while maintaining a reasonable runtime. Our best approach randomly selected candidate nodes, used degree centrality to pick cluster-like neighborhoods, and chose smaller neighborhoods that could be optimally laid out in 0.6 or 1.2 seconds (versus 6 seconds). In a case study visualizing 13 control flow graphs, most with over 1000 nodes, we show that our method can be employed to create visualizations with fewer crossings than Tabu Search, another metaheuristic, and vastly outperforms an ILP solver when runtime is bounded.