本文關(guān)鍵詞：大規(guī)模網(wǎng)絡(luò)布局壓縮算法及加速研究

  更多相關(guān)文章： 力導(dǎo)引布局算法 關(guān)節(jié)點 介數(shù)中心性 k-核 GPU

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

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

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前2條

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

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

，

本文編號：896930