在超图中，每条边不再仅限于表示一个二元关系，而是能够表示一个任意的n元关系（n大于等于2），如果依然使用传统的点边形式(node-link)对超图进行可视化，那么每一条边都将被表示为一个团的结构，这会带来大量的边，导致视觉聚集，从而干扰用户对图结构的认知过程。本文提出了使用多边形来对超边进行可视化的方法（图1），并最终给出了一种支持对偶视图形式的自动布局算法。
具体地来说，在本文的可视化设计中，每一条表示n元关系的边被一个多边形代表，而每一个多边形顶点，则表示一个超图中的点，如果一个超图中的点被包含在多组关系中，那么在最终的可视化中，这些关系所对应的多边形将共用这个顶点。
在确定了可视化的设计之后，更加困难的事在于如何对这样的一个多边形视图进行自动地布局，以达到良好的视觉效果。作者从直觉上和先前的一些工作中总结出了四个布局的目标：
- 规则性：正多边形是更加易于辨认的，所以所有的多边形都应该要是正多边形，如果有两个多边形存在三个以上的公共点，那么这两个多边形相交的部分应该也要是规则的。
- 简单性：在某些时候要使得所有多边形是严格规则的是很困难的，此时应该要保证每个多边形至少是简单多边形（即无自交），自交会严重干扰用户对多边形个体的感知，使得用户难以在不同个多边形个体中做出分辨。
- 减少重叠：无关的或只具有较弱关系的多边形之间的重叠面积应该尽量地少，过多的重叠同样会干扰用户的感知。
- 等比面积：多边形的面积大小应该要和多边形的顶点数成正比，这样能够帮助用户对每组关系的大小拥有更快的感知。
在这四条规则之下，作者设计了不同的能量函数和绘制方法（图2），这里就简要介绍这些方法背后的思想，具体公式请参考论文。
- 规则性：此部分包括使得多边形以及两个多边形的重叠部分尽可能规则的能量函数，以及让重叠部分尽可能在中间位置的能量函数。
- 要使得每个多边形以及两个多边形的重叠部分尽可能是正多边形，可以使用多边形的直径与面积之比作为能量函数，这一指标可以反映多边形规则的程度，在顶点数固定式，一个正多边形具有最小的比值。
- 要使得多边形的重叠时重叠部分将两个多边形均匀划分，可以使用理想情况下的平均边长时实际划分边长的平方误差作为能量函数。
- 简单性：对于简单性，使用特殊的多边形绘制方法来达成，即在为一组顶点绘制多边形时，按照其凸包重心到每个点的角度排序的顺序绘制，这样可以保证不会有自交的情况出现。
- 减少重叠：对于无公共顶点的多边形，使用他们之间的实际距离和理想距离的平方误差作为能量函数；对于公共一个顶点的多边形，则可以使用角度来衡量；对于公共两个顶点的多边形，也适用距离作为标准。
- 等比面积：可以通过要求每个多边形的边长恰好为1来达到，使用实际边长和1之间的误差的平方作为能量函数。
在确定了能量函数与绘制方法之后，作者使用L-BFGS优化方法与贪心地顶点顺序交换来迭代优化整体布局，每一次迭代的时间复杂度为O(|V+E|^4)，最终能够在较短的时间内取得较好的效果。
同时，考虑到超图自身天然存在的对偶表示，作者同样利用了这一性质通过对偶的编码方式展示超图中的点和边，使得用户能选择具有优势的视图完成对应的任务。
作者最后还进行了用户实验，对比了新方法与之前的方法的有效性（图3），也通过实验证明了对偶视图在任务中对用户的帮助，并通过两个案例研究为读者展示了更多结果与实例。
总的来说，本工作使用多边形简化了图中n元关系表示，并精心地发掘设计需求，从不同角度设计了目标函数，成功地提出了一种具有良好效果的超图可视化方法。值得一提地时，作者在叙述时引入CW complex的概念，在CW complex下，这种包含点，线，多边形的视图与传统的只包含点和线的可视化是具有一定统一性的，这或许值得更加深入的思考与研究。
评论关闭。