CASEB：基於社群感知骨架之結構保留式邊綑綁

Abstract

邊綑綁是降低高密度節點連結圖中視覺雜亂的常用技術。然而，許多傳統方法將邊綑綁視為圖形佈局完成後的後處理步驟，可能造成路徑扭曲、視覺歧義，並削弱原始結構的可讀性。近年的 Bundling-Aware Graph Drawing 方法透過 Filter-Draw-Bundle 框架，將骨架選取、圖形佈局與邊綑綁共同納入考量，以改善此限制。然而，既有方法多著重於一般邊綑綁品質，對於最終結果中的社群結構保留則鮮少被明確探討。 本論文提出 CASEB，一種用於結構保留的社群感知骨架式邊綑綁方法。CASEB 以 Filter-Draw-Bundle 架構為基礎，將社群資訊納入骨架建構與佈局最佳化。首先，本研究使用 Metric Backbone 去除冗餘邊，同時保留基礎距離結構。接著，CASEB 結合 Neighboring Edge Betweenness、局部 Jaccard 相似度與社群權重，形成骨架建構的優先級分數。此外，本研究引入自適應伸縮因子與抗塌陷佈局策略，以降低社群重疊並改善高密度群集的視覺分離效果。 本研究於隨機區塊模型圖、真實圖資料與 scale-free networks 上進行實驗，並以 Ink Ratio、Distortion、Ambiguity 與 Entropy 四項指標，將 CASEB 與 EPB、EB-FDB、NEB-FDB 及 SW-FDB 進行比較。結果顯示，在代表性設定下，CASEB 具有較佳的整體表現。特別是，CASEB 能在維持優異的邊綑綁品質之餘，進一步提升社群結構的保留程度，顯示將社群資訊納入骨架選取與佈局設計，有助於提升邊綑綁圖形的結構可讀性。

Edge bundling is widely used to reduce visual clutter in dense node-link diagrams. However, many traditional methods treat bundling as a post-processing step after graph layout, which may introduce path distortion, visual ambiguity, and reduced structural readability. Recent Bundling-Aware Graph Drawing methods address this limitation through the Filter-Draw-Bundle framework, which jointly considers skeleton selection, layout, and edge bundling. Nevertheless, existing methods mainly focus on general bundling quality, while community-structure preservation is less explicitly considered. This thesis proposes CASEB, a community-aware skeleton-based edge bundling method for structure preservation. CASEB extends the Filter-Draw-Bundle pipeline by incorporating community information into skeleton construction and layout optimization. It first uses Metric Backbone to remove redundant edges while preserving basic distance structures. It then combines Neighboring Edge Betweenness, local Jaccard similarity, and community weighting into a priority score for skeleton construction. In addition, an adaptive stretch factor and an anti-collapse layout strategy are introduced to reduce community overlap and improve visual separation among densely connected groups. Experiments on stochastic block model graphs, real-world graphs, and scale-free networks compare CASEB with EPB, EB-FDB, NEB-FDB, and SW-FDB using Ink Ratio, Distortion, Ambiguity, and Entropy. The results show that CASEB achieves better overall performance under the representative setting. In particular, CASEB improves community preservation while maintaining competitive bundling quality, indicating that community-aware skeleton selection and layout design can enhance the structural readability of bundled graph drawings.