本文關鍵詞：基于結(jié)構相似度的動態(tài)復雜網(wǎng)絡社團增量更新算法研究

  更多相關文章： 動態(tài)復雜網(wǎng)絡 社團劃分 相似度 增量更新

【摘要】：隨著科學技術的發(fā)展,科學研究理論的變革,復雜網(wǎng)絡已成為熱門研究課題。目前,發(fā)現(xiàn)的復雜網(wǎng)絡結(jié)構特征有小世界、無標度、冪律分布等,其中比較重要且研究廣泛的是社團結(jié)構特征。在大容量存儲成為可能、大數(shù)據(jù)時代到來的背景下,當今各領域的網(wǎng)絡均呈現(xiàn)出規(guī)模大且頻繁平穩(wěn)變化的特點。以往提出的社團劃分算法并不能被直接簡單地從傳統(tǒng)小規(guī)模靜態(tài)網(wǎng)絡上移植到當今大規(guī)模動態(tài)網(wǎng)絡平臺上運行,這樣做是低效率的,甚至是不切合實際的。因此,針對當今各領域網(wǎng)絡形態(tài)的特點,提出一種專門應用于動態(tài)大規(guī)模復雜網(wǎng)絡的社團劃分算法,來解決復雜網(wǎng)絡動態(tài)變化引起社團劃分變動的問題。本文在余弦相似度的基礎上提出了用于描述兩點距離的結(jié)構相似度——基于二級影響的結(jié)構相似度的定義。所謂二級影響結(jié)構相似度,即是網(wǎng)絡中邊的變化不僅會影響兩端點,同時也可能會對兩端點鄰域內(nèi)的節(jié)點造成影響(點變化同理)。針對當今復雜網(wǎng)絡超大規(guī)模的特點,在節(jié)點間結(jié)構相似度及結(jié)構相似度相關的定義基礎上提出了一種局部的靜態(tài)社團劃分算法LBS (Local method Based on Similarity)算法。LBS算法采用局部思想,即可以不用掌握全局信息,就可以進行社團劃分,極大降低了算法的時間復雜度。LBS算法采用兩階段方式對網(wǎng)絡進行社團劃分：第一階段,通過節(jié)點的連接偏好,形成社團小結(jié)構；第二階段,通過發(fā)揮連接偏好鏈中核節(jié)點的角色任務,對連接偏好鏈進行連接,最終形成社團結(jié)構�；贚BS算法在社團的增量更新上的優(yōu)勢,本文進一步提出了動態(tài)復雜網(wǎng)絡上的社團增量更新算法IU-LBS (Incremental Updating LBS)算法。IU-LBS算法在網(wǎng)絡發(fā)生變化時,首先檢測變化相關節(jié)點集,然后對屬于不同類別的節(jié)點采用相應的社團更新方法。本文通過在多個真實網(wǎng)絡和人工生成網(wǎng)絡上運行LBS靜態(tài)算法和IU-LBS動態(tài)算法,進一步實證了LBS算法針對于靜態(tài)復雜網(wǎng)絡的社團劃分、IU-LBS算法針對于動態(tài)復雜網(wǎng)絡的社團更新均是高效準確的。
【關鍵詞】：動態(tài)復雜網(wǎng)絡 社團劃分 相似度 增量更新
【學位授予單位】：遼寧大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 摘要4-5
• ABSTRACT5-11
• 第1章 緒論11-15
• 1.1 選題背景及研究意義11-13
• 1.2 本文的主要工作及創(chuàng)新點13-14
• 1.3 論文結(jié)構14-15
• 第2章 復雜網(wǎng)絡和社團理論及研究方法15-22
• 2.1 復雜網(wǎng)絡及社團理論15-17
• 2.2 國內(nèi)外現(xiàn)有和經(jīng)典的靜態(tài)社團劃分方法17-19
• 2.3 動態(tài)復雜網(wǎng)絡上的社團劃分方法19-22
• 第3章 社團劃分相關定義22-30
• 3.1 復雜網(wǎng)絡的表示方法22-23
• 3.2 相似度表示方法23
• 3.3 基于二級影響的結(jié)構相似度定義23-26
• 3.4 基于結(jié)構相似度的區(qū)域定義26-27
• 3.5 連接偏好的定義27-28
• 3.6 網(wǎng)絡中節(jié)點的域信息存儲結(jié)構28-30
• 第4章 靜態(tài)局部社團劃分算法-LBS算法30-45
• 4.1 LBS算法基本思想30
• 4.2 LBS算法具體步驟30-34
• 4.3 靜態(tài)算法的實驗與分析34-45
• 4.3.1 網(wǎng)絡(圖)的存儲方式與表示34-35
• 4.3.2 實驗目的35-36
• 4.3.3 劃分質(zhì)量評價標準36
• 4.3.4 參數(shù)選擇的影響分析36-38
• 4.3.5 現(xiàn)實網(wǎng)絡實驗結(jié)果及分析38-42
• 4.3.6 人工網(wǎng)絡實驗結(jié)果及分析42-45
• 第5章 動態(tài)復雜網(wǎng)絡上的社團更新算法-IU-LBS算法45-59
• 5.1 IU-LBS算法基本思想45-46
• 5.2 IU-LBS算法基本過程及具體步驟46-55
• 5.2.1 變化相關節(jié)點集的確定46-47
• 5.2.2 更新變化節(jié)點的屬性域47-48
• 5.2.3 社團劃分相關的變化量48-50
• 5.2.4 社團劃分的更新50-52
• 5.2.5 IU-LBS算法具體步驟及示例52-55
• 5.3 動態(tài)算法的實驗與分析55-59
• 5.3.1 實驗目的55-56
• 5.3.2 劃分質(zhì)量評價標準56
• 5.3.3 實驗網(wǎng)絡數(shù)據(jù)集56-59
• 第6章 總結(jié)和展望59-61
• 6.1 總結(jié)59
• 6.2 展望59-61
• 致謝61-62
• 參考文獻62-64

