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

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

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

3、。在提高算法效率方面，針對壓縮后的網絡數(shù)據(jù)，對力導引算法需要的斥力計算、引力計算和更新坐標三個部分均實現(xiàn)了基于GPU的并行計算，大大縮短了算法的運行時間，從而使人們在可接受時間內獲得大規(guī)模網絡數(shù)據(jù)的可視化布局結果。最后，給出相應算法的實驗布局結果，并提出了面向壓縮布局的復雜網絡信息量的概念，用于量化衡量網絡數(shù)據(jù)在壓縮前后的變化情況。結合實驗數(shù)據(jù)分析和對比了網絡數(shù)據(jù)性質壓縮前后的變化，驗證了三種網絡數(shù)據(jù)壓縮方式和GPU并行計算力導引算法的