本文選題：網(wǎng)絡(luò)圖壓縮 + 冪律分布�。� 參考：《西安電子科技大學(xué)》2014年碩士論文

【摘要】：互聯(lián)網(wǎng)中的網(wǎng)頁及其超鏈接可建模為一個(gè)龐大的有向圖，稱為Web Graph。Web Graph的分析研究可應(yīng)用于網(wǎng)頁排名、檢測(cè)網(wǎng)絡(luò)垃圾信息、發(fā)現(xiàn)社區(qū)和鏡像站點(diǎn)等。然而，這項(xiàng)研究受阻于需要把巨大的圖存儲(chǔ)到外存上，從而影響有效地隨機(jī)訪問結(jié)點(diǎn)。因此，把Web Graph壓縮存儲(chǔ)到內(nèi)存的研究具有十分重要的意義。 Web Graph具有本地性和相似性，且服從冪律分布。BV算法采用Zeta-k編碼，是最有效的Web Graph壓縮方案之一�；贐V算法，本文提出了兩種改進(jìn)的Web Graph壓縮算法：近似最優(yōu)引用序列的壓縮算法和合并最優(yōu)引用序列的壓縮算法。二者均采用引用壓縮，其關(guān)鍵是選取最優(yōu)引用序列。不同的是，前者不再局限于滑動(dòng)窗口內(nèi)部，可以實(shí)現(xiàn)沿著結(jié)點(diǎn)的引用鏈回溯搜索近似全局的最優(yōu)引用序列；后者則是通過合并固定數(shù)目的結(jié)點(diǎn)生成塊結(jié)點(diǎn)，用來作為塊內(nèi)結(jié)點(diǎn)的最優(yōu)引用序列。 本文選用五組測(cè)試數(shù)據(jù)分別對(duì)三種壓縮算法進(jìn)行測(cè)試。主要的測(cè)試內(nèi)容包括兩個(gè)基本點(diǎn)：存儲(chǔ)每條鏈接所用的比特位和隨機(jī)訪問每個(gè)結(jié)點(diǎn)所用的時(shí)間。最后，通過比較和分析三種算法的實(shí)驗(yàn)結(jié)果，，表明改進(jìn)后的方法提高了壓縮效果，而且縮短了結(jié)點(diǎn)引用鏈的長(zhǎng)度，提高了隨機(jī)訪問結(jié)點(diǎn)的效率。
[Abstract]:The web pages and their hyperlinks in the Internet can be modeled as a huge directed graph. The analysis and research called Web Graph.Web Graph can be applied to the ranking of web pages, the detection of web spam, the discovery of community and mirror sites, and so on. However, this study is hampered by the need to store large graphs on external memory, thus affecting efficient random access nodes. Therefore, it is of great significance to compress Web Graph into memory. Web Graph is one of the most effective Web Graph compression schemes, because it is local and similar, and Zeta-k coding is used in the following power law distribution. BV algorithm. Based on BV algorithm, this paper proposes two improved Web Graph compression algorithms: approximate optimal reference sequence compression algorithm and merging optimal reference sequence compression algorithm. Both of them adopt reference compression, and the key is to select the optimal reference sequence. The difference is that the former is no longer confined to the sliding window and can be traced back along the node's reference chain to search the approximate global optimal reference sequence, while the latter is to generate block nodes by merging a fixed number of nodes. Used as an optimal sequence of references within a block. In this paper, five groups of test data are selected to test the three compression algorithms. The main tests include two basic points: the bits used to store each link and the time taken to randomly access each node. Finally, by comparing and analyzing the experimental results of the three algorithms, it is shown that the improved method improves the compression effect, shortens the length of the node reference chain, and improves the efficiency of random access nodes.
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP393.092

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李永成;黃曙光;楊斌;郭浩;;新浪微博名人堂用戶關(guān)系網(wǎng)絡(luò)分析[J];江西師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年04期

