本文選題：復(fù)雜網(wǎng)絡(luò)分析 + 社團(tuán)發(fā)現(xiàn)��； 參考：《南京大學(xué)》2016年碩士論文

【摘要】：當(dāng)今世界復(fù)雜網(wǎng)絡(luò)無處不在,網(wǎng)絡(luò)型系統(tǒng)已深深嵌入到我們生產(chǎn)生活的過程之中。復(fù)雜網(wǎng)絡(luò)分析越來越受到學(xué)術(shù)界和工業(yè)界的關(guān)注。復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)揭示了網(wǎng)絡(luò)中的節(jié)點(diǎn)個(gè)體之間邊連接關(guān)系之上更高層的交互關(guān)系,研究社團(tuán)關(guān)系能夠使研究者更好地理解一個(gè)復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)及功能。目前,已經(jīng)有許多學(xué)者將社團(tuán)發(fā)現(xiàn)應(yīng)用于多種實(shí)際應(yīng)用場(chǎng)景之中。因此,社團(tuán)發(fā)現(xiàn)對(duì)于復(fù)雜網(wǎng)絡(luò)理論研究及實(shí)際應(yīng)用都具有非凡的意義。本文就社團(tuán)發(fā)現(xiàn)中的局部社團(tuán)發(fā)現(xiàn)相關(guān)問題進(jìn)行研究,分析目前局部社團(tuán)發(fā)現(xiàn)算法的共性及存在的問題,并提出兩種新的局部社團(tuán)發(fā)現(xiàn)算法,論文主要工作如下：1)分析了多種局部社團(tuán)發(fā)現(xiàn)算法,發(fā)現(xiàn)其在局部社團(tuán)擴(kuò)張過程中存在多種節(jié)點(diǎn)劃分錯(cuò)誤問題,指出錯(cuò)誤的原因在于算法無法區(qū)分真實(shí)社團(tuán)的內(nèi)部邊及外部邊,為了解決該問題,本文基于邊聚類系數(shù)提出了一種區(qū)分內(nèi)部邊外部邊的邊度量方法,該度量應(yīng)用于本文提出的兩種局部社團(tuán)發(fā)現(xiàn)算法之中。2)為了解決目前局部社團(tuán)發(fā)現(xiàn)算法普遍存在的樞紐節(jié)點(diǎn)及長(zhǎng)尾結(jié)構(gòu)之上的社團(tuán)劃分錯(cuò)誤問題,基于本文提出的改進(jìn)的邊聚類系數(shù),提出了局部社團(tuán)發(fā)算法CELCD,算法使用一種簡(jiǎn)潔有效的種子邊選取方法,并提出了一種新的適應(yīng)度函數(shù)。本文分別在真實(shí)世界復(fù)雜網(wǎng)絡(luò)及計(jì)算機(jī)生成網(wǎng)絡(luò)上對(duì)CELCD算法進(jìn)行了實(shí)驗(yàn)分析,實(shí)驗(yàn)結(jié)果表明該算法社團(tuán)劃分效果優(yōu)于對(duì)比算法。3)基于單一適應(yīng)度函數(shù)的局部社團(tuán)發(fā)現(xiàn)算法在社團(tuán)擴(kuò)張選取節(jié)點(diǎn)時(shí)存在一些局限性；且在局部社團(tuán)擴(kuò)張初期,社團(tuán)結(jié)構(gòu)還未穩(wěn)定,此時(shí)基于內(nèi)部邊外部邊比值進(jìn)行定義的適應(yīng)度函數(shù)易發(fā)生擴(kuò)張至社團(tuán)外部節(jié)點(diǎn)的情況。基于以上分析,本文提出了基于多目標(biāo)節(jié)點(diǎn)適應(yīng)度函數(shù)思想的局部社團(tuán)發(fā)現(xiàn)算法MOLCD,該算法使用兩個(gè)節(jié)點(diǎn)適應(yīng)度函數(shù),結(jié)合帕累托最優(yōu)的集合計(jì)算來選取加入社團(tuán)的候選節(jié)點(diǎn)。實(shí)驗(yàn)分析表明MOLCD算法減少了算法迭代次數(shù),提高了效率,且劃分效果在多數(shù)情況下優(yōu)于CELCD及其他對(duì)比算法。
[Abstract]:In today's world, the complex network is ubiquitous, and the network system has been embedded in the process of our production and life. Complex network analysis has attracted more and more attention from academia and industry. The community structure in a complex network reveals a higher level of interaction over the edge connection relationship between nodes and individuals in the network, and the study of community relations can enable researchers to better understand the structure and functions of a complex network. At present, many scholars have applied community discovery to many practical application scenarios. Therefore, community discovery is of great significance for the theoretical research and practical application of complex networks. In this paper, the problems related to local community discovery in community discovery are studied, the commonness and existing problems of local community discovery algorithms are analyzed, and two new local community discovery algorithms are proposed. The main work of this paper is as follows: (1) this paper analyzes several local community discovery algorithms, and finds that there are many node division errors in the process of local community expansion, and points out that the reason of the error lies in the fact that the algorithm can not distinguish the inner and outer edges of the real community. In order to solve this problem, an edge measurement method based on edge clustering coefficients is proposed to distinguish internal and external edges. This metric is applied to the two local community discovery algorithms proposed in this paper. Based on the improved edge clustering coefficient proposed in this paper, a local community distribution algorithm (CELCDD) is proposed. The algorithm uses a simple and effective seed edge selection method, and a new fitness function is proposed. In this paper, the CELCD algorithm is experimentally analyzed on real world complex networks and computer generated networks, respectively. The experimental results show that the algorithm has some limitations in selecting nodes for community expansion, and in the initial stage of local community expansion, the algorithm is superior to the contrast algorithm .3) the local community discovery algorithm based on a single fitness function has some limitations. The structure of the community is not stable, and the fitness function defined based on the ratio of the inner edge and the outer edge is easy to expand to the external node of the community. Based on the above analysis, this paper proposes a local community discovery algorithm, MOLCDD, which is based on the idea of multi-objective node fitness function. The algorithm uses two node fitness functions and combines Pareto optimal set calculation to select candidate nodes to join the community. The experimental results show that the MOLCD algorithm reduces the number of iterations and improves the efficiency, and the partition effect is better than that of CELCD and other contrast algorithms in most cases.
【學(xué)位授予單位】：南京大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP301.6;O157.5

【參考文獻(xiàn)】

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

1 魚亮;高琳;孫鵬崗;;蛋白質(zhì)網(wǎng)絡(luò)中復(fù)合體和功能模塊預(yù)測(cè)算法研究[J];計(jì)算機(jī)學(xué)報(bào);2011年07期

，

本文編號(hào)：1966201