發(fā)布時(shí)間：2017-07-14 19:04

  本文關(guān)鍵詞：基于進(jìn)化計(jì)算的社區(qū)挖掘算法及其應(yīng)用研究

  更多相關(guān)文章： 復(fù)雜網(wǎng)絡(luò) 社區(qū)挖掘 擴(kuò)展模塊度密度 進(jìn)化算法 文化基因算法

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

• 摘要5-7
• Abstract7-11
• 第一章 緒論11-16
• 1.1 研究背景和意義11-13
• 1.2 國(guó)內(nèi)外研究現(xiàn)狀13-14
• 1.3 本文的主要工作及內(nèi)容安排14-16
• 第二章 常見(jiàn)的幾種復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘算法16-28
• 2.1 復(fù)雜網(wǎng)絡(luò)概述16-20
• 2.1.1 復(fù)雜網(wǎng)絡(luò)的圖表示16-17
• 2.1.2 復(fù)雜網(wǎng)絡(luò)的特性17-20
• 2.1.2.1 小世界特性17-18
• 2.1.2.2 無(wú)標(biāo)度特性18
• 2.1.2.3 社區(qū)結(jié)構(gòu)特性18-20
• 2.2 復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘常見(jiàn)的幾種算法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 基于層次聚類(lèi)的方法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
• 第三章 基于文化基因算法的復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘28-40
• 3.1 引言28
• 3.2 文化基因算法概述28-30
• 3.3 模塊度的缺陷30-32
• 3.4 模塊度密度的概念32-33
• 3.5 一種應(yīng)用于復(fù)雜網(wǎng)絡(luò)社區(qū)挖掘的文化基因算法33-40
• 第四章 算法驗(yàn)證與分析40-59
• 4.1 引言40
• 4.2 評(píng)價(jià)標(biāo)準(zhǔn)40-41
• 4.3 仿真實(shí)驗(yàn)及結(jié)果分析41-58
• 4.3.1 人工合成網(wǎng)絡(luò)實(shí)驗(yàn)41-46
• 4.3.2 真實(shí)世界網(wǎng)絡(luò)實(shí)驗(yàn)46-58
• 4.4 本章小結(jié)58-59
• 第五章 總結(jié)與展望59-62
• 5.1 總結(jié)59-60
• 5.2 展望60-62
• 參考文獻(xiàn)62-67
• 攻讀碩士學(xué)位期間取得的研究成果67-68
• 致謝68-69
• 附件69

【相似文獻(xiàn)】

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

1 蔚承建,何振亞;改進(jìn)的進(jìn)化計(jì)算及其應(yīng)用[J];自動(dòng)化學(xué)報(bào);1998年02期

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

3 郝寧湘;進(jìn)化計(jì)算及其哲學(xué)研究[J];自然辯證法研究;2003年11期

4 魏敏潔;一種進(jìn)化計(jì)算的抽象機(jī)器模型[J];計(jì)算技術(shù)與自動(dòng)化;1998年03期

5 劉健勤,魏敏潔;進(jìn)化計(jì)算的可計(jì)算性[J];計(jì)算技術(shù)與自動(dòng)化;1998年03期

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

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

8 韓泉葉;黨建武;趙庶旭;;人類(lèi)進(jìn)化特征及模型研究[J];計(jì)算機(jī)工程與設(shè)計(jì);2008年01期

9 侯廣坤,李明;自動(dòng)布局問(wèn)題的進(jìn)化計(jì)算算法[J];中山大學(xué)學(xué)報(bào)(自然科學(xué)版);2001年02期

10 劉進(jìn);;進(jìn)化計(jì)算在計(jì)算機(jī)輔助概念設(shè)計(jì)中的應(yīng)用[J];科技信息(科學(xué)教研);2007年32期

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

1 孫承意;王皖貞;賈鴻雁;;思維進(jìn)化計(jì)算的產(chǎn)生與進(jìn)展[A];2001年中國(guó)智能自動(dòng)化會(huì)議論文集（上冊(cè)）[C];2001年

2 柯益華;胡學(xué)姝;;油氣田產(chǎn)量預(yù)報(bào)Г模型參數(shù)估計(jì)的進(jìn)化計(jì)算[A];2001年中國(guó)智能自動(dòng)化會(huì)議論文集（下冊(cè)）[C];2001年

3 邵桂芳;李祖樞;陳桂強(qiáng);;基于進(jìn)化計(jì)算的控制結(jié)構(gòu)設(shè)計(jì)方法[A];2007年中國(guó)智能自動(dòng)化會(huì)議論文集[C];2007年

4 劉第楷;徐家云;李桂青;;進(jìn)化計(jì)算理論在結(jié)構(gòu)控制中的應(yīng)用研究[A];第六屆全國(guó)結(jié)構(gòu)工程學(xué)術(shù)會(huì)議論文集（第一卷）[C];1997年

5 趙清杰;楊波;;基于進(jìn)化計(jì)算的BP網(wǎng)權(quán)值訓(xùn)練算法及其應(yīng)用探討[A];1998年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（下冊(cè)）[C];1998年

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

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

2 陳得寶;進(jìn)化計(jì)算中的若干問(wèn)題及應(yīng)用研究[D];南京理工大學(xué);2008年

3 王帥強(qiáng);基于進(jìn)化計(jì)算的行為模型自動(dòng)精化和排序?qū)W習(xí)方法的研究[D];山東大學(xué);2009年

4 王志春;基于進(jìn)化計(jì)算的復(fù)雜分類(lèi)算法研究及應(yīng)用[D];天津大學(xué);2010年

5 薛明志;進(jìn)化計(jì)算與小波分析若干問(wèn)題研究[D];西安電子科技大學(xué);2004年

6 季偉東;進(jìn)化計(jì)算優(yōu)化前向神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)方法研究[D];東北林業(yè)大學(xué);2013年

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

8 劉軍萬(wàn);微陣列基因表達(dá)數(shù)據(jù)雙聚類(lèi)的多目標(biāo)進(jìn)化計(jì)算技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2009年

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

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

2 章潔;進(jìn)化計(jì)算的研究及其在自適應(yīng)濾波中的應(yīng)用[D];電子科技大學(xué);2005年

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

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

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

6 陳珂;進(jìn)化計(jì)算技術(shù)在手機(jī)造型設(shè)計(jì)及評(píng)價(jià)中的應(yīng)用研究[D];山東師范大學(xué);2008年

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

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

9 陳偉;進(jìn)化計(jì)算在優(yōu)化問(wèn)題中的應(yīng)用[D];武漢理工大學(xué);2010年

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

，

本文編號(hào)：542246