【相似文獻】

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

1 張勇;金偉其;;基于結(jié)構相似度與感興趣區(qū)域的圖像融合評價方法[J];光子學報;2011年02期

2 許少凡;劉顯峰;狄紅衛(wèi);;基于加權結(jié)構相似度的圖像融合質(zhì)量評價[J];暨南大學學報(自然科學版);2007年05期

3 王曉艷;劉勇;蔣志勇;;一種基于結(jié)構相似度的IHS變換融合算法[J];遙感技術與應用;2011年05期

4 狄紅衛(wèi);劉顯峰;;基于結(jié)構相似度的圖像融合質(zhì)量評價[J];光子學報;2006年05期

5 黃健斌;鐘翔;孫鶴立;茆婉婷;;基于相似性模塊度最大約束標記傳播的網(wǎng)絡社團發(fā)現(xiàn)算法[J];北京大學學報(自然科學版);2013年03期

6 ;[J];;年期

中國重要會議論文全文數(shù)據(jù)庫 前3條

1 張勇;金偉其;;基于結(jié)構相似度與感興趣區(qū)域的圖像融合評價方法[A];中國光學學會2010年光學大會論文集[C];2010年

2 許晟;李亞楠;王斌;吳麗輝;;基于加權SimRank的中文查詢推薦研究[A];第五屆全國信息檢索學術會議論文集[C];2009年

3 李增揚;李兵;何克清;;本體中復雜網(wǎng)絡特性的發(fā)現(xiàn)[A];2006全國復雜網(wǎng)絡學術會議論文集[C];2006年

中國博士學位論文全文數(shù)據(jù)庫 前1條

1 俞唯仁;普適的結(jié)構相似度在大規(guī)模網(wǎng)絡中的計算優(yōu)化技術研究[D];東華大學;2012年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 陳東;基于子圖匹配的社會網(wǎng)絡目標群體檢索技術研究[D];解放軍信息工程大學;2014年

2 許凱;基于結(jié)構相似度的圖像修補算法研究[D];蘭州大學;2016年

3 周進;基于結(jié)構相似度的動態(tài)復雜網(wǎng)絡社團增量更新算法研究[D];遼寧大學;2016年

4 張振山;基于結(jié)構相似度的圖像去噪方法研究[D];西安電子科技大學;2014年

5 萬芬;結(jié)構相似度圖像質(zhì)量評價算法的改進研究[D];大連海事大學;2011年

6 鄭德品;基于結(jié)構相似度的圖像質(zhì)量評價方法研究[D];浙江大學;2007年

7 周長飛;基于MIC的圖像顯著性檢測技術研究[D];國防科學技術大學;2013年

8 徐小琳;重視邊緣的結(jié)構相似度圖像/視頻質(zhì)量評價方法研究[D];華南理工大學;2012年

9 陳巖;基于結(jié)構相似度的圖像質(zhì)量評估研究[D];華北電力大學（北京）;2008年

10 陳勇;結(jié)構相似度及其在推薦系統(tǒng)中的應用研究[D];電子科技大學;2011年

，

本文編號：643139