Fast and Readable Layered Network Visualizations Using Large Neighborhood Search

Area of Science:

• Computer Science
• Information Visualization
• Graph Drawing

Background:

• Layered network visualizations are crucial for representing complex data but often suffer from edge crossings and long edges, impairing readability.
• Existing layout algorithms use heuristics or optimal methods, trading off quality for computation time.

Purpose of the Study:

• To develop an optimization metaheuristic that balances high-quality network layouts with predetermined execution times.
• To improve the readability of layered network visualizations by minimizing edge crossings and edge lengths.

Main Methods:

• An adaptation of the large neighborhood search (LNS) metaheuristic was developed, which repeatedly selects fixed-sized subgraphs for optimal layout.
• A computational evaluation compared five node selection strategies, four neighborhood selection methods, and three subgraph size criteria on 450 synthetic networks.
• The method was further tested on 13 large control flow graphs in a case study.

Main Results:

• The LNS metaheuristic generally reduced edge crossings by half compared to the barycentric heuristic, while maintaining reasonable runtimes.
• The optimal approach involved random candidate node selection, degree centrality for neighborhood identification, and small subgraph sizes (0.6 or 1.2 seconds layout time).
• In case studies, the LNS method produced fewer crossings than Tabu Search and significantly outperformed an ILP solver under bounded runtime.

Conclusions:

• The proposed LNS-based optimization metaheuristic effectively generates high-quality layered network visualizations within specified time constraints.
• This approach offers a practical solution for creating more readable network diagrams, outperforming existing methods like Tabu Search and ILP solvers in time-bounded scenarios.