今天我们讨论的是由AT&T实验室Emden R. Gansner等发表的“Multilevel Agglomerative Edge Bundling for Visualizing Large Graphs”。这篇文章针对的还是怎么显示大规模的节点连接图(Node-Link Diagram)的问题。熟悉这个问题的同学或者看过我们前面帖子的同学都知道,当节点和边的数目变大的时候,如果随随便便往屏幕上直接画节点连接图,只能得到一堆像乱麻的东西。人们想了很多方法来解决这个问题,而其中连接线束(Edge Bundling)的方法(比如FDEB)是一种比较有效的方法:通过1)把很多类似的边合并,2)把边画成样条曲线,来得到既漂亮又简洁的图。但是现有的Edge Bundling的方法的算法复杂度大都是O(N^2)的,所以在实际应用中运行速度比较慢。而Emden R. Gansner提出了一种新的方法来加速Edge Bundling,下面的图显示他们方法的整个流程:

image courtesy of Emden R. Gansner,  Yifan Hu,  Stephen North and Carlos Scheidegger. AT&T Labs

给定原始的 边(a), 构造相似图(b), 从相似图中找到最应该合并的边,比如1和2, 3和4,5和6, 7和8,9和10。合并两条边的时候,先把两条边中间的部分并成一条边,然后两端长出两个小枝杈,代表原来的两条边,这样就生成图(c)。然后我们可以重复整个过程,构造图(c)的相似图(d),继续合并生成图(e)。继续的话,我们可以把所有的边都合并,生成图(f)。把图(f)中的边当作骨架,我们就可以生成样条曲线啦,得到图(g)。图(h)是调整一些参数的结果。

我们可以看出中间计算相似性和合并的过程是一个典型的自底向上的聚类(clustering)过程。而这篇论文新的地方是提出了一种组织边的方法:作者将每 条2维的线表示成一个4维空间的点(两端点各有一个2维坐标,所以一共有4个数值),然后在4维空间里,用k-d tree的方法,对每个点找它的最近邻居。这样的话,在计算机相似性的时候,每条边只要跟最近的邻居比较,而不用跟所有其他的边比较,可以把算法复杂度从 O(N^2)降到O(KlogN),其中N是边的数目,K是考虑的最近邻居数(比如只考虑最近的3个邻居,K就等于3)。在计算相似性的时候,作者引入 ink的概念,小编认为ink可以理解为像素,也就是两条边的相似性衡量为合并后像素的减少量,如果像素减的越多,则两条边越相似;所以每次迭代,当然合并最能减少像素的两条边。

下面的左图是原始的航线图,右图是使用他们方法的后结果。同学可以把他们的结果和FDEB方法的结果比较一下。从运行时间来看,在同样的运算平台上,新的方法只要0.1秒,而FDEB需要19秒,所以效率上提高还是比较明显的。

image courtesy of Emden R. Gansner,  Yifan Hu,  Stephen North and Carlos Scheidegger. AT&T Labs

© 2011, 视物 | 致知. All rights reserved.

Related Posts: