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

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

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

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

【參考文獻】

相關期刊論文 前2條

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

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

相關碩士學位論文 前3條

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

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

3 劉亞冰;復雜網(wǎng)絡中的社團結構特性研究[D];上海交通大學;2010年

本文編號：2778380