請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/88240
標題: | 隨機遊走方法應用在基於事件之動態圖繪製 Event-based Dynamic Graph Drawing via Random Walk Sampling |
作者: | 黃翊哲 I-Che Huang |
指導教授: | 顏嗣鈞 Hsu-Chun Yen |
關鍵字: | 圖採樣,動態圖繪製,多階層力導向佈局演算法,基於事件之資料集, Graph sampling,Dynamic graph drawing,Event-based data,Multilevel force-directed algorithm, |
出版年 : | 2023 |
學位: | 碩士 |
摘要: | 資料視覺化在現實世界中的重要性與日俱增,而圖形繪製在描述各種元素之間的連接方面起著至關重要的作用。雖然靜態圖的視覺化已經得到廣泛研究,可以有效率地繪製高品質圖形佈局,但對於動態圖的需求仍不斷增長,如社群媒體、串流服務的資料分析等,尚待進一步的探索。時間是視覺化動態圖的一個重要因素,一般大都將資料切割成不同時間片段來繪製圖形。然而,並非所有的複雜網路都能在時間切片內得到良好定義。基於事件的動態圖繪製通過捕捉圖形中發生的事件序列,從事件的角度產生圖形佈局。但是在面對大型的複雜網路時,基於事件的圖形繪製演算法仍面臨耗時過長的挑戰。為了解決上述問題,在這篇論文中,我們採用了一種基於隨機遊走的方法來繪製基於事件的動態圖。我們利用隨機遊走方法產生圖採樣來增加輸入資料集的擴展性,並加入了多階層方法來大幅加速繪製圖形佈局所需的時間。此外,我們引入了一種新的指標來評估我們的方法。實驗結果顯示,我們的方法在繪製時間和其他多個指標方面優於原始演算法,並且成功地用圖採樣方法捕捉了圖形結構。 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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/88240 |
DOI: | 10.6342/NTU202301808 |
全文授權: | 未授權 |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-111-2.pdf 目前未授權公開取用 | 5.01 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。