在图序列中分析动态层次(Visualizing Dynamic Hierarchies in Graph Sequences)

图经常用来描述对象之间的关系,基于对象之间的连接关系,我们可以通过层次聚类的算法将对象进行层次化分组(grouped hierarchically)。在许多应用中,对象之间的关系随着时间变化,因此它们的分层组织结构(hierarchical group structure)也发生变化。本文设计了一种可视化形式支持对动态图的拓扑结构和分层组织结构进行分析并且追踪它们的变化。

1

图1 根据图的拓扑结构得到分层组织结构

vehlow1图2 与图的拓扑以及分层组织结构相关连的任务

在图2中,当图的拓扑结构发生巨大变化时(顶部行),相应的分层组织结构也发生变化(底部行)。这样,我们可以得到如下的分析任务:

I) Topology-to-Hierarchy Task: 分析单个图的分层组织结构和拓扑结构之间的一致性(绿色)

II)Topology-to-Topology Task: 分析拓扑结构随时间变化情况(蓝色)

III)Hierarchy-to-Hierarchy Task: 分析分层组织结构随时间变化情况(紫色)

IV)Change-to-Change Task: 分析拓扑结构的变化是否在层次结构的变化中反映出来

为了在每个图中编码层次结构信息,作者采用了邻接矩阵的方式可视化动态图。

未标题-4图3 通过矩阵展现图的拓扑结构和分层组织结构

如图3所示,矩阵中每一行/列代表图中的一个节点,每一个方形代表一条边,通过颜色的亮度表现边的权重。其中,绿色的方形代表新加入的边,带有紫色边框的方形代表刚除去的边。通过嵌入式的边界(nested contours)来表现图的层次结构,红色的边界围起来的节点代表它们在同一个层次下,其中的背景深度代表这个层次中边的密度,层次与层次之间的边的密度通过邻接矩形的背景色表现。在矩阵的四周通过冰柱图(Icicle plots)进一步加强对图的分层组织结构的感知,通过压痕(Indentation)划分不同的层次结构,冰柱图的叶子节点代表图上的 节点。通过这种方式,我们可以从矩阵中观察到图的拓扑结构,也可以看到图的分层组织结构。

为了比较在不同时间点图的分层组织结构的变化,作者提出了一种计算一个节点在两个层次结构中差异性(dissimilarity)的方法,并通过连边的颜色映射这种差异性,而两个层次结构的整体差异是所有节点差异性和的平均值。这样,我们可以具体比较两个层次结构的差异性。

algorithm

图4 计算节点在相邻分组层次结构中的差异性

同时,为了减少边的交叉给视图带来的干扰,作者采用了类似[2]中方法对冰柱图的叶子节点排序。

下面以Junit regression testing framework数据为例,介绍这个可视化工作如何帮助开发者发现软件开发过程中类(classes)之间的依赖关系以及不合理的包(package)设计问题。该软件包含21个版本,因此每一个图序列(graph sequence)包含21个邻接矩阵,为了便于分析,如果相邻的矩阵差异性较小,将它们合并,最后每个行序列只剩下6个邻接矩阵。case2

图5 合并后的Junit演变视图

在这个视图中,矩阵中的每一个节点代表一个类,节点之间的边代表一个类对另一个类的依赖数量。两个图序列分别是Hierarchical Clustering, Package Structure. Hierarchical Clustering中分层组织结构是根据图的拓扑结构由层次聚类算法得到,而Package Structure中的分层组织结构则是根据软件中包与包,包与类之间的固有关系得到。邻接矩阵之间的蓝色矩形代表两个graph中层次结构之间的差异性,绿色矩形代表新加入边的数量,紫色矩形代表减少边的数量。

从视图中,我们可以看出随着版本的升级,Junit framework的结构变得越来越庞大,出现了更多的类。在4.0.0版本中引入了包org,导致图的分层组织机构发生了巨大的变化(B中蓝色矩形)。在Package Structure 中,包Junit(B)与包org.Juint中的一些类有轻微耦合,然而在Hierarchical Clustering中,包Junit与org.Junit中耦合的类被整合在同一层次中。还有Junit.extensions中类(F),依赖于Junit.framework,在Hierarchical Clustering中也被聚合到同一个层次中。

detail2

图6 通过zoom,观察junit-4.5.0-4.8.1的细节

通过观察Hierarchical Clustering和Package Structure冰柱图叶子的连边,我们可以发现一些类应该移动到不同的包中,比如包org.juint.internal中的类SuiteMethod应该移到org.framework(A)。对于一些包在两种分组层次结构中有着良好的一致性(B),表明这些包的设计满足高内聚、低耦合的特点。在一些包中(C),内部的类并没有依赖关系。

所以通过这种可视化的方式,我们可以发现软件设计过程中不合理的包依赖关系从而提高软件的质量。

总体来说,这篇文章通过组合已有的可视化元素(矩阵、冰柱图)实现了分析动态图中分层组织结构随着拓扑结构的变化,并且可以比较不同的分层组织结构方法。但是可视化方式有些复杂,需要一个学习过程,并且比较临近矩阵的结构变化。由于节点在矩阵中的位置不是固定的,会给人带来节点在分层组织结构中发生变化的误解。

参考文献:

[1] Corinna Vehlow, Fabian Beck,  Daniel Weiskopf. Visualizing Dynamic Hierarchies in Graph Sequences. In IEEE Transactions on Visualization and Computer Graphics, (to appear), 2016.

[2] D. Holten and J. J. van Wijk. Visual comparison of hierarchically organized data. Computer Graphics Forum, vol. 27, no. 3, pp. 759–766, 2008.

 

评论关闭。