【摘要】：社會網(wǎng)絡(luò)(SNs)的研究是近年來的熱點�，F(xiàn)實世界中,通常情況下實體和它們之間存在的關(guān)系可以由各種社會網(wǎng)絡(luò)代替。比如朋友關(guān)系網(wǎng),新陳代謝網(wǎng)絡(luò)等。實體抽象為社會網(wǎng)絡(luò)的節(jié)點,它們之間的關(guān)系則是社會網(wǎng)絡(luò)的連邊。隨著對社會網(wǎng)絡(luò)研究的不斷深入,研究者發(fā)現(xiàn)大多數(shù)社會網(wǎng)絡(luò)具有社區(qū)結(jié)構(gòu)的特征,即社會網(wǎng)絡(luò)可以分為一定數(shù)量并且規(guī)模大小不定的社區(qū)。通常,對于社會網(wǎng)絡(luò)的一對節(jié)點,它們之間更大的連接強度意味著這對節(jié)點在同一社區(qū)的可能性越大。特別的,如果一個社會網(wǎng)絡(luò)中既存在正連邊又存在負連邊,那么該網(wǎng)絡(luò)稱為符號社會網(wǎng)絡(luò);如果社區(qū)結(jié)構(gòu)中存在共享節(jié)點的社區(qū),那么社會網(wǎng)絡(luò)帶有重疊社區(qū)。盡管目前出現(xiàn)了很多社區(qū)檢測算法,但大多數(shù)都是針對無符號和不存在重疊社區(qū)結(jié)構(gòu)的社會網(wǎng)絡(luò)。顯然,符號社會網(wǎng)絡(luò)和帶有重疊社區(qū)的社會網(wǎng)絡(luò)能更有效地表示現(xiàn)實世界的各種網(wǎng)絡(luò),更符合現(xiàn)實意義。在符號社會網(wǎng)絡(luò)中,社區(qū)結(jié)構(gòu)的劃分不僅要考慮連接強度,還要依據(jù)連接的屬性。在帶有重疊社區(qū)的社會網(wǎng)絡(luò)中,如何有效表示重疊節(jié)點是個難題。為了更好的檢測符號社會網(wǎng)絡(luò),和具有重疊社區(qū)結(jié)構(gòu)的社會網(wǎng)絡(luò),同時考慮現(xiàn)實世界社會網(wǎng)絡(luò)存在噪音的問題,本文完成以下研究內(nèi)容從而設(shè)計針對以上兩種類型社會網(wǎng)絡(luò)的社區(qū)檢測算法。(1)提出混合符號相似度和網(wǎng)絡(luò)節(jié)點間固有連接權(quán)重來定義節(jié)點的連接強度用于符號社會網(wǎng)絡(luò)社區(qū)檢測。首先,本文的節(jié)點連接強度克服了僅使用符號相似度不適用于稀疏網(wǎng)絡(luò)的缺陷和單使用節(jié)點連接權(quán)重容易被噪音干擾的弊端。同時基于本文定義的節(jié)點連接強度設(shè)計的社區(qū)緊致度在初始化時生成更有社區(qū)結(jié)構(gòu)意義的種群,并在進化過程中發(fā)揮指導基因是否發(fā)生變異的作用。然后,結(jié)合更為高效的多目標優(yōu)化算法CAEA,實現(xiàn)符號網(wǎng)絡(luò)社區(qū)檢測算法。(2)結(jié)合CAEA與最大團表示機制對社會網(wǎng)絡(luò)重疊社區(qū)檢測。借助于分解的思想,MOEA/D將一個多目標優(yōu)化問題分解成多個單目標優(yōu)化子問題,并通過種群進化同時優(yōu)化這些子問題。與MOEA/D不同,CAEA不僅將多目標優(yōu)化問題分解為多個規(guī)模的子問題,而且還給每個子問題分配一個獨有的決策子區(qū)域。此外,每個子問題都使用錐形區(qū)域指示器作為其標量目標,在其關(guān)聯(lián)的決策子集中找到一個局部非支配解。實踐表明,CAEA算法擁有更好的效果和更高的效率。將團和最大團應(yīng)用在社區(qū)檢測上有效地利用了團之間共享節(jié)點恰符合重疊社區(qū)結(jié)構(gòu)的屬性。在預(yù)處理階段找出所有的最大團,將最大團設(shè)為新的節(jié)點,然后使用簡單個體直接表示機制便可以進行重疊社區(qū)檢測。同時,針對目標函數(shù)尺度不同導致的進化偏向大尺度目標,進而損失種群多樣性的問題,本文設(shè)計了目標函數(shù)的離差標準化。(3)分別在真實世界網(wǎng)絡(luò),人工合成網(wǎng)絡(luò)(即帶噪音的網(wǎng)絡(luò))兩類網(wǎng)絡(luò)對兩個算法的性能進行全面評估。其中人工合成網(wǎng)絡(luò)實驗使用多種參數(shù)組合進行了較為系統(tǒng)的實驗,這些實驗包含較大規(guī)模,較高噪音時對兩個算法的檢驗。并與性能表現(xiàn)良好的MEAs-SN,louvain和實驗MCMOEA進行系統(tǒng)對比,以驗證本文算法在社區(qū)檢測問題上的有效性和高效性。在人工合成網(wǎng)絡(luò)和現(xiàn)實世界網(wǎng)絡(luò)的實驗結(jié)果表明,本文設(shè)計的兩個基于錐面積演化算法的社會網(wǎng)絡(luò)多目標社區(qū)檢測算法在相應(yīng)類型的社會網(wǎng)絡(luò)社區(qū)檢測問題上,不僅能夠獲得優(yōu)異的檢測結(jié)果,同時還擁有較高計算效率和魯棒性。
【學位授予單位】：華南理工大學
【學位級別】：碩士
【學位授予年份】：2019
【分類號】：TP393.09;TP301.6

【參考文獻】

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

1 林友芳;王天宇;唐銳;周元煒;黃厚寬;;一種有效的社會網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)模型和算法[J];計算機研究與發(fā)展;2012年02期

本文編號：2735333