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

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

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

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

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