本文選題：復(fù)雜網(wǎng)絡(luò)　切入點(diǎn)：社區(qū)發(fā)現(xiàn)　出處：《吉林大學(xué)》2016年博士論文

【摘要】：現(xiàn)實(shí)世界的許多復(fù)雜系統(tǒng)都可以表示成復(fù)雜網(wǎng)絡(luò),如社會(huì)網(wǎng)、生物網(wǎng)、技術(shù)網(wǎng)等。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)中的一個(gè)重要屬性,它表明網(wǎng)絡(luò)中的節(jié)點(diǎn)具有集聚化特性。網(wǎng)絡(luò)具有的復(fù)雜性、多樣性、動(dòng)態(tài)性等特點(diǎn)會(huì)使發(fā)現(xiàn)社區(qū)結(jié)構(gòu)的研究工作變得更加復(fù)雜,也使該工作成為最具挑戰(zhàn)的課題任務(wù)之一。檢測(cè)社區(qū)結(jié)構(gòu)可用于分析和理解網(wǎng)絡(luò)中的結(jié)構(gòu)功能、發(fā)現(xiàn)網(wǎng)絡(luò)中的隱含模式、預(yù)測(cè)網(wǎng)絡(luò)的動(dòng)態(tài)發(fā)展規(guī)律,乃至對(duì)于網(wǎng)絡(luò)的認(rèn)知和利用具有非常重要的意義。在解決社會(huì)網(wǎng)絡(luò)、無(wú)線傳感器網(wǎng)絡(luò)、郵件交互網(wǎng)絡(luò)等實(shí)際問(wèn)題中,社區(qū)發(fā)現(xiàn)的研究工作是網(wǎng)絡(luò)分析中的重要組成部分。雖然目前諸多社區(qū)結(jié)構(gòu)挖掘算法已經(jīng)被廣泛應(yīng)用于網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問(wèn)題,但如何能夠在不需要先驗(yàn)知識(shí)的基礎(chǔ)上,既降低算法的復(fù)雜度又提高社區(qū)劃分結(jié)果的準(zhǔn)確度,一直是社區(qū)發(fā)現(xiàn)算法不斷發(fā)展和研究的方向。本文研究復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)、重疊社區(qū)發(fā)現(xiàn)、動(dòng)態(tài)社區(qū)發(fā)現(xiàn)三個(gè)方面的內(nèi)容,主要貢獻(xiàn)與創(chuàng)新工作如下:1.為了解決基于模塊度優(yōu)化的社區(qū)發(fā)現(xiàn)方法存在的分辨率限制問(wèn)題,本文將社區(qū)發(fā)現(xiàn)看做是一個(gè)多目標(biāo)優(yōu)化問(wèn)題,首次利用布谷鳥(niǎo)算法求解社區(qū)發(fā)現(xiàn)問(wèn)題并提出了一種基于多目標(biāo)布谷鳥(niǎo)優(yōu)化的社區(qū)發(fā)現(xiàn)方法(MDCL)。該算法通過(guò)同時(shí)優(yōu)化兩個(gè)互相沖突的目標(biāo)函數(shù)Negative Ratio Association和Ratio Cut來(lái)控制網(wǎng)絡(luò)中的社區(qū)規(guī)模,同時(shí),MDCL設(shè)計(jì)了滿足要求的離散形式位置更新公式和放棄操作算子,并采用局部搜索和克隆策略提高種群質(zhì)量。在人工和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上驗(yàn)證了算法的有效性,實(shí)驗(yàn)結(jié)果表明MDCL方法相比于其他算法可以挖掘出高質(zhì)量的社區(qū)結(jié)構(gòu)。2.本文提出了一種基于蟻群算法的重疊社區(qū)發(fā)現(xiàn)方法(Ant CBO)。該算法主要包括螞蟻初始化、螞蟻移動(dòng)和后處理三個(gè)模塊。算法在初始化階段確定螞蟻位置和各節(jié)點(diǎn)中的初始標(biāo)簽;在移動(dòng)階段,通過(guò)螞蟻在轉(zhuǎn)移機(jī)制的啟發(fā)下自由移動(dòng)實(shí)現(xiàn)各個(gè)節(jié)點(diǎn)中標(biāo)簽信息的更新,當(dāng)終止條件滿足時(shí)各個(gè)節(jié)點(diǎn)會(huì)得到相應(yīng)的標(biāo)簽序列;最后,通過(guò)后處理策略得到網(wǎng)絡(luò)中的重疊社區(qū)劃分結(jié)果。另外,本文提出了一種求解轉(zhuǎn)移概率的啟發(fā)式信息計(jì)算方法。在人工和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果均表明,相比于其他算法,Ant CBO算法具有更好的性能,可以更加準(zhǔn)確地檢測(cè)出網(wǎng)絡(luò)中重疊節(jié)點(diǎn)和重疊社區(qū)結(jié)構(gòu)。3.為解決基于邊聚類算法導(dǎo)致社區(qū)結(jié)構(gòu)出現(xiàn)節(jié)點(diǎn)過(guò)度重疊的問(wèn)題,同時(shí)為有效地提高重疊社團(tuán)劃分的準(zhǔn)確性,本文提出了一種基于密度邊聚類的重疊社區(qū)發(fā)現(xiàn)算法(DBLC)。該算法在邊擴(kuò)展階段基于核心密度可達(dá)概念對(duì)核心邊進(jìn)行初始聚類得到若干邊社團(tuán),然后通過(guò)更新策略將未分類的邊劃分至與之相似度最高的社團(tuán)中。同時(shí),我們提出了一種計(jì)算邊與邊相似度的方法�；谌斯�(shù)據(jù)集和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,該算法在挖掘重疊社區(qū)結(jié)構(gòu)和重疊節(jié)點(diǎn)方面性能表現(xiàn)更優(yōu)。4.靜態(tài)網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)研究工作會(huì)忽略網(wǎng)絡(luò)的動(dòng)態(tài)性,難以識(shí)別網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的變化,而動(dòng)態(tài)社區(qū)發(fā)現(xiàn)算法研究可有效地檢測(cè)動(dòng)態(tài)社區(qū)結(jié)構(gòu)。本文提出了一種基于多目標(biāo)生物地理優(yōu)化動(dòng)態(tài)社區(qū)發(fā)現(xiàn)算法(MBBOD)。該方法采用分解機(jī)制同時(shí)優(yōu)化分別表示快照代價(jià)的目標(biāo)函數(shù)模塊度和表示時(shí)間代價(jià)的目標(biāo)函數(shù)標(biāo)準(zhǔn)化互信息,提出了一種新的排序策略并利用該策略比較生物地理優(yōu)化算法中棲息地質(zhì)量?jī)?yōu)劣進(jìn)而獲取物種數(shù)目。另外,本文設(shè)計(jì)了針對(duì)特定問(wèn)題的遷移模型和變異模型以提高算法的有效性。實(shí)驗(yàn)結(jié)果表明,MBBOD算法與DYNMOGA和Facet Net算法相比具有較好的性能,可以得到準(zhǔn)確度更高的社區(qū)劃分結(jié)果。5.基于演化聚類框架的動(dòng)態(tài)社區(qū)發(fā)現(xiàn)算法通過(guò)優(yōu)化由快照代價(jià)和時(shí)間代價(jià)組成的代價(jià)函數(shù)實(shí)現(xiàn)動(dòng)態(tài)社區(qū)發(fā)現(xiàn)。為了避免人為輸入?yún)?shù)控制快照代價(jià)和時(shí)間代價(jià)的權(quán)重限制算法性能和影響優(yōu)化結(jié)果精準(zhǔn)性的問(wèn)題,本文將動(dòng)態(tài)社區(qū)發(fā)現(xiàn)問(wèn)題轉(zhuǎn)換成多目標(biāo)優(yōu)化問(wèn)題,提出了一種基于多目標(biāo)布谷鳥(niǎo)優(yōu)化的動(dòng)態(tài)社區(qū)發(fā)現(xiàn)算法(MODCS)。算法首先采用基于有序鄰居列表的編碼方式對(duì)鳥(niǎo)巢進(jìn)行編碼,重點(diǎn)在離散布谷鳥(niǎo)框架中重定義了符合社區(qū)發(fā)現(xiàn)問(wèn)題的離散位置更新策略和放棄操作算子,最后結(jié)合擁擠距離和非占優(yōu)排序機(jī)制實(shí)現(xiàn)動(dòng)態(tài)社區(qū)發(fā)現(xiàn)。在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,MODCS算法可有效地挖掘出每個(gè)時(shí)刻的高質(zhì)量的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。
[Abstract]:......
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18;O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 韓進(jìn);;算法淺說(shuō)[J];廣西教育學(xué)院學(xué)報(bào);2008年04期

