關(guān)系圖的快速布局技術(shù)及其評價標(biāo)準(zhǔn)的研究.pdf

1、當(dāng)今社會互聯(lián)網(wǎng)日益普及,近幾年來涌現(xiàn)出了大量社交網(wǎng)站,這使得人們能夠更加方便的利用網(wǎng)絡(luò)交換信息實現(xiàn)自己的個人發(fā)展。如何將網(wǎng)站服務(wù)器中存儲的大量用戶數(shù)據(jù)構(gòu)造成一個社會網(wǎng)絡(luò)圖并將其進行信息檢索和直觀分析形成了近幾年來的一個重要研究方向——社會化網(wǎng)絡(luò)服務(wù)。
　　作為社會化網(wǎng)絡(luò)服務(wù)研究的一個重要方向,可視化技術(shù)主要研究如何將網(wǎng)站服務(wù)器中存儲的大量數(shù)據(jù)如內(nèi)容和用戶等構(gòu)造社會網(wǎng)絡(luò)圖并將其界面展示給用戶,便于其直觀分析數(shù)據(jù)。在可視化技術(shù)研究領(lǐng)域

2、中,傳統(tǒng)的布局算法當(dāng)網(wǎng)絡(luò)圖規(guī)模較大時會遇到瓶頸,并且現(xiàn)有的評價標(biāo)準(zhǔn)都是算法設(shè)計者直接提出來的,并沒有嚴(yán)格的理論和實驗基礎(chǔ)。
　　本文首先列舉了關(guān)系圖的一些可視化技術(shù),然后介紹了node-link布局的兩種彈簧布局算法——傳統(tǒng)的單級布局方法和多級布局方法?；趥鹘y(tǒng)布局算法的不足,本文提出了一種新的能快速對大規(guī)模(關(guān)系圖節(jié)點規(guī)模在1000到10000之間)關(guān)系圖布局的算法,并通過實驗證明了該算法的優(yōu)越性。同時本文在根據(jù)前人實驗的結(jié)果提

3、出了兩種node-link評判指標(biāo),并分別設(shè)計了兩組實驗證明了利用該指標(biāo)可以評判出布局結(jié)果的好壞。本文的主要研究內(nèi)容如下:
　　(1)提出一種新的利用簡單隨機抽樣來提高斥力計算效率的單級布局算法,該算法對傳統(tǒng)的布局算法的每個點的斥力計算所涉及到的點,斥力計算公式,引力計算公式進行了調(diào)整和優(yōu)化,通過實驗驗證能大大減少單級布局算法的達到穩(wěn)定狀態(tài)的運行時間。
　　(2)結(jié)合基于抽樣的單級布局算法和壓縮-細化策略,本文提出了一種快速

4、多級布局算法。該多級布局算法提出了一種新的壓縮策略,使得每層壓縮的圖更加符合圖結(jié)構(gòu),在細化每一層布局時采用了利用簡單隨機抽樣計算斥力的單級布局算法,大大減少了大規(guī)模社會網(wǎng)絡(luò)圖的布局時間,同時該算法增加了布局結(jié)果居中的功能。
　　(3)傳統(tǒng)的布局算法指標(biāo)沒有經(jīng)過實驗推斷,要滿足這些美學(xué)標(biāo)準(zhǔn)布局需要耗費很多的時間。本文根據(jù)前人實驗推斷結(jié)果提出了兩種有社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)圖布局算法的評價指標(biāo),同時其中指標(biāo)之一還可以作為評判網(wǎng)絡(luò)圖是否有社區(qū)結(jié)構(gòu)