復(fù)雜網(wǎng)絡(luò)是對(duì)現(xiàn)實(shí)復(fù)雜系統(tǒng)的抽象化描述,如社交網(wǎng)絡(luò)、科學(xué)合作網(wǎng)絡(luò)、生物蛋白系統(tǒng)等。社區(qū)是用于描述復(fù)雜網(wǎng)絡(luò)中連接緊密的節(jié)點(diǎn)簇或模塊,復(fù)雜網(wǎng)絡(luò)的社區(qū)檢測(cè)就是利用網(wǎng)絡(luò)中特殊的拓?fù)浣Y(jié)構(gòu)來(lái)識(shí)別這些連接緊密的節(jié)點(diǎn)簇,有時(shí)也被稱為復(fù)雜網(wǎng)絡(luò)的聚類(lèi)。對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行社區(qū)檢測(cè),能夠幫助人們發(fā)現(xiàn)網(wǎng)絡(luò)中潛在的結(jié)構(gòu)模式,并進(jìn)一步理解網(wǎng)絡(luò)的組織功能。近些年來(lái),研究者從不同的角度設(shè)計(jì)出許多復(fù)雜網(wǎng)絡(luò)的社區(qū)檢測(cè)算法,但是大多數(shù)算法都是針對(duì)于單一的網(wǎng)絡(luò)結(jié)構(gòu),即無(wú)符號(hào)復(fù)雜網(wǎng)絡(luò)。然而,現(xiàn)實(shí)的復(fù)雜系統(tǒng)往往涵蓋著多種特征,如符號(hào)網(wǎng)絡(luò)可以描述實(shí)體之間的多種關(guān)系,而屬性網(wǎng)絡(luò)不僅可以描述實(shí)體之間的關(guān)系,還可以描述實(shí)體的屬性或特征。這些網(wǎng)絡(luò)能夠更真實(shí)地描繪現(xiàn)實(shí)系統(tǒng)的復(fù)雜性,給社區(qū)檢測(cè)問(wèn)題帶來(lái)更多信息的同時(shí)也帶來(lái)了更大挑戰(zhàn)。此外,充分利用節(jié)點(diǎn)的鄰域信息,更為針對(duì)性地設(shè)計(jì)出合理的操作步驟,能夠更大程度上提高算法的檢測(cè)精度。針對(duì)以上現(xiàn)存算法普遍存在的問(wèn)題,本文對(duì)不同類(lèi)型的網(wǎng)絡(luò)進(jìn)行深層次研究。設(shè)計(jì)出具體的解決方案如下:1)提出一種基于節(jié)點(diǎn)鄰域信息與三步策略的社區(qū)檢測(cè)算法。首先,算法將K近鄰思想引入標(biāo)簽傳播算法,并提出網(wǎng)絡(luò)的預(yù)劃分策略。該策略充分考慮節(jié)點(diǎn)間的親近度,并且克服了標(biāo)簽傳播算法在社區(qū)結(jié)構(gòu)較為模糊的情況下無(wú)法識(shí)別社區(qū)的缺陷,使得算法初期能夠精確識(shí)別局部連接緊密的子社區(qū)。其次,在預(yù)處理的基礎(chǔ)上設(shè)計(jì)了基于社區(qū)互隸屬度的子社區(qū)融合策略,并對(duì)親密度高的子社區(qū)進(jìn)行有效合并。最后,一種精制策略被用來(lái)對(duì)誤劃分的節(jié)點(diǎn)進(jìn)行重劃分。算法對(duì)初始點(diǎn)個(gè)數(shù)及迭代次數(shù)的依賴性很小,因此能夠節(jié)省大量時(shí)間成本,適合大規(guī)模網(wǎng)絡(luò)的社區(qū)檢測(cè)問(wèn)題。2)提出一種基于K節(jié)點(diǎn)更新策略與相似度矩陣的多目標(biāo)社區(qū)檢測(cè)算法。首先,建立泛化的相似度函數(shù)來(lái)計(jì)算無(wú)符號(hào)網(wǎng)絡(luò)或符號(hào)網(wǎng)絡(luò)的相似度矩陣,并根據(jù)節(jié)點(diǎn)的相似度矩陣設(shè)計(jì)了一種預(yù)劃分技術(shù),這種預(yù)劃分技術(shù)僅僅考慮相似度值較高的部分節(jié)點(diǎn),能夠有效地避免噪聲節(jié)點(diǎn)對(duì)標(biāo)簽更新過(guò)程的影響,因此可以將連接緊密的節(jié)點(diǎn)迅速聚集成局部子社區(qū)。其次,交叉合并算子被設(shè)計(jì)并用于合并預(yù)處理策略所得到的子社區(qū),以及基于相似度矩陣的變異算子被用于調(diào)整邊界節(jié)點(diǎn)所屬的社區(qū)。最后,構(gòu)建多目標(biāo)優(yōu)化模型并用于處理不同類(lèi)型的網(wǎng)絡(luò)。因此,算法能夠處理無(wú)符號(hào)網(wǎng)絡(luò)與符號(hào)網(wǎng)絡(luò)的社區(qū)檢測(cè)問(wèn)題。3)提出一種基于邊結(jié)構(gòu)與節(jié)點(diǎn)屬性的多目標(biāo)離散粒子群社區(qū)檢測(cè)算法。首先,該算法計(jì)算邊結(jié)構(gòu)的相似性矩陣與節(jié)點(diǎn)的屬性相似度矩陣,通過(guò)混合參數(shù)將兩者結(jié)合得到網(wǎng)絡(luò)的混合相似度矩陣,并基于此設(shè)計(jì)一種更新鄰居節(jié)點(diǎn)標(biāo)簽的初始化策略。其次,考慮到粒子群算法的易操作性以及其時(shí)間效率較高,該算法首次將多目標(biāo)離散粒子群算法引入屬性網(wǎng)絡(luò)中。最后,設(shè)計(jì)屬性網(wǎng)絡(luò)的平均屬性相似度函數(shù)并用于構(gòu)建多目標(biāo)優(yōu)化模型,能夠兼顧社區(qū)內(nèi)部節(jié)點(diǎn)連接緊密的同時(shí)使得社區(qū)內(nèi)節(jié)點(diǎn)屬性同質(zhì)化程度高。
【學(xué)位單位】：西安電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2018
【中圖分類(lèi)】：O157.5;TP301.6
【部分圖文】：

