引言 —— 你看這錯(cuò)綜復(fù)雜的圖像不像早上沒梳頭的女盆友？真想給她扎個(gè)美美的頭發(fā)呀潜必。首先靴姿，你得....。害磁滚，沒女友沒關(guān)系佛吓！先給圖可視化扎個(gè)頭吧！大規(guī)模圖往往具有復(fù)雜的數(shù)據(jù)關(guān)系垂攘。視覺混亂是可視化大規(guī)模圖的一大問題维雇。研究者們提出了多種降低視覺混亂的方法。其中晒他，邊綁定（扎頭發(fā)大法）是一種高效的吱型、可減輕混亂、展現(xiàn)高層級的邊趨勢的方法陨仅。

本文中部分圖可視化由 G6 提供支持津滞。G6 —— 專業(yè)的圖可視化引擎。讓關(guān)系數(shù)據(jù)變得簡單透明灼伤，讓用戶獲得 Insight触徐。

G6 官網(wǎng)：https://g6.antv.vision/zh。歡迎關(guān)注狐赡。

GitHub：https://github.com/antvis/G6撞鹉。歡迎 Star。

什么時(shí)候扎頭發(fā)

大多數(shù)圖數(shù)據(jù)在可視化時(shí)被展示成點(diǎn)-線圖（Node-link Diagram）的形式。點(diǎn)-線圖特別適用于如交通網(wǎng)絡(luò)圖一類的關(guān)系數(shù)據(jù)的展示孔祸，這種數(shù)據(jù)的節(jié)點(diǎn)通常帶有地理位置信息隆敢，例如遷徙圖、移民圖崔慧、航線圖等拂蝎。

（左）圖 1. 法國航線圖皇钞。（右）圖 2. 美國航線圖悼泌。

（左）圖 3. 世界網(wǎng)絡(luò) IXP 對等圖。（右）圖 4. 美國移民圖夹界。

雖然點(diǎn)-線圖提供了直觀的可視化馆里，但是當(dāng)數(shù)據(jù)存在大量節(jié)點(diǎn)和邊時(shí)，視覺混亂（Visual Clutter）成為了嚴(yán)重的問題可柿。點(diǎn)-線圖中的視覺混亂通常是邊過于交錯(cuò)復(fù)雜的直接結(jié)果鸠踪。特別在如交通網(wǎng)絡(luò)一類數(shù)據(jù)中营密，節(jié)點(diǎn)位置具有明確含義，其位置是不可以被修改的目锭，如圖 1～4 四個(gè)例子评汰。因此，諸多研究者設(shè)計(jì)了各種通過優(yōu)化邊的方式減輕上述視覺混亂奖唯，其中“扎個(gè)頭發(fā)”邊綁定（Edge Bundling）方法被廣泛研究和應(yīng)用”嗾瘢現(xiàn)在，圖可以有很多種“發(fā)型”臭埋，緊的松的、臟辮臀玄、魚骨辮瓢阴、防禿的（？健无？荣恐？）... 下面，我們將詳細(xì)介紹被廣泛使用的 FDEB（Force-Directed Edge Bundling） 方法，并概覽學(xué)術(shù)中其他幾種邊綁定算法叠穆。最后少漆，我們將介紹一種融合多種邊綁定結(jié)果的算法。

力導(dǎo)向扎頭發(fā) FDEB

FDEB（Force-Directed Edge Bundling for Graph Visualization (2009)）是最常見的硼被、基于力導(dǎo)的邊綁定方法示损。也是 D3.js 和 G6 中使用的邊綁定方法。

算法原理

利用力導(dǎo)向的思想嚷硫，把每根頭發(fā)絲兒（邊）使用 k 個(gè)控制點(diǎn)切割成 k-1 份检访，使直發(fā)變?yōu)橛?k 個(gè)控制點(diǎn)的折線∽械В控制點(diǎn)之間存在兩種力：

同一根頭發(fā)上的相鄰節(jié)點(diǎn)之間存在 Fs（spring force）脆贵；

不同頭發(fā)上相對應(yīng)的節(jié)點(diǎn)之間可能存在 Fe（electrostatic force）。

圖 5. FDEB 邊的切割及控制點(diǎn)上的力圖解起暮。

并不是所有的頭發(fā)絲兒之間的控制點(diǎn)都存在Fe卖氨。比如兩根頭發(fā)在腦殼兒上距離太遠(yuǎn)、長短差距太大等情況下负懦，就不應(yīng)該將它們強(qiáng)行綁在一起筒捺。

