基於快速傅立葉轉換之核密度估計動態圖束邊演算法

Abstract

束邊演算法是一種資料視覺化的技術，讓圖可以在不失去結構性意義的前提下增加圖的可讀性。束邊演算法作用的對象是由點與邊組成的網絡圖，且他達到上述所提到的目標的方法在於將圖上雜亂且無序的邊集合形成一個視覺上綑綁起來的邊束。 這篇論文提出了一個作用於動態圖上的束邊演算法，作用於動態圖與靜態圖本質上的區別在於動態圖在不同時間點的圖之間可能會差異過大，這導致作用後的結果可能會導致觀看者的疑惑或是矛盾。我們所提出的方法是基於更早提出的“核密度估計束邊演算法”，這個方法主要是在計算圖上邊的密度分佈，我們的方法則利用快速傅立葉轉換這個理論上消耗較少時間的演算法來取代它。 在測量階段，我們利用幾個標準去衡量我們與前面方法的品質差異，其中一個是我們從一個 dynamic layout 的衡量改編而來，測量的重點在於保留心智地圖(mental map)的程度與圖形變形程度和減少亂邊的轉換效率。

Edge bundling is a visualization technique used to enhance the readability of node-link diagrams by grouping together edges that are visually close to each other while preserving the underlying structure of the graph. This technique is particularly useful for reducing visual clutter in complex graphs.

In this thesis, we present an algorithm for edge bundling in dynamic graphs. Unlike static graphs, dynamic graphs can undergo significant changes over different timestamps, which introduces additional challenges in maintaining the integrity of the bundled edges. Our method builds upon previous work that employed Kernel Density Estimation (KDE) to calculate the density distribution of edges in graphs. To improve the efficiency of KDE, we leverage Fast Fourier Transform (FFT) and modify the existing approach to achieve better results.

To evaluate the effectiveness of our method, we employ various metrics that assess the quality of the bundled graphs compared to the previous approach. In a novel metric proposed in this work, we focus on preserving the mental map of the graph while considering the trade-off between clutter reduction and distortion.