復雜網絡的可視化顯示.pdf

1、實際社會中的復雜系統(tǒng)要么以復雜網絡的形式存在，要么可以通過某種形式的轉換而變?yōu)閺碗s網絡。而傳統(tǒng)的利用數字和表格的形式來組織數據的方式，使得人們很難對復雜網絡有整體上的認識。復雜網絡可視化技術可以有效地展現網絡的結構，使得人們可以從中及時獲取有用的信息來加以利用。而由于信息社會的高速發(fā)展，所產生的數據也越來越多，復雜網絡的規(guī)模在急劇增長，嚴格按照布局算法來對網絡進行可視化變得越來越困難。一方面由于計算機性能的限制，導致其在應對大量的數據時

2、不能有效地對節(jié)點進行布局，導致大量節(jié)點的重疊和邊的交叉；另一方面，在結果展示的圖上節(jié)點太多，會嚴重影響人們的觀察，也就無法從其中獲取任何有用信息了。因此，誕生了可視化壓縮算法。
　　可視化壓縮算法的目標就是對網絡的節(jié)點和邊進行刪除操作，這樣做的目的是為了更好地展示網絡的拓撲結構，便于人們更好地去理解它，以挖掘網絡所包含的有用信息。眾所周知，實際社會中的復雜網絡的度分布都比較好地滿足冪律分布，即大部分節(jié)點的度比較小，只有極少部分節(jié)點

3、的度比較大。而這些具有較較小度的節(jié)點中，大部分的節(jié)點都屬于不那么重要的節(jié)點，其存在與否對網絡的整體拓撲結構影響不大?？梢暬瘔嚎s算法的做法就是刪除重要程度不高的節(jié)點。
　　本文設計了一個復雜網絡壓縮算法，該壓縮算法的主要操作有節(jié)點的合并和節(jié)點的刪除。節(jié)點的刪除操作所依據的是節(jié)點的重要性程度，本文采用PageRank值來表示節(jié)點的重要性程度。復雜網絡普遍存在社區(qū)結構的特性，所以節(jié)點的重要性程度也具有相對性。因此算法先利用基于標簽傳播的

4、RAK社區(qū)挖掘算法對網絡進行社區(qū)劃分，然后以社區(qū)為單位來對節(jié)點進行刪除。節(jié)點刪除時，考慮到原網絡的連通性，還要適當地進行邊的添加。由于復雜網絡的節(jié)點規(guī)模巨大，為了滿足快速和準確的要求，采用了GraphLab并行框架。
　　本文實現了上述的復雜網絡壓縮算法，且其中的PageRank值的計算及社區(qū)劃分都是基于GraphLab框架的實現。通過在實際數據集上進行測試，來驗證在GraphLab框架下的PageRank算法和RAK算法的準確性