西安電子科技大學(xué)碩士學(xué)位論文8圖2.1 算法的遺傳表示與解碼過(guò)程算法的編碼與解碼過(guò)程如圖 2.1 所示。該圖例展示了在算法初始化階段，TJA-net賦予每個(gè)節(jié)點(diǎn)一個(gè)唯一的標(biāo)簽，代表著該節(jié)點(diǎn)所屬的社區(qū)標(biāo)簽。通過(guò)解碼，擁有相同標(biāo)簽值的節(jié)點(diǎn)將被劃分到同一社區(qū)。如同圖 2.1 所示，圖中用不同的顏色與形狀來(lái)表示不同的社區(qū)，由于節(jié)點(diǎn)集{1, 2, 3, 4, 5}具有相同的社區(qū)標(biāo)簽而被劃分為社區(qū) 1；同理，節(jié)點(diǎn)集{6, 7, 8, 9}被劃分到社區(qū) 2 中。2.2.2預(yù)處理策略在介紹 TJA-net 算法的預(yù)處理策略之前，本節(jié)首先給出一些相關(guān)背景知識(shí)。KNN算法[47]是機(jī)器學(xué)習(xí)算法中比較成熟且較為簡(jiǎn)單的分類(lèi)算法之一，它是由 Cover 與 Hart于 1967 年提出的用于解決分類(lèi)問(wèn)題的算法。直觀來(lái)講

