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