本文關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)的可視化顯示

  更多相關(guān)文章： 復(fù)雜網(wǎng)絡(luò)可視化 壓縮算法 PageRank 社區(qū)挖掘 GraphLab

【摘要】：實際社會中的復(fù)雜系統(tǒng)要么以復(fù)雜網(wǎng)絡(luò)的形式存在,要么可以通過某種形式的轉(zhuǎn)換而變?yōu)閺?fù)雜網(wǎng)絡(luò)。而傳統(tǒng)的利用數(shù)字和表格的形式來組織數(shù)據(jù)的方式,使得人們很難對復(fù)雜網(wǎng)絡(luò)有整體上的認識。復(fù)雜網(wǎng)絡(luò)可視化技術(shù)可以有效地展現(xiàn)網(wǎng)絡(luò)的結(jié)構(gòu),使得人們可以從中及時獲取有用的信息來加以利用。而由于信息社會的高速發(fā)展,所產(chǎn)生的數(shù)據(jù)也越來越多,復(fù)雜網(wǎng)絡(luò)的規(guī)模在急劇增長,嚴格按照布局算法來對網(wǎng)絡(luò)進行可視化變得越來越困難。一方面由于計算機性能的限制,導(dǎo)致其在應(yīng)對大量的數(shù)據(jù)時不能有效地對節(jié)點進行布局,導(dǎo)致大量節(jié)點的重疊和邊的交叉;另一方面,在結(jié)果展示的圖上節(jié)點太多,會嚴重影響人們的觀察,也就無法從其中獲取任何有用信息了。因此,誕生了可視化壓縮算法。可視化壓縮算法的目標就是對網(wǎng)絡(luò)的節(jié)點和邊進行刪除操作,這樣做的目的是為了更好地展示網(wǎng)絡(luò)的拓撲結(jié)構(gòu),便于人們更好地去理解它,以挖掘網(wǎng)絡(luò)所包含的有用信息。眾所周知,實際社會中的復(fù)雜網(wǎng)絡(luò)的度分布都比較好地滿足冪律分布,即大部分節(jié)點的度比較小,只有極少部分節(jié)點的度比較大。而這些具有較較小度的節(jié)點中,大部分的節(jié)點都屬于不那么重要的節(jié)點,其存在與否對網(wǎng)絡(luò)的整體拓撲結(jié)構(gòu)影響不大。可視化壓縮算法的做法就是刪除重要程度不高的節(jié)點。本文設(shè)計了一個復(fù)雜網(wǎng)絡(luò)壓縮算法,該壓縮算法的主要操作有節(jié)點的合并和節(jié)點的刪除。節(jié)點的刪除操作所依據(jù)的是節(jié)點的重要性程度,本文采用PageRank值來表示節(jié)點的重要性程度。復(fù)雜網(wǎng)絡(luò)普遍存在社區(qū)結(jié)構(gòu)的特性,所以節(jié)點的重要性程度也具有相對性。因此算法先利用基于標簽傳播的RAK社區(qū)挖掘算法對網(wǎng)絡(luò)進行社區(qū)劃分,然后以社區(qū)為單位來對節(jié)點進行刪除。節(jié)點刪除時,考慮到原網(wǎng)絡(luò)的連通性,還要適當?shù)剡M行邊的添加。由于復(fù)雜網(wǎng)絡(luò)的節(jié)點規(guī)模巨大,為了滿足快速和準確的要求,采用了GraphLab并行框架。本文實現(xiàn)了上述的復(fù)雜網(wǎng)絡(luò)壓縮算法,且其中的PageRank值的計算及社區(qū)劃分都是基于GraphLab框架的實現(xiàn)。通過在實際數(shù)據(jù)集上進行測試,來驗證在GraphLab框架下的PageRank算法和RAK算法的準確性及高效性,同時測試本文的壓縮算法。通過檢驗壓縮后的網(wǎng)絡(luò)的度分布,發(fā)現(xiàn)其仍滿足冪律的特性,說明了壓縮算法的有效性。最后展示了壓縮效果。
【關(guān)鍵詞】：復(fù)雜網(wǎng)絡(luò)可視化 壓縮算法 PageRank 社區(qū)挖掘 GraphLab
【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要5-6
• ABSTRACT6-10
• 第一章 緒論10-19
• 1.1 研究背景與意義10-11
• 1.2 國內(nèi)外研究現(xiàn)狀11-17
• 1.3 本文的主要研究內(nèi)容及結(jié)構(gòu)安排17-19
• 第二章 復(fù)雜網(wǎng)絡(luò)分析研究19-34
• 2.1 復(fù)雜網(wǎng)絡(luò)簡介19-22
• 2.2 復(fù)雜網(wǎng)絡(luò)的統(tǒng)計特征22-24
• 2.3 復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘方法24-26
• 2.4 復(fù)雜網(wǎng)絡(luò)中的節(jié)點重要性程度26-30
• 2.5 GraphLab并行框架30-32
• 2.5.1 GraphLab的數(shù)據(jù)模型31-32
• 2.5.2 GraphLab的執(zhí)行模型32
• 2.6 本章小結(jié)32-34
• 第三章 基于GraphLab的PageRank算法及RAK算法實現(xiàn)34-53
• 3.1 問題提出34
• 3.2 基于GraphLab的PageRank算法的實現(xiàn)34-41
• 3.2.1 基本思路34-35
• 3.2.2 具體實現(xiàn)35-39
• 3.2.3 實驗結(jié)果及分析39-41
• 3.3 基于GraphLab的RAK社區(qū)挖掘算法的實現(xiàn)41-51
• 3.3.1 基本思路41-43
• 3.3.2 具體實現(xiàn)43-48
• 3.3.3 實驗結(jié)果及分析48-51
• 3.4 本章小結(jié)51-53
• 第四章 基于PageRank和RAK社區(qū)劃分的可視化壓縮算法53-68
• 4.1 問題描述及目標53
• 4.2 算法設(shè)計53-59
• 4.3 實驗結(jié)果及分析59-66
• 4.5 本章總結(jié)66-68
• 第五章 總結(jié)與展望68-70
• 5.1 本文總結(jié)68-69
• 5.2 后續(xù)工作展望69-70
• 致謝70-71
• 參考文獻71-74
• 攻讀碩士學(xué)位期間取得的成果74-75

