本文關鍵詞：大規(guī)模網絡布局壓縮算法及加速研究

  更多相關文章： 力導引布局算法 關節(jié)點 介數中心性 k-核 GPU

【摘要】：復雜網絡可視化是復雜網絡研究中的重要手段。隨著Web2.0時代和大數據時代的來臨,作為研究對象的復雜網絡的規(guī)模越來越大,人們也越來越需要對規(guī)模龐大的數據進行準確地表達和理解,并從中進一步探索和挖掘有效信息。采用傳統(tǒng)的數據表達方式已經不再能夠滿足人們的需求。因此,將復雜網絡數據進行可視化成為了人們理解和研究復雜網絡數據的一個主要方式。然而伴隨著復雜網絡數據的海量式增長,對復雜網絡可視化布局算法的布局效果和運算速度都提出了新的挑戰(zhàn)。在可視化布局算法中,力導引布局算法由于其布局結果的美觀性等原因得到了最為廣泛的應用。因而,本文基于力導引布局算法,從優(yōu)化布局效果和提高算法效率兩方面同時對大規(guī)模網絡數據的布局算法進行了改進和實現。在優(yōu)化布局效果方面,分別利用復雜網絡中的關節(jié)點,介數中心性和k-核的概念,提出了三種不同的網絡數據壓縮方式。將網絡節(jié)點劃分為不同類別,并根據節(jié)點所屬類別進一步對其進行聚集合并,實現大規(guī)模網絡數據的壓縮布局顯示,從整體上清晰地顯示網絡宏觀結構。在提高算法效率方面,針對壓縮后的網絡數據,對力導引算法需要的斥力計算、引力計算和更新坐標三個部分均實現了基于GPU的并行計算,大大縮短了算法的運行時間,從而使人們在可接受時間內獲得大規(guī)模網絡數據的可視化布局結果。最后,給出相應算法的實驗布局結果,并提出了面向壓縮布局的復雜網絡信息量的概念,用于量化衡量網絡數據在壓縮前后的變化情況。結合實驗數據分析和對比了網絡數據性質壓縮前后的變化,驗證了三種網絡數據壓縮方式和GPU并行計算力導引算法的有效性。
【關鍵詞】：力導引布局算法 關節(jié)點 介數中心性 k-核 GPU
【學位授予單位】：北京化工大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要4-6
• Abstract6-12
• 第一章 緒論12-22
• 1.1 課題研究背景及意義12-14
• 1.2 國內外相關研究14-19
• 1.3 論文主要貢獻19-20
• 1.4 論文的組織結構20-22
• 第二章 本文相關概念及算法22-28
• 2.1 FR布局算法22-24
• 2.2 關節(jié)點及查找算法24-25
• 2.3 本文相關拓撲參數25-26
• 2.4 本章小結26-28
• 第三章 大規(guī)模網絡壓縮布局及算法加速28-42
• 3.1 基于關節(jié)點的大規(guī)模網絡數據壓縮算法(CABAP)28-33
• 3.2 基于介數關節(jié)點的大規(guī)模網絡數據壓縮算法(CABBAP)33-35
• 3.3 基于k-核的大規(guī)模網絡布局壓縮算法(CABK)35-37
• 3.4 基于GPU的FR算法加速37-41
• 3.4.1 大規(guī)模網絡數據ICSR式存儲結構37-39
• 3.4.2 基于GPU的FR算法39-41
• 3.5 本章小結41-42
• 第四章 大規(guī)模網絡壓縮布局及算法加速實驗與分析42-62
• 4.1 面向壓縮布局的復雜網絡信息量42-43
• 4.2 CABAP算法實驗結果及分析43-47
• 4.3 CABBAP算法實驗結果及分析47-53
• 4.4 CABK算法實驗結果及分析53-56
• 4.5 基于GPU加速FR算法實驗結果及分析56-58
• 4.6 壓縮網絡細節(jié)展示58-59
• 4.7 本章小結59-62
• 第五章 結論與展望62-64
• 5.1 論文主要成果62-63
• 5.2 未來工作展望63-64
• 參考文獻64-68
• 致謝68-70
• 研究成果及發(fā)表的學術論文70-72
• 作者及導師簡介72-73
• 附件73-74

【參考文獻】

中國期刊全文數據庫 前2條

1 任磊;杜一;馬帥;張小龍;戴國忠;;大數據可視分析綜述[J];軟件學報;2014年09期

2 張清國,黃競偉;一個無向平面圖的畫圖算法[J];小型微型計算機系統(tǒng);2003年06期

，

本文編號：896930