發(fā)布時間：2018-01-12 18:17

  本文關(guān)鍵詞：基于局部信息的復(fù)雜網(wǎng)絡(luò)社團(tuán)挖掘算法研究　出處：《燕山大學(xué)》2015年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 復(fù)雜網(wǎng)絡(luò) 局部信息 種子 貪婪擴(kuò)張 重疊社團(tuán)

【摘要】：近年來,網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法研究及應(yīng)用成為多學(xué)科間共同研究的熱點。盡管取得了一定的成果,但是現(xiàn)有的社團(tuán)發(fā)現(xiàn)算法時間復(fù)雜度、聚類質(zhì)量和算法穩(wěn)定性仍不盡如人意,亟待解決的難題如下:在數(shù)據(jù)量大、拓?fù)浣Y(jié)構(gòu)復(fù)雜的網(wǎng)絡(luò)中提高挖掘社團(tuán)結(jié)構(gòu)算法的聚類精度;重疊網(wǎng)絡(luò)中的重疊結(jié)點有效劃分;在缺少先驗知識的前提下,劃分社團(tuán)結(jié)構(gòu)結(jié)果的一致性。針對以上問題,本文在前人的研究基礎(chǔ)上,提出了基于亞團(tuán)貪婪擴(kuò)張的非重疊社團(tuán)劃分算法,針對重疊社團(tuán)結(jié)構(gòu)網(wǎng)絡(luò)提出了基于超邊貪婪擴(kuò)張的社團(tuán)發(fā)現(xiàn)算法,并采用標(biāo)準(zhǔn)的虛擬數(shù)據(jù)集分別做對比實驗,論文的主要內(nèi)容如下。首先,概述了復(fù)雜網(wǎng)絡(luò)的相關(guān)知識,并著重介紹了社團(tuán)發(fā)現(xiàn)算法研究的研究現(xiàn)狀,包括當(dāng)下典型的社團(tuán)發(fā)現(xiàn)算法,以及這些算法各自的特點和存在的不足。其次,在相對成熟的非重疊網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)研究中,由于網(wǎng)絡(luò)數(shù)據(jù)量較大、社團(tuán)結(jié)構(gòu)復(fù)雜導(dǎo)致算法的聚類精度下降,算法劃分社團(tuán)結(jié)果不一致。本文在基于局部信息算法的基礎(chǔ)上提出亞團(tuán)貪婪擴(kuò)張的劃分算法,該算法使用亞團(tuán)做算法種子,有效的提高了算法聚類進(jìn)度。然后,針對重疊復(fù)雜網(wǎng)絡(luò)中社團(tuán)重疊區(qū)域結(jié)點不易劃分的難題,本文使用邊作為度量工具,在基于局部信息貪婪擴(kuò)張的算法研究工作之上,通過篩選網(wǎng)絡(luò)中可聚度較高的邊組成超邊,并作為社團(tuán)發(fā)現(xiàn)算法的種子,提出了基于超邊種子的貪婪擴(kuò)張算法,算法的聚類精度較高。最后,對本文提出的兩個算法,分別在復(fù)雜網(wǎng)絡(luò)中的標(biāo)準(zhǔn)數(shù)據(jù)集上做了實驗,并和幾個經(jīng)典算法做對比,并在算法聚類精度和穩(wěn)定性方面進(jìn)行了分析。
[Abstract]:In recent years, the network community structure discovery algorithm research and application become interdisciplinary common research focus. Although achieved certain results, but the existing community detection algorithm time complexity, clustering quality and stability of the algorithm is still not satisfactory, problems to be solved are as follows: in the large amount of data and improve the accuracy of the clustering mining algorithm of community structure the topological structure of complex networks; overlapped nodes effectively divide in overlapping networks; in the premise of the lack of prior knowledge, the consistency of the partition of community structure. Aiming at the above problems, this paper based on previous studies, the sub group greedy expansion non overlapping partitioning algorithm based on overlapping community structure of the network super edge detection algorithm was proposed based on the greedy expansion of community, virtual data and using the standard set respectively do a comparative experiment, the main contents of this paper are as follows. First of all And summarizes the related knowledge of complex network, and emphatically introduces the research status of algorithm research found associations, including the typical community discovery algorithm, and their characteristics and shortcomings of these algorithms. Secondly, in the non overlapping community network discovery research is relatively mature, because a large amount of data, complex community structure lead to a decline in accuracy of clustering algorithm, the algorithm is not consistent results. Based on the partition of community partitioning algorithm based on local information on the algorithm of sub group proposed greedy expansion, the algorithm uses sub group algorithm seed, effectively improve the clustering progress. Then, in order to solve the problem of overlapping in complex network community overlap region node not classified in this paper, using the edge as a measurement tool, based on the algorithm of local information greedy expansion, poly degree higher edge composition by screening in super network The edge, and as a community discovery algorithm of seeds, propose the greedy expansion algorithm based on Super Edge seeds, high clustering accuracy algorithm. Finally, the two algorithms presented in this paper, the standard data respectively in the complex network set to do the experiment, and compare several classic algorithms, and analyzed in algorithm of clustering accuracy and stability.

【學(xué)位授予單位】：燕山大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5

【參考文獻(xiàn)】

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

1 韓言妮;李德毅;陳桂生;;軟件網(wǎng)絡(luò)的多粒度拓?fù)涮匦苑治黾捌鋺?yīng)用[J];計算機(jī)學(xué)報;2009年09期

2 金弟;楊博;劉杰;劉大有;何東曉;;復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu)探測——基于隨機(jī)游走的蟻群算法[J];軟件學(xué)報;2012年03期

，

本文編號：1415411