【摘要】：很多復(fù)雜系統(tǒng)都可以抽象成復(fù)雜網(wǎng)絡(luò)或者圖來進(jìn)行研究,同時,復(fù)雜網(wǎng)絡(luò)科學(xué)的發(fā)展也極大地促進(jìn)了人們對復(fù)雜系統(tǒng)的理解。在對復(fù)雜網(wǎng)絡(luò)研究過程中,相繼有很多重要特性被發(fā)現(xiàn),比如自相似、吸引子、小世界、無標(biāo)度和社團(tuán)結(jié)構(gòu)等。其中,社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)中最重要的特性之一,對研究復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)和功能有著舉足輕重的作用,在社會學(xué)、物理學(xué)、生物學(xué)和計(jì)算機(jī)科學(xué)等很多領(lǐng)域均具有非常重要的意義。網(wǎng)絡(luò)聚類就是檢測復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu),這些社團(tuán)結(jié)構(gòu)具有內(nèi)部連接緊密社團(tuán)之間連接稀疏的特點(diǎn)。隨著人們對社團(tuán)結(jié)構(gòu)持續(xù)不斷的深入研究,已經(jīng)涌現(xiàn)出大量優(yōu)秀的圖聚類算法。目前,在快速發(fā)展的社交網(wǎng)絡(luò)和大數(shù)據(jù)的推動下,網(wǎng)絡(luò)規(guī)模也不斷增長,很多網(wǎng)絡(luò)的規(guī)模甚至包含數(shù)百萬個結(jié)點(diǎn)和數(shù)十億條邊。如何解決大規(guī)模網(wǎng)絡(luò)聚類已成為該領(lǐng)域內(nèi)的研究難點(diǎn)。基于此,本文首先簡要介紹圖聚類的研究背景及意義,并概述該領(lǐng)域重要的研究進(jìn)展。接著對復(fù)雜網(wǎng)絡(luò)的定義和特性、社團(tuán)結(jié)構(gòu)的定義以及圖聚類的評價指標(biāo)等相關(guān)基礎(chǔ)知識作了簡單介紹。然后,從優(yōu)化一般圖聚類算法出發(fā),結(jié)合最近提出的基于快速發(fā)現(xiàn)和搜索密度峰值聚類算法和復(fù)雜網(wǎng)絡(luò)無標(biāo)度特性,提出基于中心結(jié)點(diǎn)快速檢測的圖聚類算法(CFCN),該算法通過快速搜索和檢測聚類中心來實(shí)現(xiàn)網(wǎng)絡(luò)的快速聚類。另一方面,為了改善一般聚類算法可擴(kuò)展性以適應(yīng)大規(guī)模網(wǎng)絡(luò)聚類,同時滿足實(shí)時性需求,本文提出了基于動態(tài)規(guī)劃的大規(guī)模網(wǎng)絡(luò)在線聚類框架(DPOCG),該框架通過構(gòu)造超級結(jié)點(diǎn)和移除邊緣結(jié)點(diǎn)大大減小了時變網(wǎng)絡(luò)規(guī)模,從而使一般的圖聚類算法得以適用。本文的主要研究工作如下:(1)提出了一種基于中心結(jié)點(diǎn)快速檢測的圖聚類算法。該算法首先計(jì)算每個結(jié)點(diǎn)的局部密度ρ和綜合距離β,接著通過由ρ和β畫出的決策圖來快速確定檢測聚類中心的局部密度閾值thrho和綜合距離閾值thbeta,并檢測出聚類中心,最后將非聚類中心結(jié)點(diǎn)分配到與其關(guān)系最緊密的聚類中心所在聚類以實(shí)現(xiàn)整個網(wǎng)絡(luò)聚類。我們在真實(shí)世界網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明,基于中心結(jié)點(diǎn)快速檢測的圖聚類算法的聚類效果明顯優(yōu)于對比算法。(2)提出一種基于動態(tài)規(guī)劃的大規(guī)模網(wǎng)絡(luò)在線聚類框架。該框架基于動態(tài)規(guī)劃的思想并結(jié)合網(wǎng)絡(luò)演變的特點(diǎn),將大規(guī)模網(wǎng)絡(luò)按一定時間段分成若干階段的子網(wǎng)絡(luò)。接著通過兩種方式來減小每一階段子網(wǎng)絡(luò)的規(guī)模,分別是根據(jù)相鄰階段聚類內(nèi)部結(jié)點(diǎn)狀態(tài)變化情況對聚類內(nèi)部狀態(tài)未改變結(jié)點(diǎn)構(gòu)造超級結(jié)點(diǎn)和移除網(wǎng)絡(luò)邊緣結(jié)點(diǎn)。最后應(yīng)用一般圖聚類算法?在縮減規(guī)模后的網(wǎng)絡(luò)上進(jìn)行聚類,并對移除結(jié)點(diǎn)按最近鄰策略快速聚類,最終實(shí)現(xiàn)整個網(wǎng)絡(luò)聚類�？焖俑咝У腄POCG框架很好的解決了大規(guī)模網(wǎng)絡(luò)聚類,并改善了一般聚類算法的可擴(kuò)展性,同時滿足了實(shí)時性要求。通過在合成的BA網(wǎng)絡(luò)和真實(shí)世界網(wǎng)絡(luò)上實(shí)驗(yàn),結(jié)果表明了DPOCG框架的有效性,且聚類效果明顯優(yōu)于其它幾種對比的大規(guī)模網(wǎng)絡(luò)聚類算法。
【學(xué)位授予單位】：西南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O157.5
【圖文】：

