本文關鍵詞：基于進化計算的社區(qū)挖掘算法及其應用研究

  更多相關文章： 復雜網絡 社區(qū)挖掘 擴展模塊度密度 進化算法 文化基因算法

【摘要】：生活中,可以用網絡來表示大量的復雜系統(tǒng),比如說,朋友關系網絡,交通運輸網絡,因特網,電話線路網絡,新陳代謝網絡,食物鏈網絡等。近些年來,復雜網絡成為了一個研究熱點,吸引了越來越多的國內外各個領域的研究人員的關注。在早期的研究中,發(fā)現(xiàn)復雜網絡具有小世界特性和無標度特性,但在后續(xù)的研究中,研究人員還發(fā)現(xiàn)復雜網絡還具有極其重要的社區(qū)結構特性,社區(qū)結構定義為:同一社區(qū)內的節(jié)點之間的連接比較緊密,不同社區(qū)之間的連接比較稀疏。挖掘復雜網絡中的社區(qū)結構,我們可以更好的分析網絡的結構,從而理解網絡的功能。此外,還有利于我們發(fā)現(xiàn)網絡中潛在的規(guī)律進而可以對網絡的行為做出預測,故社區(qū)挖掘具有十分重要的意義以及廣泛的應用前景。為了研究復雜網絡,研究人員提出了許多社區(qū)挖掘算法,這些算法總的來說可以歸為以下三類:基于圖分割的方法,基于層次聚類的方法和基于模塊度(modularity)優(yōu)化的方法,在這三類方法中,研究人員比較關注的是基于模塊度優(yōu)化的方法。模塊度是Newman和Girvan提出來的,它是一個用于衡量網絡社區(qū)劃分質量的目標函數(shù)。通常來說,得到的模塊度值越大,劃分得到的社區(qū)結構也會越明顯。文化基因算法(Memetic algorithm)最近在進化計算領域里受到了很多研究人員的關注,它除了對種群的全局搜索還具有對個體的局部啟發(fā)式搜索,這兩者的結合使其在解決某些問題的搜索效率上要比傳統(tǒng)的遺傳算法高。利用文化基因算法的優(yōu)點,將其應用于復雜網絡社區(qū)挖掘中。本文所做的主要工作如下:(1)研究了使用基于模塊度優(yōu)化的方法挖掘出的社區(qū)結構會存在分辨率限制的問題,我們通過采用一個新的目標函數(shù)——擴展模塊度密度(general modularity density)來解決這個問題,該目標函數(shù)可以通過調節(jié)里面的參數(shù)來解決分辨率限制問題。(2)在研究文化基因算法(Memetic algorithm)基本理論的基礎上,提出了一種可應用于復雜網絡社區(qū)挖掘的文化基因算法。我們將復雜網絡社區(qū)挖掘問題看成是一個單目標優(yōu)化問題,把模塊度Q和擴展模塊度密度作為目標函數(shù),并采用文化基因算法MA-Net分別優(yōu)化這兩個目標,得到了基于MA-Net框架的兩種社區(qū)挖掘算法:MA-Net(Q)和MA-Net()。接著,我們在人工合成網絡和真實世界網絡中進行了實驗,實驗表明,帶有局部搜索策略的文化基因算法相比于傳統(tǒng)的遺傳算法具有收斂速度快,不容易陷入局部最優(yōu),而且挖掘出的網絡社區(qū)準確度比傳統(tǒng)遺傳算法更高的優(yōu)點。最后,通過與GN算法比較,驗證了本文的算法是有效的。
【關鍵詞】：復雜網絡 社區(qū)挖掘 擴展模塊度密度 進化算法 文化基因算法
【學位授予單位】：華南理工大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP18;O157.5
【目錄】：

• 摘要5-7
• Abstract7-11
• 第一章 緒論11-16
• 1.1 研究背景和意義11-13
• 1.2 國內外研究現(xiàn)狀13-14
• 1.3 本文的主要工作及內容安排14-16
• 第二章 常見的幾種復雜網絡社區(qū)挖掘算法16-28
• 2.1 復雜網絡概述16-20
• 2.1.1 復雜網絡的圖表示16-17
• 2.1.2 復雜網絡的特性17-20
• 2.1.2.1 小世界特性17-18
• 2.1.2.2 無標度特性18
• 2.1.2.3 社區(qū)結構特性18-20
• 2.2 復雜網絡社區(qū)挖掘常見的幾種算法20-28
• 2.2.1 基于圖分割的方法20-22
• 2.2.1.1 Kernighan-Lin算法20-21
• 2.2.1.2 基于Laplace矩陣的譜平分法21-22
• 2.2.2 基于層次聚類的方法22-25
• 2.2.2.1 分裂方法23-24
• 2.2.2.2 凝聚方法24-25
• 2.2.3 基于模塊度優(yōu)化的算法25-28
• 2.2.3.1 模塊度的定義25-26
• 2.2.3.2 基于模塊度優(yōu)化的算法26-28
• 第三章 基于文化基因算法的復雜網絡社區(qū)挖掘28-40
• 3.1 引言28
• 3.2 文化基因算法概述28-30
• 3.3 模塊度的缺陷30-32
• 3.4 模塊度密度的概念32-33
• 3.5 一種應用于復雜網絡社區(qū)挖掘的文化基因算法33-40
• 第四章 算法驗證與分析40-59
• 4.1 引言40
• 4.2 評價標準40-41
• 4.3 仿真實驗及結果分析41-58
• 4.3.1 人工合成網絡實驗41-46
• 4.3.2 真實世界網絡實驗46-58
• 4.4 本章小結58-59
• 第五章 總結與展望59-62
• 5.1 總結59-60
• 5.2 展望60-62
• 參考文獻62-67
• 攻讀碩士學位期間取得的研究成果67-68
• 致謝68-69
• 附件69

