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

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

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

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

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

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

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

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

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