快速可读的分层网络可视化使用大邻里搜索
IEEE transactions on visualization and computer graphics
|March 3, 2025
概括
本研究引入了一种使用大邻里搜索 (LNS) 改进分层网络可视化的新方法. 在LNS方法显著减少边缘交叉在网络布局,提高可读性在实际的时间限制.
科学领域:
- 计算机科学 计算机科学
- 信息可视化 信息可视化
- 图形绘制 图形绘制 图形绘制
背景情况:
- 层级网络可视化对于表示复杂数据至关重要,但通常会受到边缘交叉和长边缘的影响,从而损害可读性.
- 现有的布局算法使用启发式或最佳方法,以计算时间换取质量.
研究的目的:
- 开发一种优化元启发方法,以平衡高质量的网络布局与预先确定的执行时间.
- 通过最小化边缘交叉和边缘长度来提高分层网络可视化的可读性.
主要方法:
- 开发了大邻里搜索 (LNS) 元启发式的适应,该元启发式反复选择固定大小的子图,以获得最佳布局.
- 一个计算评估比较了五个节点选择策略,四个邻里选择方法和三个子图大小标准在450个合成网络上.
- 在一个案例研究中,该方法在13个大型控制流图上进行了进一步测试.
主要成果:
- 与重心启发式相比,LNS元启发式通常将边缘交叉减少了一半,同时保持合理的运行时间.
- 最优的方法涉及随机候选节点选择,社区识别的中心度,以及小子图大小 (0.6或1.2秒布局时间).
- 在案例研究中,LNS方法的交叉结果比 Tabu Search 的交叉结果要少,并且在有限运行时间下显著优于 ILP 解决程序.
结论:
- 提出的基于LNS的优化元启发有效地在特定的时间限制内生成高质量的分层网络可视化.
- 这种方法为创建更易于阅读的网络图提供了实际解决方案,在时间有限的场景中优于 Tabu Search 和 ILP 解决方案等现有方法.
