復雜網(wǎng)絡的可視化顯示.pdf

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

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

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

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