在图上给边“扎个头发”会怎么样?

原创
2019/12/23 10:32
阅读数 4K

引言 —— 你看这错综复杂的图像不像早上没梳头的女盆友?真想给她扎个美美的头发呀。首先,你得....。害,没女友没关系!先给图可视化扎个头吧!大规模图往往具有复杂的数据关系。视觉混乱是可视化大规模图的一大问题。研究者们提出了多种降低视觉混乱的方法。其中,边绑定(扎头发大法)是一种高效的、可减轻混乱、展现高层级的边趋势的方法。

本文中部分图可视化由 G6 提供支持。G6 —— 专业的图可视化引擎。让关系数据变得简单透明,让用户获得 Insight。

G6 官网:https://g6.antv.vision/zh。欢迎关注。

GitHub:https://github.com/antvis/G6。欢迎 Star。

什么时候扎头发

大多数图数据在可视化时被展示成点-线图(Node-link Diagram)的形式。点-线图特别适用于如交通网络图一类的关系数据的展示,这种数据的节点通常带有地理位置信息,例如迁徙图、移民图、航线图等。

(左)图 1. 法国航线图。(右)图 2. 美国航线图。

(左)图 3. 世界网络 IXP 对等图。(右)图 4. 美国移民图。

虽然点-线图提供了直观的可视化,但是当数据存在大量节点和边时,视觉混乱(Visual Clutter)成为了严重的问题。点-线图中的视觉混乱通常是边过于交错复杂的直接结果。特别在如交通网络一类数据中,节点位置具有明确含义,其位置是不可以被修改的,如图 1~4 四个例子。因此,诸多研究者设计了各种通过优化边的方式减轻上述视觉混乱,其中“扎个头发”边绑定(Edge Bundling)方法被广泛研究和应用。现在,图可以有很多种“发型”,紧的松的、脏辫、鱼骨辫、防秃的(???)... 下面,我们将详细介绍被广泛使用的 FDEB(Force-Directed Edge Bundling) 方法,并概览学术中其他几种边绑定算法。最后,我们将介绍一种融合多种边绑定结果的算法。

力导向扎头发 FDEB

FDEB(Force-Directed Edge Bundling for Graph Visualization (2009))是最常见的、基于力导的边绑定方法。也是 D3.js 和 G6 中使用的边绑定方法。

算法原理

利用力导向的思想,把每根头发丝儿(边)使用 k 个控制点切割成 k-1 份,使直发变为有 k 个控制点的折线。控制点之间存在两种力:

  • 同一根头发上的相邻节点之间存在 Fs(spring force);
  • 不同头发上相对应的节点之间可能存在 Fe(electrostatic force)。

图 5. FDEB 边的切割及控制点上的力图解。

并不是所有的头发丝儿之间的控制点都存在 Fe。比如两根头发在脑壳儿上距离太远、长短差距太大等情况下,就不应该将它们强行绑在一起。

如下图四种情况:(a)当两条边之间的夹角接近 90 度时、(b)当两条边的长度差距过大时、(c)当两条边的中点太远时、(d)当两条边相互投影不到对方时,Fe 将不存在。根据这些条件,计算两条边的兼容性(compatibility),当兼容性达到用户指定的阈值(compatibility threshold)时,才会计算它们之间的 Fe。

image.png

图 6. 边的兼容性决定了两边的控制点之间是否存在 Fe。

效果

图 7. FDEB 论文中展示的结果。发型完成!

妈,扎的有点紧。可以通过控制参数调整松紧程度。

在 G6 中使用 FDEB

图可视化开源引擎 G6 将 FDEB 实现为一种插件,只需要在实例化图时配置边绑定插件即可:

// 实例化插件

const edgeBundling = new Bundling({

// ...

 // 边绑定算法的配置项

});

const graph = new G6.Graph({

plugins: [edgeBundling],// 加入插件实例

// ...                      // 其他图配置项

 });

// 执行边绑定

edgeBundling.bundling(data);

// 读取数据到图上

graph.data(data);

// 渲染

graph.render();

图 8. 美国航线图,节点代表城市,边代表航线。(左)使用 G6 渲染的未绑定的原图。(右)使用 G6 中的 FEDB 绑定后的结果。

除了简单使用边绑定插件外,利用 G6 提供到一系列配置方法,可以实现带交互的风格化可视化结果:

图 9. 使用 G6 优化美国航线图的视觉效果。边颜色映射飞行方向。节点饼图映射该城市飞入/飞出航线数量关系。

传送门:Demo 及完整代码」「G6 GitHub

其他发型 Look

MINGLE

Multilevel Agglomerative Edge Bundling for Visualizing Large Graphs (2011, PVIS)

「如何快速处理女盆友的大头浓密秀发」MINGLE 旨在用更少的“墨水”绘制复杂图的一种多层级边绑定方式。优点:速度快,可以处理大规模图。

缺点:线条略生硬、结果仍不够清晰。「妈,头发都打柳儿了。」

图 10. MINGLE 效果图。

KDEEB

Graph bundling by Kernel Density Estimation (2014)