(a) 社區(qū)檢測(cè)示例圖 (b) 利用 ILPA 完成圖圖2.2 ILPA 預(yù)處理實(shí)例為了更好的解釋 ILPA 與 LPA 的不同之處，本章使用圖 2.2 來(lái)進(jìn)行說(shuō)明。由于 (a) 中的節(jié)點(diǎn)集{v1, v2, v3}屬于社區(qū) C1 而被標(biāo)記為“1”，而節(jié)點(diǎn)集{ v5, v6, v7, v8于社區(qū) C2，被標(biāo)記為“2”。此時(shí)的節(jié)點(diǎn) v4為待處理節(jié)點(diǎn)。利用 LPA 對(duì)節(jié)點(diǎn) v4進(jìn)類(lèi)，可以看出此時(shí)節(jié)點(diǎn) v4與社區(qū) C1、社區(qū) C2 的連接數(shù)相等。因此，利用 LPA對(duì)此時(shí)的節(jié)點(diǎn) v4進(jìn)行聚類(lèi)。與此相比，ILPA 則首先計(jì)算節(jié)點(diǎn) v4與其鄰接節(jié)點(diǎn){v1 v5, v7, v8}的親密程度，計(jì)算結(jié)果如表 2.2 所示。示例中，設(shè)置 K = 3，計(jì)算得到 v4最親近的節(jié)點(diǎn)集為{v1, v2, v3}，其類(lèi)別最多的社區(qū)標(biāo)簽為 1，因此將節(jié)點(diǎn) v4劃社區(qū) C1，如圖 2.1 (b)所示。表2.2 節(jié)點(diǎn) v4與其鄰接節(jié)點(diǎn)的親近度鄰接節(jié)點(diǎn) v1v2v3v5v7v社區(qū)標(biāo)簽 '1' '1' '1' '2' '2' '2親近度值 3 3 3 2 3 2

合的閾值δ = 1，算法的迭代次數(shù)iterm = 5，目標(biāo)函數(shù)中參數(shù)λ的取值為{0.2, 0.3, 0.4, ...,1.0}。則算法運(yùn)行 30 次所得到的最佳 NMI 值如圖 2.3 所示。圖2.3 算法在 GN 擴(kuò)展網(wǎng)絡(luò)上所得的 NMI 值對(duì)比從圖 2.3 中可以看出，TJA-net 算法與 Memetic-net 算法在 0.2 ≤ λ ≤ 0.5 時(shí)的效果基本相同，而 CSA-net 算法在 0.2 ≤ λ ≤ 0.4 且 γ = 0.4 時(shí)要稍微優(yōu)于其他算法。此外，TJA_v-net 算法在 λ ≤ 0.6 時(shí)表現(xiàn)得不如其他算法，但是在 0.8 ≤ λ ≤ 1.0 時(shí)，無(wú)論是TJA_v-net算法還是TJA-net算法均要比CSA-net算法和Memetic-net算法表現(xiàn)得優(yōu)秀。需要注意的是，即使當(dāng)社區(qū)結(jié)構(gòu)比較明顯時(shí)，即 0.2 ≤ γ ≤ 0.3，利用了 LPA 算法作為預(yù)處理策略的 TJA_v-net 算法也無(wú)法檢測(cè)出真實(shí)的社區(qū)結(jié)構(gòu)
【相似文獻(xiàn)】

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

1 張明紅;佘廉;耿波;;基于情景的結(jié)構(gòu)化突發(fā)事件相似度研究[J];中國(guó)管理科學(xué);2017年01期

2 陳葉斐;張學(xué)軍;黃衛(wèi)東;;基于干擾相似度的多話題演化模型[J];電信科學(xué);2017年09期

3 任雪利;代余彪;;軟件相似度在成本估算中的應(yīng)用[J];計(jì)算機(jī)應(yīng)用與軟件;2015年06期

4 譚明超;刁興春;曹建軍;馮徑;;一種基于函數(shù)依賴的屬性相似度調(diào)整算法[J];上海交通大學(xué)學(xué)報(bào);2015年08期

5 陳立鳳;;河馬找親戚[J];學(xué)生之友(童花果);2016年12期

6 周嫻莉;;十個(gè)中文流行語(yǔ)翻譯[J];初中生輔導(dǎo);2016年36期

7 杜碧涵;;母愛(ài)[J];少年月刊;2017年05期

8 張呈宇;;熱點(diǎn)話題相似度常用算法比較[J];好家長(zhǎng);2017年12期

9 仇麗青;陳卓艷;;基于共同鄰居相似度的社區(qū)發(fā)現(xiàn)算法[J];信息系統(tǒng)工程;2014年05期

10 詹雪艷;林兆洲;段天璇;李磊;喬延江;;色譜指紋圖譜相似度方法的適應(yīng)性研究[J];中國(guó)中醫(yī)藥信息雜志;2012年05期

相關(guān)博士學(xué)位論文 前10條

1 高欣健;多模態(tài)相似度學(xué)習(xí)方法研究[D];合肥工業(yè)大學(xué);2017年

2 夏云慶;IHSMTS系統(tǒng)中啟發(fā)式類(lèi)比翻譯處理機(jī)制（HATM）的設(shè)計(jì)與實(shí)現(xiàn)[D];中國(guó)科學(xué)院研究生院（計(jì)算技術(shù)研究所）;2001年

3 武威;異質(zhì)數(shù)據(jù)相似度學(xué)習(xí)及其在網(wǎng)絡(luò)搜索中的應(yīng)用[D];北京大學(xué);2012年

4 張明西;信息網(wǎng)絡(luò)中的相似度搜索問(wèn)題研究[D];復(fù)旦大學(xué);2013年

5 朱娜斐;基于RTT相似度的網(wǎng)絡(luò)延遲估測(cè)理論和方法[D];北京工業(yè)大學(xué);2012年

6 錢(qián)鵬飛;基于模糊相似度的異構(gòu)本體映射、合并及校驗(yàn)方法的研究[D];上海交通大學(xué);2008年

7 朱笑塵;異質(zhì)過(guò)程數(shù)據(jù)集成與修復(fù)[D];清華大學(xué);2015年

8 賈連印;內(nèi)存數(shù)據(jù)庫(kù)中集合相似度及集合包含問(wèn)題的研究[D];華南理工大學(xué);2012年

9 崔曉蘭;面向在線抱怨自動(dòng)處理的推薦方法研究[D];華中科技大學(xué);2017年

10 馬海平;基于概率生成模型的相似度建模技術(shù)研究及應(yīng)用[D];中國(guó)科學(xué)技術(shù)大學(xué);2013年

相關(guān)碩士學(xué)位論文 前10條

1 劉佳雯;語(yǔ)句相似度匹配在自動(dòng)問(wèn)答系統(tǒng)中的應(yīng)用與實(shí)現(xiàn)[D];南京郵電大學(xué);2018年

2 邊青全;基于動(dòng)力學(xué)模型的網(wǎng)絡(luò)社團(tuán)檢測(cè)算法研究[D];西安電子科技大學(xué);2018年

3 程亞男;在線問(wèn)答社區(qū)意見(jiàn)型問(wèn)題的答案摘要研究[D];大連理工大學(xué);2018年

4 戴東慶;魯棒局部保持投影技術(shù)研究及應(yīng)用[D];西安電子科技大學(xué);2018年

5 劉歡;基于節(jié)點(diǎn)鄰域信息與相似度矩陣的社區(qū)檢測(cè)[D];西安電子科技大學(xué);2018年

6 方敏;基于節(jié)點(diǎn)相似度的線要素匹配方法設(shè)計(jì)[D];北京建筑大學(xué);2018年

7 張學(xué)理;基于多因子標(biāo)簽相似度的標(biāo)簽聚類(lèi)算法的研究[D];遼寧大學(xué);2018年

8 李凱翔;產(chǎn)科知識(shí)圖譜的構(gòu)建與研究[D];鄭州大學(xué);2018年

9 李超男;基于節(jié)點(diǎn)相似度的社會(huì)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)的算法研究[D];重慶師范大學(xué);2018年

10 花凌鋒;面向位置的移動(dòng)新聞推薦研究[D];安徽理工大學(xué);2018年

本文編號(hào)：2891438