2 王春娟;林振權(quán);;人類通信行為中的標(biāo)度律[J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2013年03期

3 葉強(qiáng);孫忠林;魏永山;;一種基于Hadoop的大規(guī)模圖直徑算法[J];電腦開發(fā)與應(yīng)用;2013年12期

4 張毅;曹晶晶;齊莉娜;吳必虎;;旅游目的地虛擬網(wǎng)絡(luò)結(jié)構(gòu)特征研究——以黃山市為例[J];北京大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年06期

5 熊金石;李建華;沈迪;郭威武;;節(jié)點(diǎn)崩潰條件下信息系統(tǒng)安全風(fēng)險(xiǎn)傳播[J];電光與控制;2014年01期

6 吳振宇;胡軍;李德毅;;社會(huì)標(biāo)注系統(tǒng)冪律特性分析[J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2014年02期

7 趙法棟;莊弘煒;金振興;;基于MLE的恐怖組織襲擊行為模式實(shí)證研究[J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2014年04期

8 高言;李昭輝;;基于人工股票市場(chǎng)的財(cái)富分布及演化研究[J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2015年01期

9 朱小棟;高春昌;王恒山;;引入資源即服務(wù)的云計(jì)算架構(gòu)及其應(yīng)用[J];上海理工大學(xué)學(xué)報(bào);2013年03期

10 陳震;陸松;李國(guó)輝;張和平;;安徽省火災(zāi)經(jīng)濟(jì)損失的尾部分布研究[J];火災(zāi)科學(xué);2013年03期

相關(guān)會(huì)議論文 前1條

1 李杰;張皎娟;;C2C電子商務(wù)顧客重復(fù)購(gòu)買冪分布規(guī)律及其影響因素[A];2013中國(guó)信息經(jīng)濟(jì)學(xué)會(huì)學(xué)術(shù)年會(huì)暨博士生論壇論文集[C];2013年

相關(guān)博士學(xué)位論文 前10條

1 李雁妮;深網(wǎng)數(shù)據(jù)集成與挖掘關(guān)鍵問題的建模及算法研究[D];西安電子科技大學(xué);2013年

2 高雅純;基于復(fù)雜系統(tǒng)理論的金融市場(chǎng)動(dòng)力學(xué)研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2013年

3 吳聯(lián)仁;基于人類動(dòng)力學(xué)的社交網(wǎng)絡(luò)信息傳播實(shí)證分析與建模研究[D];北京郵電大學(xué);2013年

4 劉瑤;社會(huì)網(wǎng)絡(luò)特征分析與社團(tuán)結(jié)構(gòu)挖掘[D];電子科技大學(xué);2013年

5 傅云斌;廣義生滅過程與隨機(jī)分枝樹演化[D];上海大學(xué);2013年

6 李朋;異構(gòu)信息網(wǎng)絡(luò)分析模型及其應(yīng)用研究[D];重慶大學(xué);2013年

7 程輝;網(wǎng)絡(luò)用戶偏好分析及話題趨勢(shì)預(yù)測(cè)方法研究[D];北京交通大學(xué);2013年

8 趙丙軍;國(guó)外力量訓(xùn)練研究知識(shí)網(wǎng)絡(luò)的結(jié)構(gòu)及演化特征[D];上海體育學(xué)院;2013年

9 楊婧;大型工程項(xiàng)目網(wǎng)絡(luò)化建模及關(guān)鍵節(jié)點(diǎn)分析方法研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2012年

10 傅晨波;復(fù)雜網(wǎng)絡(luò)同步若干問題研究[D];浙江大學(xué);2013年

相關(guān)碩士學(xué)位論文 前10條

1 楊俊;粒子群算法在發(fā)酵補(bǔ)料控制中的應(yīng)用和研究[D];大連理工大學(xué);2013年

2 耿玉嬌;MapReduce中基于抽樣技術(shù)的傾斜問題研究[D];大連海事大學(xué);2013年

3 章琴;基于BA的混合演化模型研究[D];西南大學(xué);2013年

4 楊yN;Wiki知識(shí)網(wǎng)絡(luò)的網(wǎng)絡(luò)特性與演化模型研究[D];浙江理工大學(xué);2013年

5 王越;微博用戶群體結(jié)構(gòu)挖掘算法分析研究[D];北京交通大學(xué);2013年

6 陸蕊;網(wǎng)絡(luò)相位聚類模型及應(yīng)用[D];西安電子科技大學(xué);2013年

7 周杰;考慮選擇性網(wǎng)絡(luò)攻擊的電網(wǎng)脆弱性分析[D];長(zhǎng)沙理工大學(xué);2013年

8 李彬;復(fù)雜網(wǎng)絡(luò)抗毀度和節(jié)點(diǎn)重要性評(píng)價(jià)方法[D];西安電子科技大學(xué);2013年

9 梁沙沙;基于單親遺傳算法的復(fù)雜網(wǎng)絡(luò)重疊社區(qū)結(jié)構(gòu)發(fā)現(xiàn)研究[D];內(nèi)蒙古大學(xué);2013年

10 肖平;廣東省高速公路網(wǎng)結(jié)構(gòu)復(fù)雜性分析[D];華南理工大學(xué);2013年

本文編號(hào)：1820991