【共引文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 蔣宗禮;李憲雷;徐學(xué)可;;基于主題Hub值的元搜索[J];北京工業(yè)大學(xué)學(xué)報;2009年03期

2 葉琳莉;林嵩凱;;基于Web結(jié)構(gòu)挖掘算法的網(wǎng)站構(gòu)建[J];電腦知識與技術(shù);2008年34期

3 王梅;;搜索引擎中的web鏈接算法研究與改進[J];電腦知識與技術(shù);2009年24期

4 譚濤;;高效的動態(tài)腳本網(wǎng)頁關(guān)聯(lián)性挖掘算法研究[J];電腦知識與技術(shù);2012年13期

5 李江;殷之明;;鏈接分析研究綜述[J];大學(xué)圖書館學(xué)報;2008年02期

6 王艷輝,吳斌,王柏;電信社群網(wǎng)絡(luò)靜態(tài)幾何性質(zhì)分析研究[J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2005年02期

7 段曉東;王存睿;劉向東;張慶靈;;基于網(wǎng)絡(luò)權(quán)重的多社團網(wǎng)絡(luò)結(jié)構(gòu)劃分算法[J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2009年03期

8 譚麗華;董毅明;李林紅;;互聯(lián)網(wǎng)群體智能的涌現(xiàn)[J];管理學(xué)報;2010年12期

9 邱均平,張洋;網(wǎng)絡(luò)信息計量學(xué)綜述[J];高校圖書館工作;2005年01期

10 肖國強;張芳;;一個元搜索引擎的設(shè)計與實現(xiàn)[J];微處理機;2008年04期

，

本文編號：1099948