2 王貴竹;一種產(chǎn)生單向分解值的算法[J];安徽大學(xué)學(xué)報(bào)(自然科學(xué)版);2001年03期

3 高廣尚;蔣泰;;ISO 18000-6 Type C中的防沖突機(jī)制分析[J];廣西科學(xué)院學(xué)報(bào);2008年04期

4 石連栓;離散變量結(jié)構(gòu)優(yōu)化設(shè)計(jì)算法研究綜述[J];天津職業(yè)技術(shù)師范學(xué)院學(xué)報(bào);2001年01期

5 張宏哲;;FFT算法的一種改進(jìn)[J];長(zhǎng)安大學(xué)學(xué)報(bào)(自然科學(xué)版);1988年01期

6 范曉平;;最小生成樹(shù)(MST)的“分級(jí)選樹(shù)”算法[J];西南交通大學(xué)學(xué)報(bào);1983年01期

7 劉志奎;劉慶民;;零件矩形邊界框區(qū)域自動(dòng)提取算法及應(yīng)用[J];光學(xué)技術(shù);2012年02期

8 戴光明;張全元;包建全;;一種車型特征提取的新算法[J];武漢大學(xué)學(xué)報(bào)(信息科學(xué)版);2009年10期

9 李躍波;王麗珍;;AUCBoost算法處理不平衡分類問(wèn)題[J];云南大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年S2期

10 顧翔,徐克t，

本文編號(hào)：1686836