計(jì)算機(jī)科學(xué)等，復(fù)雜系統(tǒng)都可以抽象成網(wǎng)絡(luò)來研究，如新陳代謝網(wǎng)[1]、蛋白質(zhì)相互作用網(wǎng)[2]、科學(xué)家合作網(wǎng)（圖1-1）、公路網(wǎng)、航空網(wǎng)[3]、萬維網(wǎng)[4]等。復(fù)雜網(wǎng)絡(luò)[5]在數(shù)學(xué)上又可以抽象為圖，通過應(yīng)用圖論的有關(guān)概念，能夠?qū)?fù)雜網(wǎng)絡(luò)中個體之間的相互作用進(jìn)行深刻的描述，其中，網(wǎng)絡(luò)中的個體可以看作圖中的結(jié)點(diǎn)，個體之間的相互作用可以由圖中邊表示。對于圖論的研究，最早可以追溯到 1736 年歐拉解決哥尼斯堡七橋問題，從此人們開始了解更多關(guān)于圖及其數(shù)學(xué)特性[6]。到了二十世紀(jì)，圖在表示各種不同領(lǐng)域的系統(tǒng)方面變得非常有用，像生物，社會，技術(shù)和信息等方面的網(wǎng)絡(luò)都可以作為圖來研究，而且圖分析對于理解這些系統(tǒng)的特征已經(jīng)變得至關(guān)重要。比如始于 20世紀(jì) 30 年代的社會網(wǎng)絡(luò)分析，已經(jīng)成為社會學(xué)中最重要的話題之一[7]。近年來，計(jì)算機(jī)革命為學(xué)者提供了大量的數(shù)據(jù)和計(jì)算資源來處理和分析這些網(wǎng)絡(luò)數(shù)據(jù)，進(jìn)而人們能處理的真實(shí)網(wǎng)絡(luò)的規(guī)模也大大增加，達(dá)到數(shù)百萬乃至數(shù)十億的結(jié)點(diǎn)。處理如此大量數(shù)據(jù)的需求已經(jīng)對圖處理方式產(chǎn)生了深刻的變化。圖 1-1 科學(xué)家合作網(wǎng)通過對圖論的進(jìn)一步研究，早期科學(xué)家建立了完全規(guī)則網(wǎng)絡(luò)[8]和完全隨機(jī)網(wǎng)絡(luò)理論[9]。其中，規(guī)則圖中每個結(jié)點(diǎn)都有相同的鄰居數(shù)，也就是每個結(jié)點(diǎn)的度都相等。

西南大學(xué)碩士學(xué)位論文度和聚類系數(shù)這兩個概念，下面將給出定義。網(wǎng)絡(luò)的平均路徑長度可以用來描述網(wǎng)絡(luò)的隨機(jī)性，它的定義如下：L ￠（￠ )∑ ≠ （2-2）其中，n 為網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)， 為從結(jié)點(diǎn) i 到結(jié)點(diǎn) j 的最短路徑，平均路徑長度 L 則表示網(wǎng)絡(luò)中任意兩個結(jié)點(diǎn)最短路徑和的平均值。聚類系數(shù)則用來描述網(wǎng)絡(luò)中結(jié)點(diǎn)群聚性或者聚集的緊密程度。網(wǎng)絡(luò)的聚集系數(shù)是所有結(jié)點(diǎn)的聚類系數(shù)均值，網(wǎng)絡(luò)中結(jié)點(diǎn) v 的聚類系數(shù)定義如下： ( )（2-3）網(wǎng)絡(luò)的聚類系數(shù)為：C ∑ （2-4）其中，m 表示結(jié)點(diǎn) v 的 個鄰居結(jié)點(diǎn)之間的邊數(shù)。Regular Small-world Random

第 2 章 預(yù)備知識及基礎(chǔ)理論分布[58]（如圖 2-2）。但是科學(xué)家們通過研究發(fā)現(xiàn)，現(xiàn)實(shí)世界的大部分網(wǎng)隨機(jī)網(wǎng)絡(luò)，它們的結(jié)點(diǎn)度分布服從冪律分布[59]（如圖 2-3），即有：P( ) （2 P(k)表示網(wǎng)絡(luò)中結(jié)點(diǎn)度為 k 的概率，γ 是一個常數(shù)通常在 1 到 3 之間。如結(jié)點(diǎn)的度分布服從冪律分布，我們可以將這種特性稱為無標(biāo)度特性，具性的網(wǎng)絡(luò)則稱為無標(biāo)度網(wǎng)絡(luò)。

【參考文獻(xiàn)】

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

1 周濤;;網(wǎng)絡(luò)大數(shù)據(jù)——復(fù)雜網(wǎng)絡(luò)的新挑戰(zhàn):如何從海量數(shù)據(jù)獲取信息?[J];電子科技大學(xué)學(xué)報;2013年01期

2 馮少榮;肖文俊;;一種提高DBSCAN聚類算法質(zhì)量的新方法[J];西安電子科技大學(xué)學(xué)報;2008年03期

相關(guān)碩士學(xué)位論文 前3條

1 王從濤;基于大規(guī)模復(fù)雜網(wǎng)絡(luò)的重疊社團(tuán)檢測算法研究[D];安徽大學(xué);2017年

2 馬磊;大規(guī)模網(wǎng)絡(luò)社團(tuán)探測算法應(yīng)用[D];華東師范大學(xué);2012年

3 劉亞冰;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)特性研究[D];上海交通大學(xué);2010年

本文編號：2778380