大規(guī)模社會網(wǎng)絡(luò)可視化若干問題及算法研究.pdf

1、在Web2.0時代，互聯(lián)網(wǎng)中社交網(wǎng)絡(luò)（臉書、Twitter、微信、新浪微博等）發(fā)展迅速，社交媒體網(wǎng)絡(luò)成員數(shù)目龐大，關(guān)系錯綜復(fù)雜，迫切需要專門針對大規(guī)模社會網(wǎng)絡(luò)的圖形可視化技術(shù)的研究。然而，社會網(wǎng)絡(luò)的大規(guī)模性、語義性以及社區(qū)性等特點要求我們必須要面向社會網(wǎng)絡(luò)的不同特點，研究具有針對性的社會網(wǎng)絡(luò)可視化方法。本文在現(xiàn)有研究工作的基礎(chǔ)上，針對社會網(wǎng)絡(luò)數(shù)據(jù)的新特性，結(jié)合關(guān)系圖抽樣算法及協(xié)同分類算法等最新研究成果，提出了若干針對社會網(wǎng)絡(luò)數(shù)據(jù)大規(guī)模性

2、、語義性以及社區(qū)性特點的可視化方法。本文的研究內(nèi)容介紹如下：
　　1.針對社會網(wǎng)絡(luò)數(shù)據(jù)的大規(guī)模性，提出了基于拓?fù)浞謱幽Ｐ偷纳鐣W(wǎng)絡(luò)抽樣算法（SS）與基于溫度傳導(dǎo)模型的社會網(wǎng)絡(luò)抽樣算法（TCS）?；谕?fù)浞謱幽Ｐ偷纳鐣W(wǎng)絡(luò)抽樣算法將整個社會網(wǎng)絡(luò)根據(jù)其直徑劃分成不同層次的子網(wǎng)絡(luò)，并在每一個層次的子網(wǎng)絡(luò)中進(jìn)行抽樣操作；基于溫度傳導(dǎo)模型的社會網(wǎng)絡(luò)抽樣算法從社會網(wǎng)絡(luò)中的某一個體開始燃燒，模擬物體燃燒后溫度傳導(dǎo)的物理過程，蔓延式地在原社會網(wǎng)絡(luò)

3、中進(jìn)行抽樣操作。通過在多個經(jīng)典的社會網(wǎng)絡(luò)數(shù)據(jù)集上的實驗結(jié)果表明，這兩種社會網(wǎng)絡(luò)抽樣方法不但可以降低社會網(wǎng)絡(luò)的數(shù)據(jù)規(guī)模，并且可以很好的保持抽樣子網(wǎng)絡(luò)與原社會網(wǎng)絡(luò)的拓?fù)湟恢滦浴?br>　　2.針對社會網(wǎng)絡(luò)中個體的意見性特征，提出了面向兩類意見網(wǎng)絡(luò)的意見環(huán)可視化方法（OpinionRings）。意見環(huán)可視化方法采用同心環(huán)的總體布局方式，將意見網(wǎng)絡(luò)中三個意見群組中的個體分別放置在三個相互獨立的區(qū)域內(nèi)。采用協(xié)同分類的方法來預(yù)測中立個體的意見傾向概

4、率，并將該意見傾向概率通過中立個體在布局中的位置與顏色可視化表現(xiàn)出來，使用戶可以通過觀察布局即可知中立個體未來的意見傾向。同時，通過一系列美學(xué)優(yōu)化算法使整個圖形布局既符合人眼的美學(xué)體驗又可揭示兩類意見網(wǎng)絡(luò)中蘊含的信息。通過一系列客觀的對比試驗表明，意見環(huán)可視化方法對兩類意見網(wǎng)絡(luò)可視化時，其質(zhì)量優(yōu)于其它傳統(tǒng)的可視化方法。同時，基于用戶體驗的滿意度調(diào)查也顯示意見環(huán)可視化布局方法能夠揭示意見網(wǎng)絡(luò)中蘊含的信息，滿足用戶多元化的可視化體驗需求。<

5、br>　　3.針對社會網(wǎng)絡(luò)中個體的多意見性特征，提出了面向多類意見網(wǎng)絡(luò)的多意見環(huán)可視化方法（Multi-opinion Ring）。多意見環(huán)可視化方法同樣采用同心環(huán)的總體布局方式，將社會網(wǎng)絡(luò)中的中立意見群組與具有確定意見的群組中的個體分別放置在中心圓區(qū)域及外環(huán)區(qū)域，并根據(jù)不同的意見目標(biāo)（Opinion target），將外環(huán)區(qū)域劃分成若干個獨立的扇環(huán)區(qū)域來可視化不同的意見群組。本文采用協(xié)同分類的方法來預(yù)測中立個體的意見傾向概率，并將該意

6、見概率通過中立個體在布局中的位置與顏色可視地表現(xiàn)出來，使用戶通過觀察圖形布局即可知中立個體未來可能持有的意見傾向。同時，通過一系列美學(xué)優(yōu)化算法使整個圖形布局既符合人眼的美學(xué)體驗又可揭示多類意見網(wǎng)絡(luò)中所蘊含的信息。實驗結(jié)果表明了多意見環(huán)可視化方法在對多意見網(wǎng)絡(luò)可視化過程中的有效性。
　　4.針對社會網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)性特點，提出了社會網(wǎng)絡(luò)空間自適應(yīng)多級布局算法。該算法的特點是對社會網(wǎng)絡(luò)進(jìn)行可視化布局的同時重點突出社會網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)特征，

7、并合理地利用有限的可視化顯示區(qū)域?qū)ι鐣W(wǎng)絡(luò)進(jìn)行可視化展示。該算法包含兩個子過程，社會網(wǎng)絡(luò)的多級壓縮過程以及自頂向下的布局過程。利用多級壓縮算法獲得原社會網(wǎng)絡(luò)的層次結(jié)構(gòu)，基于此壓縮結(jié)構(gòu)進(jìn)行自頂向下的空間自適應(yīng)布局算法。通過與快速多級布局算法F M3的對比顯示，空間自適應(yīng)多級布局算法可以合理利用顯示區(qū)域來對社會網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行可視化，同時還能夠明顯突出其社區(qū)性的特點。
　　本文提出了五個算法來解決大規(guī)模社會網(wǎng)絡(luò)可視化的若干問題?；谕?fù)浞?/p>

8、層模型的社會網(wǎng)絡(luò)抽樣算法與基于溫度傳導(dǎo)模型的社會網(wǎng)絡(luò)抽樣算法的作用是降低社會網(wǎng)絡(luò)的數(shù)據(jù)規(guī)模，同時使抽樣子網(wǎng)絡(luò)和原社會網(wǎng)絡(luò)之間保持較好的拓?fù)湎嗨菩?，?dāng)待可視化社會網(wǎng)絡(luò)數(shù)據(jù)集規(guī)模較大時，可先利用社會網(wǎng)絡(luò)抽樣算法降低社會網(wǎng)絡(luò)的規(guī)模，再對抽樣子網(wǎng)絡(luò)進(jìn)行可視化。面向兩類意見網(wǎng)絡(luò)的意見環(huán)可視化算法是針對社會網(wǎng)絡(luò)中的語義性特點設(shè)計的可視化方法，面向多類意見網(wǎng)絡(luò)的多意見環(huán)可視化布局算法將兩類意見網(wǎng)絡(luò)擴展為多類意見網(wǎng)絡(luò)?？臻g自適應(yīng)多級布局算法針對社會網(wǎng)絡(luò)