- 學位論文
隨機遊走方法應用在基於事件之動態圖繪製
Event-based Dynamic Graph Drawing via Random Walk Sampling
若您是本文的作者，可授權文章由華藝線上圖書館中協助推廣。
摘要
資料視覺化在現實世界中的重要性與日俱增，而圖形繪製在描述各種元素之間的連接方面起著至關重要的作用。雖然靜態圖的視覺化已經得到廣泛研究，可以有效率地繪製高品質圖形佈局，但對於動態圖的需求仍不斷增長，如社群媒體、串流服務的資料分析等，尚待進一步的探索。時間是視覺化動態圖的一個重要因素，一般大都將資料切割成不同時間片段來繪製圖形。然而，並非所有的複雜網路都能在時間切片內得到良好定義。基於事件的動態圖繪製通過捕捉圖形中發生的事件序列，從事件的角度產生圖形佈局。但是在面對大型的複雜網路時，基於事件的圖形繪製演算法仍面臨耗時過長的挑戰。為了解決上述問題，在這篇論文中，我們採用了一種基於隨機遊走的方法來繪製基於事件的動態圖。我們利用隨機遊走方法產生圖採樣來增加輸入資料集的擴展性，並加入了多階層方法來大幅加速繪製圖形佈局所需的時間。此外，我們引入了一種新的指標來評估我們的方法。實驗結果顯示，我們的方法在繪製時間和其他多個指標方面優於原始演算法，並且成功地用圖採樣方法捕捉了圖形結構。
並列摘要
The significance of data visualization is increasing in the real world, and graph drawing plays a crucial role in depicting connections among various elements. While static graph visualization has been extensively studied and is efficient in creating quality graph layouts, the growing demand for analyzing real-time and streaming data requires further investigation. Time is an important factor in visualizing dynamic graphs, and the technique of dividing data into time slices is commonly employed in drawing dynamic graphs. Nevertheless, not all complex networks can be well-defined in fixed intervals. An event-based model for dynamic graphs has been proposed to solve the above problem. By capturing the sequence of events that result in modifications in the graph, this approach produces graph layouts from event-based perspective. However, large and complex graphs still pose a challenge to event-based graph drawing for consuming too much time to create graph layouts. To tackle this problem, we apply a random walk-based approach for drawing event-based dynamic graphs. We utilize the random walk graph sampling method along with a multi-level framework to the event-based dynamic graph drawing algorithm to improve the scalability of input dataset and reduce the time complexity when computing the graph layout. Besides, we introduce a new quality metric for event-based dynamic graph drawing. In the experiment results, our approach outperforms the original algorithm in drawing time and several other metrics, and successfully captures the graph structure with the sampling method.
參考文獻
[1] D. Archambault, H. Purchase, and B. Pinaud, “Animation, small multiples, and the effect of mental map preservation in dynamic graphs,” IEEE transactions on visualization and computer graphics, vol. 17, no. 4, pp. 539–552, 2010.
[2] D. Archambault and H. C. Purchase, “Can animation support the visualisation of dynamic graphs?” Information Sciences, vol. 330, pp. 495–509, 2016.
[3] P. Simonetto, D. Archambault, and S. Kobourov, “Event-based dynamic graph visualisation,” IEEE Transactions on Visualization and Computer Graphics, vol. 26, no. 7, pp. 2373–2386, 2018.
[4] T. M. Fruchterman and E. M. Reingold, “Graph drawing by force-directed placement,” Software: Practice and experience, vol. 21, no. 11, pp. 1129–1164, 1991.
[5] D. Rafiei, “Effectively visualizing large networks through sampling,” in VIS5. IEEE Visualization, 2005. IEEE, 2005, pp. 375–382.