給圖上的邊“扎個頭髮”會怎樣？
引言—— 你看這錯綜複雜的圖像不像早上沒梳頭的女盆友？真想給她扎個美美的頭髮呀。首先，你得....。害，沒女友沒關係！先給圖可視化扎個頭吧！大規模圖往往具有復雜的數據關係。視覺混亂是可視化大規模圖的一大問題。研究者們提出了多種降低視覺混亂的方法。其中，邊綁定（紮頭發大法）是一種高效的、可減輕混亂、展現高層級的邊趨勢的方法。
本文中部分圖可視化由螞蟻金服AntV G6 提供支持。 G6 —— 專業的圖可視化引擎。讓關係數據變得簡單透明，讓用戶獲得Insight。
G6官網： https:// antv-g6.gitee.io/zh 。歡迎關注。
GitHub： https:// github.com/antvis/G6 。歡迎Star。
什麼時候紮頭發
大多數圖數據在可視化時被展示成點-線圖（Node-link Diagram）的形式。點-線圖特別適用於如交通網絡圖一類的關係數據的展示，這種數據的節點通常帶有地理位置訊息，例如遷徙圖、移民圖、航線圖等。
雖然點-線圖提供了直觀的可視化，但是當數據存在大量節點和邊時，視覺混亂（Visual Clutter）成為了嚴重的問題。點-線圖中的視覺混亂通常是邊過於交錯複雜的直接結果。特別在如交通網絡一類數據中，節點位置具有明確含義，其位置是不可以被修改的，如圖1～4 四個例子。因此，諸多研究者設計了各種通過優化邊的方式減輕上述視覺混亂，其中“扎個頭髮”邊綁定（Edge Bundling）方法被廣泛研究和應用。
現在，圖可以有很多種“髮型”，緊的鬆的、臟辮、魚骨辮、防禿的（？？？）... 下面，我們將詳細介紹被廣泛使用的FDEB（Force-Directed Edge Bundling） 方法，並概覽學術中其他幾種邊綁定算法。最後，我們將介紹一種融合多種邊綁定結果的算法。
力導向紮頭發FDEB
FDEB 是最常見的、基於力導的邊綁定方法。也是D3.js 和G6 中使用的邊綁定方法。
算法原理
利用力導向的思想，把每根頭髮絲兒（邊）使用k 個控制點切割成k-1 份，使直髮變為有k 個控制點的折線。控制點之間存在兩種力：
- 同一根頭髮上的相鄰節點之間存在Fs（spring force）；
- 不同頭髮上相對應的節點之間可能存在Fe（electrostatic force）。
並不是所有的頭髮絲兒之間的控制點都存在Fe。比如兩根頭髮在腦殼兒上距離太遠、長短差距太大等情況下，就不應該將它們強行綁在一起。
如下圖四種情況：（a）當兩條邊之間的夾角接近90 度時；（b）當兩條邊的長度差距過大時；（c）當兩條邊的中點太遠時；（d）當兩條邊相互投影不到對方時，Fe 將不存在。根據這些條件，計算兩條邊的兼容性（compatibility），當兼容性達到用戶指定的閾值（compatibility threshold）時，才會計算它們之間的Fe。
效果
媽，扎的有點緊。可以通過控制參數調整鬆緊程度。
在G6 中使用FDEB
圖可視化開源引擎G6將FDEB實現為一種插件，只需要在實例化圖時配置邊綁定插件即可：
// 实例化插件const edgeBundling = new Bundling({ // ... // 边绑定算法的配置项}); const graph = new G6.Graph({ plugins: [ edgeBundling ], // 加入插件实例// ... // 其他图配置项}); // 执行边绑定edgeBundling.bundling(data); // 读取数据到图上graph.data(data); // 渲染graph.render();
除了簡單使用邊綁定插件外，利用G6 提供到一系列配置方法，可以實現如圖9 展示的帶交互的風格化可視化結果。傳送門： 「 Demo及完整代碼」「 G6 GitHub 」
其他髮型Look
MINGLE
Multilevel Agglomerative Edge Bundling for Visualizing Large Graphs (2011, PVIS)
「如何快速處理女盆友的大頭（劃掉）濃密秀發」MINGLE 旨在用更少的“墨水”繪製複雜圖的一種多層級邊綁定方式。優點：速度快，可以處理大規模圖。
缺點：線條略生硬、結果仍不夠清晰。 「頭髮都打柳兒了。」
KDEEB
「想看看女盆友腦殼兒上哪裡頭髮密度比較大？」KDEEB 根據圖佈局預先計算密度（kernel density）進行綁定。優點：可以突出圖的密度，滿足一些美學原則。
SBEB
「想搞個魚骨辮？」SBEB 可以根據預先計算的圖佈局骨架，將邊綁定到骨架上。優點：可以清晰了解一幅圖的骨架。
ADEB
Attribute-Driven Edge Bundling for General Graphs with Applications in Trail Analysis (2015)
「假如你女盆友的頭髮有塑料的、金屬的、纖維的，想把它們分類綁在一塊。emmmm，這女盆友到底是個啥？」ADEB 針對“路徑”（Trail）分析的邊綁定方法。可根據邊的屬性，將相似屬性的邊綁定在一起。例如：邊方向、時間戳、權重等。
FFTEB
FFTEB: Edge Bundling of Huge Graphs by the Fast Fourier Transform (2017)
「早上上班快遲到了，女盆友頭又比較大（劃掉），女盆友頭髮又比較多，趕時間扎幾撮吧」FFTEB 針對大規模圖數據的快速綁定方法。允許根據邊屬性進行選擇性快速綁定。
「混搭髮型」交互式融合多種邊綁定算法
上面介紹了女盆友的這麼多髮型，各有優劣，每種方法又可以調參，不知道該選哪個好了，無論選啥女盆友還是不滿意怎麼辦？此時，我們希望把不同髮型的局部拼合起來。簡單掰掰手指，腦子裡蹦出幾個方案：
- Plan A：單純使用圖片進行拼接。由於被綁定後邊的路徑的差異，圖片接縫處的邊一定是接不上的。
- Plan B：由於在邊綁定算法中，每條邊一般是有k個控制點的折線。可以接縫處強行將同一條邊的兩個相鄰切割點連接。這種方式會雖然解決了Plan A 中邊斷開的問題，但連接處將會出現極不平滑的折點。如圖12（c）。
- Plan C：使用線性插值的方式，在接縫附近一定範圍內修改控制點位置使之平滑過度。如圖12（d）。這種方式雖然可以得到非常平滑的結果，但接縫附近兩幅圖的結構會被線性差值嚴重地破壞。如圖12（d）中圓圈中左側原先被綁定的邊變得鬆散，右側原先未綁定的直線也改變了軌跡。
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）的結果。
這種拼接方法還可以擴展到更加「任務驅動」的交互上，例如探索一條路徑——綁定指定兩部分端點之間的路徑簇。用戶在圖15（a）中使用兩個紫色的虛線框選中了兩部分端點，黃色的邊為這兩部分端點之間的所有路徑，藍色虛線部分為該路徑附近輻射的區域。使用任意現有的邊綁定算法得到圖15（b）的全圖綁定結果，黑色框標註了該結果的歧義——被關注的路徑與背景中一簇邊綁定重合了。圖15（c）在融合該路徑及背景的邊綁定結果到原圖上的同時，解決了黑色方框中標註的歧義，將兩簇重合的邊綁定分離。
結束語
Tony 老師介紹了這麼多狂拽酷炫的髮型，要不要辦個卡，給女盆友試試呢？沒有女盆友？那，給自己扎也行。沒沒有頭髮？打打擾了:)。
走前，Tony 老師跪求辦卡！請關注「 專業的開源圖可視化引擎G6 」，做圖可視化，我們是認真的。請期待G6 帶來的更多驚喜～
G6官網： https:// antv-g6.gitee.io/zh 。歡迎關注。
GitHub： https:// github.com/antvis/G6 。歡迎Star。
