頻譜稀疏化在線上動態作圖問題的應用

Applying Spectral Sparsification to Online Dynamic Graph Drawing

何帝儀(Ti-Yi Ho)

指導教授 ： 顏嗣鈞

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2021年)

https://doi.org/10.6342/NTU202102291

摘要

這篇論文提出一個方法，可以將圖的頻譜稀疏化應用在線上動態圖的作圖問題，並在現有的演算法上做一些改善，並給出一個實例，這個方法側重在降低時間複雜度，同時它保有力導向布局算法繪圖的美感，且維持了用戶的思維導圖。
這個方法主要針對力的計算時間作優化，眾所皆知，力的計算在此類演算法往往是最花時間的一部份。在計算排斥力上，天文界的N體模擬，包括Barnes–Hut模擬和快速多極方法等，已經很好的被應用先前的許多研究上。但在計算吸引力上就缺乏廣泛的討論。在對於大的靜態圖，有研究使用頻譜稀疏化作抽樣，再用抽樣後的結果作圖的方法，但很少看到延伸到動態圖上的做法，這篇論文給出了一個方案，可以將頻譜稀疏化應用在線上動態圖的布局上。
除此之外，這個方法基於力的模型作改良，可以套用在絕大多數的力導向布局算法，在這裡我們只實作了一個，並比較有稀疏化跟沒有稀疏化的差別。
在實驗的過程中，我們挑選了一些指標，用以衡量三個方面上的表現：圖形是否具有美學布局，是否保留了用戶的思維導圖，以及布局是否可以即時生成。

關鍵字

線上動態圖 ； 頻譜稀疏化 ； 力導向布局算法

並列摘要

This thesis proposes a method of applying spectral sparsification to online dynamic graph drawing problems, and gives an example based on the existing pinning algorithm with some enhancements.
Our approach focuses on reducing time complexity while maintaining the aesthetic layout and the user’s mental map.
The force calculation step is considered to be the most time-consuming part in the force-directed based algorithms. For repulsive force, n-body simulation techniques, such as Fast Multipole Method or Barnes–Hut simulation, have been well implemented in previous work. But for attractive forces, there is not so much discussion. Only a few works on large static graphs have some discussion about sparsifiers. This thesis attempts to give an implementation of spectral sparsification on dynamic graphs to deal with it.
In addition, this method is based on the force-directed algorithm, so it is suitable for most force-directed based dynamic graph drawing algorithms. Here we only implement one and compare the results whether to use the sparsification method.
In the experiment, we select several metrics to measure the performance of three aspects. They are whether the graph has an aesthetic layout, whether the user's mental map is preserved, and whether the layout can be generated in real time.

並列關鍵字

Online dynamic graph ； Spectral sparsification ； Force-directed layout

參考文獻

Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Spectral sparsification in dynamic graph streams. InApproximation, Randomization,and Combinatorial Optimization. Algorithms and Techniques, pages 1–10. Springer, 2013.

Fabian Beck, Michael Burch, Stephan Diehl, and Daniel Weiskopf. Ataxonomy and survey of dynamic graph visualization.Computer Graphics Forum, 01 2016.

Tarik Crnovrsanin, Jacqueline Chu, and Kwan-Liu Ma. An incrementallayout method for visualizing online dynamic graphs. InInternationalSymposium on Graph Drawing, pages 16–29. Springer, 2015.

Aritra Dasgupta, Dustin L Arendt, Lyndsey R Franklin, Pak ChungWong, and Kristin A Cook. Human factors in streaming data analysis:Challenges and opportunities for information visualization. InComputerGraphics Forum, volume 37, pages 254–272. Wiley Online Library, 2018.

Peter Eades, Quan Nguyen, and Seok-Hee Hong. Drawing big graphs using spectral sparsification. InInternational Symposium on Graph Drawing and Network Visualization, pages 272–286. Springer, 2017.