STRATISFIMAL LAYOUT:一种分层节点链接网络可视化的模块化优化模型(STRATISFIMAL LAYOUT: A Modular Optimization Model for Laying out Layered Node-link Network Visualizations)

节点链接图是一个用于显示网络中关系的有效工具。本文关注于计算网络的分层布局,在这种布局中,节点被排列在一组平行的轴上,来更好地展示层次或顺序关系。通常基于启发式的布局方法 [1] 可以得到可读的,但不是最优的可视化结果。本文提出了STRATISFIMAL LAYOUT [2],一种模块化优化模型来计算最优的节点布局。

图1:模块化的优化模型

为了得到一个最优的分层布局,本文基于对已有工作的分析,定义了以下目标和约束。

优化目标:

  • 最小化边交叉:边交叉会对网络可视化的可读性产生严重的负面影响,因此,调整节点位置使边交叉的数量最小化是最优先的优化目标。
  • 最小化边弯曲:边弯曲也是一个对可读性有负面影响的指标。在分层布局中,如果一个边的两端不位于与各层垂直的线上,我们就定义它为弯曲的。

硬约束:必须满足的约束

  • 节点之间不能重叠。
  • 边之间不能重叠。
  • 在一个组的的标记所包围的区域内,只能有属于组的成员的节点。

软约束:希望能满足但不是必须要满足的约束

  • 矩形分组:一个组内的节点最好被布局在一个矩形区域内。
  • 分组区域最小化:每个组所占的区域应该尽可能的小。

如图1所示,本文根据以上的目标和约束,设计了三个模块进行优化,分别为最小化边交叉模块,最小化边弯曲模块和分组模块。每个模块将对应的目标和约束转化为模块化的整数线性规划描述,具体公式请参考论文,对公式细节描述和证明可参考 [3]。对问题进行建模之后,可以使用求解优化问题的常用库,例如GLPK.js或Gurobi来求解该问题。

由于此方法的模块化,通过选择不同的使用模块,可以适用与许多不同的场景。例如在故事线可视化中,使用本文提出的布局算法,可以得到最优的节点分层布局。如图2所示,在Star Wars trilogy数据的故事线可视化中,使用STRATISFIMAL LAYOUT得到的结果相比于之前的方法有更少的边交叉数量。

图2:在故事线可视化中的应用

[1] Hai Tang and Zhihui Hu. Network Simplex Algorithm for DAG Layering. International Conference on Computational and Information Sciences, pp. 1525-1528, 2013.

[2] Sara Di Bartolomeo, Mirek Riedewald, Wolfgang Gatterbauer, and Cody Dunne. STRATISFIMAL LAYOUT: A Modular Optimization Model for Laying out Layered Node-link Network Visualizations. IEEE VIS 2021.

[3] https://visdunneright.github.io/stratisfimal/proofs.html

发表评论?

0 条评论。

发表评论


注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>