如下圖四種情況：（a）當(dāng)兩條邊之間的夾角接近 90 度時(shí)、（b）當(dāng)兩條邊的長度差距過大時(shí)密似、（c）當(dāng)兩條邊的中點(diǎn)太遠(yuǎn)時(shí)焙矛、（d）當(dāng)兩條邊相互投影不到對方時(shí)，F(xiàn)e 將不存在残腌。根據(jù)這些條件村斟，計(jì)算兩條邊的兼容性（compatibility），當(dāng)兼容性達(dá)到用戶指定的閾值（compatibility threshold）時(shí)抛猫，才會計(jì)算它們之間的 Fe蟆盹。

圖 6. 邊的兼容性決定了兩邊的控制點(diǎn)之間是否存在 Fe。

效果

圖 7. FDEB 論文中展示的結(jié)果闺金。發(fā)型完成逾滥！

?媽，扎的有點(diǎn)緊败匹≌迹可以通過控制參數(shù)調(diào)整松緊程度。

在 G6 中使用 FDEB

圖可視化開源引擎 G6?將 FDEB 實(shí)現(xiàn)為一種插件掀亩，只需要在實(shí)例化圖時(shí)配置邊綁定插件即可：

// 實(shí)例化插件

const edgeBundling = new Bundling({

// ...

?// 邊綁定算法的配置項(xiàng)

});

const graph = new G6.Graph({

plugins: [edgeBundling],// 加入插件實(shí)例

// ...? ? ? ? ? ? ? ? ? ? ? // 其他圖配置項(xiàng)

?});

// 執(zhí)行邊綁定

edgeBundling.bundling(data);

// 讀取數(shù)據(jù)到圖上

graph.data(data);

// 渲染

graph.render();

圖 8. 美國航線圖舔哪，節(jié)點(diǎn)代表城市，邊代表航線槽棍。（左）使用 G6 渲染的未綁定的原圖捉蚤。（右）使用 G6 中的 FEDB 綁定后的結(jié)果抬驴。

除了簡單使用邊綁定插件外，利用 G6 提供到一系列配置方法缆巧，可以實(shí)現(xiàn)帶交互的風(fēng)格化可視化結(jié)果：

傳送門：「Demo 及完整代碼」「G6 GitHub」

圖 9. 使用 G6 優(yōu)化美國航線圖的視覺效果布持。邊顏色映射飛行方向。節(jié)點(diǎn)餅圖映射該城市飛入/飛出航線數(shù)量關(guān)系陕悬。

其他發(fā)型 Look

MINGLE

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

「如何快速處理女盆友的大頭濃密秀發(fā)」MINGLE 旨在用更少的“墨水”繪制復(fù)雜圖的一種多層級邊綁定方式题暖。優(yōu)點(diǎn)：速度快，可以處理大規(guī)模圖墩莫。

缺點(diǎn)：線條略生硬芙委、結(jié)果仍不夠清晰】袂兀「頭發(fā)都打柳兒了灌侣。」

圖 10. MINGLE 效果圖裂问。

KDEEB

Graph bundling by Kernel Density Estimation(2014)

「想看看女盆友腦殼兒上哪里頭發(fā)密度比較大侧啼？」KDEEB?根據(jù)圖布局預(yù)先計(jì)算密度（kernel density）進(jìn)行綁定。優(yōu)點(diǎn)：可以突出圖的密度堪簿，滿足一些美學(xué)原則痊乾。

圖 11. KDEEB 效果圖。

SBEB

Skeleton-based edge bundling for graph visualization(2014)

「想搞個(gè)魚骨辮椭更？」SBEB 可以根據(jù)預(yù)先計(jì)算的圖布局骨架哪审，將邊綁定到骨架上。優(yōu)點(diǎn)：可以清晰了解一幅圖的骨架虑瀑。

圖 11. SBEB 效果圖湿滓。

ADEB

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

「假如你女盆友的頭發(fā)有塑料的、金屬的舌狗、纖維的叽奥，想把它們分類綁在一塊。emmmm痛侍，這女盆友到底是個(gè)啥朝氓？」ADEB 針對“路徑”（Trail）分析的邊綁定方法≈鹘欤可根據(jù)邊的屬性赵哲，將相似屬性的邊綁定在一起。例如：邊方向君丁、時(shí)間戳枫夺、權(quán)重等。

圖 11. ADEB 效果圖谈截。

FFTEB

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

「早上上班快遲到了，女盆友頭又比較大，女盆友頭發(fā)又比較多簸喂，趕時(shí)間扎幾撮吧」FFTEB 針對大規(guī)模圖數(shù)據(jù)的快速綁定方法毙死。允許根據(jù)邊屬性進(jìn)行選擇性快速綁定。

圖 11. FFTEB 效果圖喻鳄。

「混搭發(fā)型」交互式融合多種邊綁定算法

上面介紹了女盆友的這么多發(fā)型扼倘，各有優(yōu)劣，每種方法又可以調(diào)參除呵，不知道該選哪個(gè)好了再菊，無論選啥女盆友還是不滿意怎么辦？此時(shí)颜曾，我們希望把不同發(fā)型的局部拼合起來纠拔。簡單掰掰手指，腦子里蹦出幾個(gè)方案：

