本文關鍵詞：隨機游走社區(qū)劃分算法的優(yōu)化技術研究

  更多相關文章： 復雜網(wǎng)絡 社區(qū)劃分 稀疏矩陣 隨機游走

【摘要】：無論是在自然界還是在人類社會中,隨處都可以見到復雜網(wǎng)絡的身影,例如,人類社會網(wǎng)絡,生物網(wǎng)絡,電路網(wǎng)絡等。為研究這些網(wǎng)絡下蘊含的意義和價值,就需要對網(wǎng)絡結構進行合理的系統(tǒng)性的分析。目前,對于復雜網(wǎng)絡的研究已經(jīng)滲透到各個領域中,社區(qū)劃分算法的研究是復雜網(wǎng)絡研究領域中的重要內容。隨著社會網(wǎng)絡和web技術的發(fā)展,網(wǎng)絡規(guī)模逐漸增加,需要復雜網(wǎng)絡社區(qū)劃分算法在大型的復雜網(wǎng)絡數(shù)據(jù)上可以進行高效快捷的社區(qū)劃分,這也是目前社區(qū)劃分領域的研究熱點。為了實現(xiàn)這一目的,本文從Page Rank算法獲得啟發(fā),利用隨機游走思想,設網(wǎng)絡中的每個節(jié)點都具有能量,網(wǎng)絡中節(jié)點的能量通過能量轉移概率矩陣進行相互傳遞。整個網(wǎng)絡中的節(jié)點經(jīng)過能量的相互傳遞達到穩(wěn)定狀態(tài)后,獲得能量矩陣,在能量矩陣中分析提取相互之間能量傳遞最多的兩個節(jié)點劃分到同一個社區(qū)中,逐漸實現(xiàn)整個劃分原則,直到整個網(wǎng)絡劃分為一個社區(qū)時終止,并且利用Q值來獲取最優(yōu)的劃分結果,這是整個算法的核心思想。隨著網(wǎng)絡規(guī)模的增大,算法在執(zhí)行過程中需要大量的存儲空間,當網(wǎng)絡規(guī)模達到一定程度,算法因存儲空間不足而導致無法有效執(zhí)行。我們知道社交網(wǎng)絡中節(jié)點的度是服從冪律分布的,從大規(guī)模社交網(wǎng)絡中抽象出的鄰接矩陣和能量轉移概率矩陣具有稀疏性。為了進一步優(yōu)化算法,利用稀疏矩陣壓縮存儲來降低算法執(zhí)行過程中需要的存儲空間。但是,在能量傳遞過程中,隨著迭代次數(shù)的增加,矩陣的稀疏性降低。為了保持矩陣的稀疏性,本文根據(jù)矩陣的維度設定閾值來維持矩陣的稀疏性,并且通過實驗來說明設定閾值的必要性以及如何設定閾值來保持矩陣的稀疏性,從而提高算法的執(zhí)行效率。為了驗證本文提出的算法的精確性,將算法在已知劃分結果的經(jīng)典小樣本數(shù)據(jù)集上做了測試,獲得了精確的劃分結果;并將該算法在大規(guī)模網(wǎng)絡數(shù)據(jù)集進行驗證,在得到較好劃分結構的基礎上提高了計算效率。
【關鍵詞】：復雜網(wǎng)絡 社區(qū)劃分 稀疏矩陣 隨機游走
【學位授予單位】：沈陽航空航天大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 摘要6-7
• Abstract7-11
• 第1章 緒論11-17
• 1.1 論文的研究背景與意義11-13
• 1.2 國內外研究現(xiàn)狀13-15
• 1.3 相關工作和內容安排15-17
• 1.3.1 相關工作15-16
• 1.3.2 本文所做的內容安排16-17
• 第2章 隨機游走思想17-24
• 2.1 圖的若干概念和定義17
• 2.2 隨機游走思想17-19
• 2.3 PAGERANK算法思想19-22
• 2.4 基于復雜網(wǎng)絡的隨機游走思想22-24
• 第3章 稀疏矩陣的壓縮存儲24-39
• 3.1 稀疏矩陣分析26-30
• 3.2 稀疏矩陣的壓縮存儲模式30-34
• 3.2.1 Coordinate(COO)存儲模式31
• 3.2.2 Compressed Sparse Row(CSR)存儲模式31-32
• 3.2.3 ELLPACK (ELL)存儲模式32-33
• 3.2.4 Diagonal (DIA)存儲模式33-34
• 3.3 稀疏矩陣壓縮存儲模式的分析34-39
• 3.3.1 數(shù)據(jù)分析34-37
• 3.3.2 復雜網(wǎng)絡中的稀疏矩陣37-39
• 第4章 基于隨機游走思想的社區(qū)劃分算法39-55
• 4.1 經(jīng)典社區(qū)劃分算法39-43
• 4.1.1 GN算法40-42
• 4.1.2 FN算法42-43
• 4.2 基于隨機游走思想進行社區(qū)劃分算法43-48
• 4.2.1 基于隨機游走思想進行社區(qū)劃分算法描述44-46
• 4.2.2 社區(qū)劃分算法的評價指標46
• 4.2.3 大規(guī)模復雜網(wǎng)絡的社區(qū)劃分算法46-48
• 4.3 實驗48-55
• 4.3.1 復雜網(wǎng)絡中重要指標介紹48-49
• 4.3.2 閾值設置的具體分析49-51
• 4.3.3 實驗結果與分析51-55
• 結論55-57
• 參考文獻57-60
• 致謝60-62
• 攻讀碩士期間發(fā)表（含錄用）的學術論文62

【參考文獻】

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

1 唐杰;陳文光;;面向大社交數(shù)據(jù)的深度分析與挖掘[J];科學通報;2015年Z1期

2 李佳佳;張秀霞;譚光明;陳明宇;;選擇稀疏矩陣乘法最優(yōu)存儲格式的研究[J];計算機研究與發(fā)展;2014年04期

3 平宇;向陽;張波;黃寅飛;;基于MapReduce的并行PageRank算法實現(xiàn)[J];計算機工程;2014年02期

4 易成岐;鮑媛媛;薛一波;;社會網(wǎng)絡大數(shù)據(jù)分析框架及其關鍵技術[J];中興通訊技術;2014年01期

5 陳德華;周蒙;孫延青;鄭亮亮;;MR-GSpar:一種基于MapReduce的大圖稀疏化算法[J];計算機科學;2013年10期

6 吳志川;毛琛;韓蕾;陳立軍;;高度可伸縮的稀疏矩陣乘法[J];計算機科學與探索;2013年11期

7 向林泓;陳芋文;張昱琳;;基于Hadoop平臺的高階矩陣相乘MapReduce算法研究[J];計算機科學;2013年S1期

8 張駿;;一種基于MapReduce并行框架的大規(guī)模矩陣乘法運算的實現(xiàn)[J];計算機應用與軟件;2012年06期

9 金弟;楊博;劉杰;劉大有;何東曉;;復雜網(wǎng)絡簇結構探測——基于隨機游走的蟻群算法[J];軟件學報;2012年03期

，

本文編號：917385