本文選題：社區(qū)發(fā)現(xiàn) + 多目標(biāo)進(jìn)化算法��； 參考：《北京郵電大學(xué)》2017年碩士論文

【摘要】：社區(qū)發(fā)現(xiàn)(又稱為社團(tuán)發(fā)現(xiàn))是復(fù)雜網(wǎng)絡(luò)研究的重要部分,主要目的是挖掘網(wǎng)絡(luò)中一群相互聯(lián)系緊密的節(jié)點(diǎn)組成的模塊。社區(qū)發(fā)現(xiàn)在推薦系統(tǒng),危險(xiǎn)預(yù)警,輿情分析等領(lǐng)域有著廣泛的應(yīng)用。傳統(tǒng)基于靜態(tài)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)已有大量研究,并且積累了許多優(yōu)秀的方法和參數(shù)。但是,隨著復(fù)雜網(wǎng)絡(luò)的快速發(fā)展,新的復(fù)雜網(wǎng)絡(luò)常常具有用戶數(shù)量多、群體結(jié)構(gòu)復(fù)雜、用戶社交廣泛、發(fā)展快等特點(diǎn)。傳統(tǒng)靜態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)研究已難以滿足當(dāng)前社區(qū)發(fā)現(xiàn)需求。動態(tài)重疊社區(qū)發(fā)現(xiàn)研究可以進(jìn)一步探索復(fù)雜網(wǎng)絡(luò)中社區(qū)的復(fù)雜性和動態(tài)性,是社區(qū)發(fā)現(xiàn)重要研究方向之一。本文采用一種基于分解的多目標(biāo)進(jìn)化算法(Decomposition based multi-objective evolutionary algorithm, MOEA/D)解決動態(tài)可重疊社區(qū)發(fā)現(xiàn)問題。基于MOEA/D的動態(tài)社區(qū)發(fā)現(xiàn)算法(MOEA/D based dynamic community detection algorithm ,MOEAD-DCD)同時優(yōu)化瞬時評分(Snapshot score, SC)和時間消耗(Temporal cost,TC)兩類目標(biāo)函數(shù)。SC采用社區(qū)發(fā)現(xiàn)經(jīng)典衡量指標(biāo),保證每一個時刻社區(qū)發(fā)現(xiàn)結(jié)果的準(zhǔn)確性。TC計(jì)算相鄰時刻間社區(qū)發(fā)現(xiàn)結(jié)果的相似性,保證動態(tài)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的穩(wěn)定性。針對復(fù)雜網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn),傳統(tǒng)社區(qū)發(fā)現(xiàn)往往具有較高時間復(fù)雜度,針對該問題本文采用了大量經(jīng)典策略提高算法效率。包括采用輪盤賭方法設(shè)計(jì)MOEA/D的初始化算子和進(jìn)化算子,采用前一時刻社區(qū)發(fā)現(xiàn)結(jié)果初始化當(dāng)前時刻初始解等。MOEAD-DCD采用一種改進(jìn)的基于鄰接軌跡表達(dá)的編碼方式,使得網(wǎng)絡(luò)中一個節(jié)點(diǎn)可以同時隸屬于多個不同的社區(qū)結(jié)構(gòu)。通過保留多種非支配解,MOEAD-DCD保證了社區(qū)發(fā)現(xiàn)結(jié)果多樣性,避免人為選擇多目標(biāo)函數(shù)的影響權(quán)重問題。根據(jù)文獻(xiàn)調(diào)研,本文首次將MOEA/D用于解決動態(tài)可重疊社區(qū)發(fā)現(xiàn)問題。MOEA/D算法具有較高運(yùn)行效率,能夠保證最終非支配解多樣性的特點(diǎn)。同時結(jié)合本文采用的大量改進(jìn)策略,與傳統(tǒng)社區(qū)發(fā)現(xiàn)算法相比,MOEAD-DCD能夠保證準(zhǔn)確性的同時,兼顧動態(tài)社區(qū)結(jié)果的穩(wěn)定性。計(jì)算實(shí)驗(yàn)對比驗(yàn)證了 MOEAD-DCD的有效性。
[Abstract]:Community discovery (also known as community discovery) is an important part of the research on complex networks. The main purpose of community discovery is to mine the modules composed of a group of closely connected nodes in the network. Community discovery has a wide range of applications in recommendation systems, hazard warning, public opinion analysis, and so on. Traditional community discovery based on static network has been studied extensively, and many excellent methods and parameters have been accumulated. However, with the rapid development of complex networks, new complex networks often have the characteristics of large number of users, complex group structure, wide social interaction and rapid development. Traditional static network community discovery research has been difficult to meet the current community discovery needs. Dynamic overlapping community discovery can further explore the complexity and dynamics of communities in complex networks and is one of the important research directions of community discovery. In this paper, a decomposition based multi-objective evolutionary algorithm (MOEA / D) is used to solve the problem of dynamic overlapping community discovery. Dynamic community discovery algorithm based on MOEA/D (moat / D based dynamic community detection algorithm / MOEAD-DCDD) simultaneously optimizes two kinds of objective functions: instantaneous scoring (SC) and time consuming time cost (SC). SC uses community discovery classical metrics. To ensure the accuracy of community discovery results at each time. TC to calculate the similarity of community discovery results between adjacent moments, and to ensure the stability of dynamic network community discovery. For the overlapping community discovery of complex networks, the traditional community discovery often has high time complexity. In this paper, a large number of classical strategies are used to improve the efficiency of the algorithm. The method of roulette is used to design the initialization operator and evolution operator of MOEA/D, and the initial solution of the current moment is initialized by the result of community discovery. MOEAD-DCD adopts an improved coding method based on adjacent locus expression. So that a node in the network can belong to multiple different community structures at the same time. By retaining a variety of non-dominant solutions MOEAD-DCD ensures diversity of community discovery results and avoids the influence of artificial selection of multi-objective functions. According to literature research, MOEA/D is used for the first time to solve the dynamic overlapping community discovery problem. MOEA / D algorithm has a high running efficiency and can guarantee the diversity of the final non-dominated solutions. At the same time, compared with the traditional community discovery algorithm, MOEAD-DCD can ensure the accuracy and stability of the dynamic community results. The effectiveness of MOEAD-DCD is verified by numerical experiments.
【學(xué)位授予單位】：北京郵電大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP18;O157.5

【參考文獻(xiàn)】

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

1 胡泳;;冪律分布[J];商務(wù)周刊;2009年22期

，

本文編號：1785840