「想看看女盆友脑壳儿上哪里头发密度比较大?」KDEEB 根据图布局预先计算密度(kernel density)进行绑定。优点:可以突出图的密度,满足一些美学原则。

图 11. KDEEB 效果图。

SBEB

Skeleton-based edge bundling for graph visualization (2014)

「想搞个鱼骨辫?」SBEB 可以根据预先计算的图布局骨架,将边绑定到骨架上。优点:可以清晰了解一幅图的骨架。

图 11. SBEB 效果图。

ADEB

Attribute-Driven Edge Bundling for General Graphs with Applications in Trail Analysis (2015)

「假如你女盆友的头发有塑料的、金属的、纤维的,想把它们分类绑在一块。emmmm,这女盆友到底是个啥?」ADEB 针对“路径”(Trail)分析的边绑定方法。可根据边的属性,将相似属性的边绑定在一起。例如:边方向、时间戳、权重等。

图 11. ADEB 效果图。

FFTEB

FFTEB: Edge Bundling of Huge Graphs by the Fast Fourier Transform (2017)

「早上上班快迟到了,女盆友头又比较大,女朋友头发又比较多,赶时间扎几撮吧」FFTEB 针对大规模图数据的快速绑定方法。允许根据边属性进行选择性快速绑定。

图 11. FFTEB 效果图。

交互式融合多种边绑定算法

上面介绍了女盆友的这么多发型,各有优劣,每种方法又可以调参,不知道该选哪个好了,无论选啥女盆友还是不满意怎么办?此时,我们希望把不同发型的局部拼合起来。简单掰掰手指,脑子里蹦出几个方案:

  • Plan A:单纯使用图片进行拼接。由于被绑定后边的路径的差异,图片接缝处的边一定是接不上的。
  • Plan B:由于在边绑定算法中,每条边一般是有 k 个控制点的折线。可以接缝处强行将同一条边的两个相邻切割点连接。这种方式会虽然解决了 Plan A 中边断开的问题,但连接处将会出现极不平滑的折点。如图 12(c)。
  • Plan C:使用线性插值的方式,在接缝附近一定范围内修改控制点位置使之平滑过度。如图 12(d)。这种方式虽然可以得到非常平滑的结果,但接缝附近两幅图的结构会被线性差值严重地破坏。如图 12(d)中圆圈中左侧原先被绑定的边变得松散,右侧原先未绑定的直线也改变了轨迹。

图 12. 将边绑定结果(a)中虚线框部分融合到(b)的相应位置上。红色圆圈高亮了局部细节。(c)直接将两幅图接缝处的边连接导致了锯齿状结果。其中红色到蓝色映射了从大到小的不平滑程度/曲率。(d)使用线性差值的方式得到平滑的结果,但两部分结构被破坏。(e)该论文但方法可以生成平滑且保持结果的拼接结果。(f)使用交互工具提升最终结果的可读性,如解决易造成歧义的点-边重合。

Interactive Structure-aware Blending of Diverse Edge Bundling Visualizations (IEEE InfoVis 2019) 一文提出了一种交互式编辑融合不同边绑定结果的方法。如图 12(c)所示,该方法不仅可以平滑拼合两幅图,还能够保证原结果的结构。最后,该方法还提供了交互式地修正技术,提升最终结果的局部可读性,见图 12 (f)。

下面例子展示了在一副图上拼合多种边绑定结果。从图 13 展示的多种边绑定结果中提取区域 2、3、4、5 拼接到原图 14 (a)上,最终得到图 14(b)的结果。

图 13. 「发型手册」多种算法生成的边绑定结果。

图 14. 拼接发型手册里的结果到原图(a)上得到(b)。

这种拼接方法还可以扩展到更加「任务驱动」的交互上,例如探索一条路径——绑定指定两部分端点之间的路径簇。用户在图 15(a)中使用两个紫色的虚线框选中了两部分端点,黄色的边为这两部分端点之间的所有路径,蓝色虚线部分为该路径附近辐射的区域。使用任意现有的边绑定算法得到图 15(b)的全图绑定结果,黑色框标注了该结果的歧义——被关注的路径与背景中一簇边绑定重合了。图 15(c)在融合该路径及背景的边绑定结果到原图上的同时,解决了黑色方框中标注的歧义,将两簇重合的边绑定分离。

图 15. 在未绑定的图上只绑定指定的路径,并消除局部歧义。

结束语

Tony 老师介绍了这么多狂拽酷炫的发型,要不要办个卡,给女盆友试试呢?没有女盆友?那,给自己扎也行。没 没有头发?打 打扰了 :)。

走前,Tony 老师跪求办卡!请关注「专业的开源图可视化引擎 G6」,做图可视化,我们是认真的。请期待 G6 带来的更多惊喜~

G6 官网:https://antv-g6.gitee.io/zh

欢迎关注。 GitHub:https://github.com/antvis/G6。欢迎 Star。

 

展开阅读全文
打赏
2
1 收藏
分享
加载中
更多评论
打赏
0 评论
1 收藏
2
分享
返回顶部
顶部