Plan A：單純使用圖片進(jìn)行拼接泛豪。由于被綁定后邊的路徑的差異稠诲，圖片接縫處的邊一定是接不上的。

Plan B：由于在邊綁定算法中诡曙，每條邊一般是有 k 個(gè)控制點(diǎn)的折線臀叙。可以接縫處強(qiáng)行將同一條邊的兩個(gè)相鄰切割點(diǎn)連接价卤。這種方式會雖然解決了 Plan A 中邊斷開的問題劝萤，但連接處將會出現(xiàn)極不平滑的折點(diǎn)。如圖 12（c）慎璧。

Plan C：使用線性插值的方式床嫌，在接縫附近一定范圍內(nèi)修改控制點(diǎn)位置使之平滑過度。如圖 12（d）炸卑。這種方式雖然可以得到非常平滑的結(jié)果既鞠，但接縫附近兩幅圖的結(jié)構(gòu)會被線性差值嚴(yán)重地破壞。如圖 12（d）中圓圈中左側(cè)原先被綁定的邊變得松散盖文，右側(cè)原先未綁定的直線也改變了軌跡嘱蛋。

圖 12. 將邊綁定結(jié)果（a）中虛線框部分融合到（b）的相應(yīng)位置上。紅色圓圈高亮了局部細(xì)節(jié)五续。（c）直接將兩幅圖接縫處的邊連接導(dǎo)致了鋸齒狀結(jié)果洒敏。其中紅色到藍(lán)色映射了從大到小的不平滑程度/曲率。（d）使用線性差值的方式得到平滑的結(jié)果疙驾，但兩部分結(jié)構(gòu)被破壞凶伙。（e）該論文但方法可以生成平滑且保持結(jié)果的拼接結(jié)果。（f）使用交互工具提升最終結(jié)果的可讀性它碎，如解決易造成歧義的點(diǎn)-邊重合函荣。

Interactive Structure-aware Blending of Diverse Edge Bundling Visualizations (IEEE InfoVis 2019) 一文提出了一種交互式編輯融合不同邊綁定結(jié)果的方法显押。如圖 12（c）所示，該方法不僅可以平滑拼合兩幅圖傻挂，還能夠保證原結(jié)果的結(jié)構(gòu)乘碑。最后，該方法還提供了交互式地修正技術(shù)金拒，提升最終結(jié)果的局部可讀性兽肤，見圖 12 （f）。

下面例子展示了在一副圖上拼合多種邊綁定結(jié)果绪抛。從圖 13 展示的多種邊綁定結(jié)果中提取區(qū)域 2资铡、3、4幢码、5 拼接到原圖 14 （a）上笤休，最終得到圖 14（b）的結(jié)果。

圖 13. 「發(fā)型手冊」多種算法生成的邊綁定結(jié)果蛤育。

圖 14. 拼接發(fā)型手冊里的結(jié)果到原圖（a）上得到（b）宛官。

這種拼接方法還可以擴(kuò)展到更加「任務(wù)驅(qū)動(dòng)」的交互上，例如探索一條路徑——綁定指定兩部分端點(diǎn)之間的路徑簇瓦糕。用戶在圖 15（a）中使用兩個(gè)紫色的虛線框選中了兩部分端點(diǎn)底洗，黃色的邊為這兩部分端點(diǎn)之間的所有路徑，藍(lán)色虛線部分為該路徑附近輻射的區(qū)域咕娄。使用任意現(xiàn)有的邊綁定算法得到圖 15（b）的全圖綁定結(jié)果亥揖，黑色框標(biāo)注了該結(jié)果的歧義——被關(guān)注的路徑與背景中一簇邊綁定重合了。圖 15（c）在融合該路徑及背景的邊綁定結(jié)果到原圖上的同時(shí)圣勒，解決了黑色方框中標(biāo)注的歧義费变，將兩簇重合的邊綁定分離。

圖 15. 在未綁定的圖上只綁定指定的路徑圣贸，并消除局部歧義挚歧。

結(jié)束語

Tony 老師介紹了這么多狂拽酷炫的發(fā)型，要不要辦個(gè)卡吁峻，給女盆友試試呢滑负？沒有女盆友？那用含，給自己扎也行矮慕。沒 沒有頭發(fā)？打 打擾了 :)啄骇。

走前痴鳄，Tony 老師跪求辦卡！請關(guān)注「專業(yè)的開源圖可視化引擎 G6」缸夹，做圖可視化痪寻，我們是認(rèn)真的螺句。請期待 G6 帶來的更多驚喜～

G6 官網(wǎng)：https://antv-g6.gitee.io/zh。歡迎關(guān)注橡类。

GitHub：https://github.com/antvis/G6壹蔓。歡迎 Star。