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

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

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

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

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