引言 —— 你看這錯綜復(fù)雜的圖像不像早上沒梳頭的女盆友？真想給她扎個美美的頭發(fā)呀。首先，你得....。害，沒女友沒關(guān)系！先給圖可視化扎個頭吧！大規(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。

什么時候扎頭發(fā)

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

（左）圖 1. 法國航線圖。（右）圖 2. 美國航線圖。

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

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

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

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

算法原理

利用力導(dǎo)向的思想，把每根頭發(fā)絲兒（邊）使用 k 個控制點切割成 k-1 份，使直發(fā)變?yōu)橛?k 個控制點的折線?？刂泣c之間存在兩種力：

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

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

圖 5. FDEB 邊的切割及控制點上的力圖解。

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

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

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

效果

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

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

在 G6 中使用 FDEB

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

// 實例化插件

const edgeBundling = new Bundling({

// ...

?// 邊綁定算法的配置項

});

const graph = new G6.Graph({

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

// ...? ? ? ? ? ? ? ? ? ? ? // 其他圖配置項

?});

// 執(zhí)行邊綁定

edgeBundling.bundling(data);

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

graph.data(data);

// 渲染

graph.render();

圖 8. 美國航線圖，節(jié)點代表城市，邊代表航線。（左）使用 G6 渲染的未綁定的原圖。（右）使用 G6 中的 FEDB 綁定后的結(jié)果。

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

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

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

其他發(fā)型 Look

MINGLE

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

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

缺點：線條略生硬、結(jié)果仍不夠清晰?！割^發(fā)都打柳兒了?！?/p>

圖 10. MINGLE 效果圖。

KDEEB

Graph bundling by Kernel Density Estimation(2014)

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

圖 11. KDEEB 效果圖。

SBEB

Skeleton-based edge bundling for graph visualization(2014)

「想搞個魚骨辮？」SBEB 可以根據(jù)預(yù)先計算的圖布局骨架，將邊綁定到骨架上。優(yōu)點：可以清晰了解一幅圖的骨架。

圖 11. SBEB 效果圖。

ADEB

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

「假如你女盆友的頭發(fā)有塑料的、金屬的、纖維的，想把它們分類綁在一塊。emmmm，這女盆友到底是個啥？」ADEB 針對“路徑”（Trail）分析的邊綁定方法。可根據(jù)邊的屬性，將相似屬性的邊綁定在一起。例如：邊方向、時間戳、權(quán)重等。

圖 11. ADEB 效果圖。

FFTEB

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

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

圖 11. FFTEB 效果圖。

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

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

Plan A：單純使用圖片進行拼接。由于被綁定后邊的路徑的差異，圖片接縫處的邊一定是接不上的。

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

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

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

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）。

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

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

結(jié)束語

Tony 老師介紹了這么多狂拽酷炫的發(fā)型，要不要辦個卡，給女盆友試試呢？沒有女盆友？那，給自己扎也行。沒 沒有頭發(fā)？打 打擾了 :)。

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

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

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