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

【摘要】：社區(qū)發(fā)現(xiàn)(又稱為社團發(fā)現(xiàn))是復雜網(wǎng)絡研究的重要部分,主要目的是挖掘網(wǎng)絡中一群相互聯(lián)系緊密的節(jié)點組成的模塊。社區(qū)發(fā)現(xiàn)在推薦系統(tǒng),危險預警,輿情分析等領(lǐng)域有著廣泛的應用。傳統(tǒng)基于靜態(tài)網(wǎng)絡的社區(qū)發(fā)現(xiàn)已有大量研究,并且積累了許多優(yōu)秀的方法和參數(shù)。但是,隨著復雜網(wǎng)絡的快速發(fā)展,新的復雜網(wǎng)絡常常具有用戶數(shù)量多、群體結(jié)構(gòu)復雜、用戶社交廣泛、發(fā)展快等特點。傳統(tǒng)靜態(tài)網(wǎng)絡社區(qū)發(fā)現(xiàn)研究已難以滿足當前社區(qū)發(fā)現(xiàn)需求。動態(tài)重疊社區(qū)發(fā)現(xiàn)研究可以進一步探索復雜網(wǎng)絡中社區(qū)的復雜性和動態(tài)性,是社區(qū)發(fā)現(xiàn)重要研究方向之一。本文采用一種基于分解的多目標進化算法(Decomposition based multi-objective evolutionary algorithm, MOEA/D)解決動態(tài)可重疊社區(qū)發(fā)現(xiàn)問題�；贛OEA/D的動態(tài)社區(qū)發(fā)現(xiàn)算法(MOEA/D based dynamic community detection algorithm ,MOEAD-DCD)同時優(yōu)化瞬時評分(Snapshot score, SC)和時間消耗(Temporal cost,TC)兩類目標函數(shù)。SC采用社區(qū)發(fā)現(xiàn)經(jīng)典衡量指標,保證每一個時刻社區(qū)發(fā)現(xiàn)結(jié)果的準確性。TC計算相鄰時刻間社區(qū)發(fā)現(xiàn)結(jié)果的相似性,保證動態(tài)網(wǎng)絡社區(qū)發(fā)現(xiàn)的穩(wěn)定性。針對復雜網(wǎng)絡的重疊社區(qū)發(fā)現(xiàn),傳統(tǒng)社區(qū)發(fā)現(xiàn)往往具有較高時間復雜度,針對該問題本文采用了大量經(jīng)典策略提高算法效率。包括采用輪盤賭方法設計MOEA/D的初始化算子和進化算子,采用前一時刻社區(qū)發(fā)現(xiàn)結(jié)果初始化當前時刻初始解等。MOEAD-DCD采用一種改進的基于鄰接軌跡表達的編碼方式,使得網(wǎng)絡中一個節(jié)點可以同時隸屬于多個不同的社區(qū)結(jié)構(gòu)。通過保留多種非支配解,MOEAD-DCD保證了社區(qū)發(fā)現(xiàn)結(jié)果多樣性,避免人為選擇多目標函數(shù)的影響權(quán)重問題。根據(jù)文獻調(diào)研,本文首次將MOEA/D用于解決動態(tài)可重疊社區(qū)發(fā)現(xiàn)問題。MOEA/D算法具有較高運行效率,能夠保證最終非支配解多樣性的特點。同時結(jié)合本文采用的大量改進策略,與傳統(tǒng)社區(qū)發(fā)現(xiàn)算法相比,MOEAD-DCD能夠保證準確性的同時,兼顧動態(tài)社區(qū)結(jié)果的穩(wě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.
【學位授予單位】：北京郵電大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP18;O157.5

【參考文獻】

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

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

，

本文編號：1785840