大規(guī)模網(wǎng)絡(luò)布局壓縮算法及加速研究.pdf

1、復(fù)雜網(wǎng)絡(luò)可視化是復(fù)雜網(wǎng)絡(luò)研究中的重要手段。隨著Web2.0時(shí)代和大數(shù)據(jù)時(shí)代的來臨，作為研究對(duì)象的復(fù)雜網(wǎng)絡(luò)的規(guī)模越來越大，人們也越來越需要對(duì)規(guī)模龐大的數(shù)據(jù)進(jìn)行準(zhǔn)確地表達(dá)和理解，并從中進(jìn)一步探索和挖掘有效信息。采用傳統(tǒng)的數(shù)據(jù)表達(dá)方式已經(jīng)不再能夠滿足人們的需求。因此，將復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行可視化成為了人們理解和研究復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)的一個(gè)主要方式。然而伴隨著復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)的海量式增長，對(duì)復(fù)雜網(wǎng)絡(luò)可視化布局算法的布局效果和運(yùn)算速度都提出了新的挑戰(zhàn)。

2、　　在可視化布局算法中，力導(dǎo)引布局算法由于其布局結(jié)果的美觀性等原因得到了最為廣泛的應(yīng)用。因而，本文基于力導(dǎo)引布局算法，從優(yōu)化布局效果和提高算法效率兩方面同時(shí)對(duì)大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的布局算法進(jìn)行了改進(jìn)和實(shí)現(xiàn)。在優(yōu)化布局效果方面，分別利用復(fù)雜網(wǎng)絡(luò)中的關(guān)節(jié)點(diǎn)，介數(shù)中心性和k-核的概念，提出了三種不同的網(wǎng)絡(luò)數(shù)據(jù)壓縮方式。將網(wǎng)絡(luò)節(jié)點(diǎn)劃分為不同類別，并根據(jù)節(jié)點(diǎn)所屬類別進(jìn)一步對(duì)其進(jìn)行聚集合并，實(shí)現(xiàn)大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的壓縮布局顯示，從整體上清晰地顯示網(wǎng)絡(luò)宏觀結(jié)構(gòu)

3、。在提高算法效率方面，針對(duì)壓縮后的網(wǎng)絡(luò)數(shù)據(jù)，對(duì)力導(dǎo)引算法需要的斥力計(jì)算、引力計(jì)算和更新坐標(biāo)三個(gè)部分均實(shí)現(xiàn)了基于GPU的并行計(jì)算，大大縮短了算法的運(yùn)行時(shí)間，從而使人們?cè)诳山邮軙r(shí)間內(nèi)獲得大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的可視化布局結(jié)果。最后，給出相應(yīng)算法的實(shí)驗(yàn)布局結(jié)果，并提出了面向壓縮布局的復(fù)雜網(wǎng)絡(luò)信息量的概念，用于量化衡量網(wǎng)絡(luò)數(shù)據(jù)在壓縮前后的變化情況。結(jié)合實(shí)驗(yàn)數(shù)據(jù)分析和對(duì)比了網(wǎng)絡(luò)數(shù)據(jù)性質(zhì)壓縮前后的變化，驗(yàn)證了三種網(wǎng)絡(luò)數(shù)據(jù)壓縮方式和GPU并行計(jì)算力導(dǎo)引算法的