【相似文獻】

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

1 蔚承建,何振亞;改進的進化計算及其應用[J];自動化學報;1998年02期

2 陸榮雙,曾璐,楊文龍;模擬進化計算理論及設計方法[J];礦山機械;2005年02期

3 郝寧湘;進化計算及其哲學研究[J];自然辯證法研究;2003年11期

4 魏敏潔;一種進化計算的抽象機器模型[J];計算技術與自動化;1998年03期

5 劉健勤,魏敏潔;進化計算的可計算性[J];計算技術與自動化;1998年03期

6 劉健勤，魏敏潔，劉其興，蔡自興;基于信息論測度的進化計算策略[J];中南工業(yè)大學學報;1996年03期

7 袁麗華;黎明;李軍華;;基于優(yōu)良育種的進化計算[J];系統(tǒng)工程;2007年07期

8 韓泉葉;黨建武;趙庶旭;;人類進化特征及模型研究[J];計算機工程與設計;2008年01期

9 侯廣坤,李明;自動布局問題的進化計算算法[J];中山大學學報(自然科學版);2001年02期

10 劉進;;進化計算在計算機輔助概念設計中的應用[J];科技信息(科學教研);2007年32期

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

1 孫承意;王皖貞;賈鴻雁;;思維進化計算的產生與進展[A];2001年中國智能自動化會議論文集（上冊）[C];2001年

2 柯益華;胡學姝;;油氣田產量預報Г模型參數(shù)估計的進化計算[A];2001年中國智能自動化會議論文集（下冊）[C];2001年

3 邵桂芳;李祖樞;陳桂強;;基于進化計算的控制結構設計方法[A];2007年中國智能自動化會議論文集[C];2007年

4 劉第楷;徐家云;李桂青;;進化計算理論在結構控制中的應用研究[A];第六屆全國結構工程學術會議論文集（第一卷）[C];1997年

5 趙清杰;楊波;;基于進化計算的BP網權值訓練算法及其應用探討[A];1998年中國智能自動化學術會議論文集（下冊）[C];1998年

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

1 楊海軍;進化計算中的模式理論、涌現(xiàn)及應用研究[D];天津大學;2004年

2 陳得寶;進化計算中的若干問題及應用研究[D];南京理工大學;2008年

3 王帥強;基于進化計算的行為模型自動精化和排序學習方法的研究[D];山東大學;2009年

4 王志春;基于進化計算的復雜分類算法研究及應用[D];天津大學;2010年

5 薛明志;進化計算與小波分析若干問題研究[D];西安電子科技大學;2004年

6 季偉東;進化計算優(yōu)化前向神經網絡的學習方法研究[D];東北林業(yè)大學;2013年

7 陳昊;動態(tài)環(huán)境下進化計算的研究[D];南京航空航天大學;2011年

8 劉軍萬;微陣列基因表達數(shù)據(jù)雙聚類的多目標進化計算技術研究[D];國防科學技術大學;2009年

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

1 李佳家;基于進化計算的社區(qū)挖掘算法及其應用研究[D];華南理工大學;2016年

2 章潔;進化計算的研究及其在自適應濾波中的應用[D];電子科技大學;2005年

3 王麗愛;研究思維進化計算的多峰優(yōu)化性能及研究算法參數(shù)對效率的影響[D];太原理工大學;2004年

4 彭偉民;基于線性變換的適應度函數(shù)及機器人進化計算研究[D];廣東工業(yè)大學;2006年

5 王俊麗;思維進化計算——搜索算法的開發(fā)和算法性能的分析[D];太原理工大學;2003年

6 陳珂;進化計算技術在手機造型設計及評價中的應用研究[D];山東師范大學;2008年

7 弓劍軍;并行思維進化計算的性能分析[D];太原理工大學;2004年

8 賈美麗;并行思維進化計算的實現(xiàn)[D];太原理工大學;2004年

9 陳偉;進化計算在優(yōu)化問題中的應用[D];武漢理工大學;2010年

10 劉福敏;基于進化計算的動漫造型研究與實現(xiàn)[D];山東師范大學;2010年

，

本文編號：542246