集合可视化是信息可视化的一个重要研究领域。对于抽象集合系统的可视化，一种常用的方法是欧拉图，但是它通常侧重于集合关系而不关注其中的单个元素。来自德国波恩大学和维也纳技术大学的研究人员提出了MosaicSets [1]，一种将给定的集合系统嵌入到规定的网格图中的可视化方法。如图1所示，该可视化包括基本地图(Base map)和覆盖(Overlay)两部分组成，基本地图中的相同颜色的节点属于同一个集合，覆盖中由一种颜色的边框包围的节点属于同一个集合。
该工作首先对问题进行形式化的建模，目标是要找到一个单射，将所有集合中的元素映射到网格图上，尽可能靠近网格的中央，并且保证出现在同一个集合中的元素映射后在图上的节点集合的导出子图是一个连通图。该工作证明了这样的一个问题是NP-hard的，因此该工作使用了整数线性规划(Integer Linear Programming)的方法来建模并求解该问题。
首先对集合中的每个元素s到图中的每个节点v引入一个0-1变量\(
x_{s, v} \)表示他们之间的关系，1表示该元素被映射到这个节点上，0表示没有这样的映射关系。为了保证集合中元素映射后在图上的连通性，该工作引入了一个多商品网络流模型，将网格图假想为一个双边有向图，每一个集合i被建模成一个商品网络流，边上流量\( y_{u,v} ^ {i} \)最大为集合中元素的数量，随机选择一个集合中的元素\( c_{i} \)作为汇点，其他集合中的元素作为源点，如果这个网络流问题可以求解得到合理的边流量，那么这个集合中元素映射到图上的节点是连通的。最终的需要最小化的目标函数如下所示：
\( \sum_{s \in S}\sum_{v \in V} w(s, v) \cdot x_{s, v} \)
其中\( w(s, v) \) 是衡量紧密度的指标，表示节点位置到网格中央的距离的平方。
\( w(s,v) = \Vert v.p – u \Vert ^{2} \)
使得映射满足单射关系的约束如下所示：
\( \sum_{v \in V} x_{s, v} = 1 \quad \forall s \in S \)
\( \sum_{s \in S} x_{s, v} \leq 1 \quad \forall v \in V \)
使得一个集合的所有元素中映射后在图上连通的约束如下所示：
\( \sum_{(v, w) \in E} y_{v, w} ^ {i} – \sum_{(u, v) \in E} y_{u, v} ^ {i} = \sum_{s \in S_{i}} x_{s, v} – |S_{i}|\cdot x_{c_{i}, v} \quad \forall S_i \in C, \forall v \in V \)
\( \sum_{(u, v) \in E} y_{u, v} ^ {i} \leq (|S_i| – 1) \cdot \sum_{s \in S_i} x_{s,v} \quad \forall S_i \in C, \forall v \in V \)
通过求解如上的整数线性规划问题，就可以得到集合到图中节点的映射关系，从而绘制MosaicSets可视化。除了基本的建模之外，该工作还提出了两种优化集合紧密度的方法。其中一种是通过最小化每个集合在图上的半径来实现的，另一种则是通过在计算紧密度指标时按集合内部计算，即计算节点位置到该集合中所有节点的重心的距离平方。
在计算得到节点位置后，需要绘制覆盖来表示集合关系，该工作提供了两种不同的风格。第一种风格如图2左侧所示，渲染每个集合的区域边界，边界本身被画在单元格边界的内侧。第二种风格则是类似KelpFusion[2]的风格。在作者与专家的讨论中提到，专家认为第一种风格合适，第二种则不太直观。
参考文献
[1] P. Rottmann, M. Wallinger, A. Bonerath, S. Gedicke, M. Nöllenburg and J. -H. Haunert, “MosaicSets: Embedding Set Systems into Grid Graphs,” IEEE Transactions on Visualization and Computer Graphics, 2022.
[2] W. Meulemans, N. H. Riche, B. Speckmann, B. Alper and T. Dwyer, “KelpFusion: A Hybrid Set Visualization Technique,” IEEE Transactions on Visualization and Computer Graphics, 19(11):1846-1858, 2013.
评论关闭。