基于復(fù)雜網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)算法研究.pdf

1、目前復(fù)雜網(wǎng)絡(luò)研究已融入到社會(huì)科學(xué)、生命科學(xué)、通信科學(xué)和電力科學(xué)等眾多重要科學(xué)領(lǐng)域，隨著復(fù)雜網(wǎng)絡(luò)研究的深入，人們逐漸發(fā)現(xiàn)了復(fù)雜網(wǎng)絡(luò)的許多重要的性質(zhì):小世界性、無(wú)標(biāo)度性、社團(tuán)結(jié)構(gòu)等基本統(tǒng)計(jì)特性。其中社團(tuán)結(jié)構(gòu)是指:網(wǎng)絡(luò)中處于相同社團(tuán)內(nèi)的節(jié)點(diǎn)聯(lián)系緊密，不同社團(tuán)間的節(jié)點(diǎn)聯(lián)系稀疏。發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)有助于分析復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和性質(zhì)、理解復(fù)雜網(wǎng)絡(luò)的功能、發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的隱藏規(guī)律以及預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)的行為。因此，復(fù)雜網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)已經(jīng)成為近幾年復(fù)雜

2、網(wǎng)絡(luò)領(lǐng)域的一個(gè)研究熱點(diǎn)，并形成了復(fù)雜網(wǎng)絡(luò)中一個(gè)重要的研究方向。
　　聚類分析是數(shù)據(jù)挖掘中的一個(gè)重要研究領(lǐng)域，它是指將物理或抽象對(duì)象的集合分成由類似的對(duì)象組成的多個(gè)類或簇的分析過(guò)程，并使得同一個(gè)簇中的對(duì)象有很大的相似性，而不同簇間的對(duì)象有很大的相異性。聚類分析在數(shù)據(jù)挖掘、統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、空間數(shù)據(jù)庫(kù)技術(shù)、生物學(xué)和市場(chǎng)學(xué)等眾多領(lǐng)域有廣泛的應(yīng)用。
　　復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)與數(shù)據(jù)的聚類分析很相似，本文在對(duì)已有的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法

3、進(jìn)行深入研究的基礎(chǔ)上，主要將聚類分析方法應(yīng)用到復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的研究中，首先把網(wǎng)絡(luò)轉(zhuǎn)化為適合聚類分析的數(shù)據(jù)結(jié)構(gòu)，然后根據(jù)轉(zhuǎn)化后的數(shù)據(jù)之間的相似性來(lái)進(jìn)行聚類，從而得到網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)劃分。
　　本文主要做了以下工作:
　　(1)提出了基于信號(hào)傳遞與層次聚類的社團(tuán)發(fā)現(xiàn)算法(SHC算法):通過(guò)在復(fù)雜網(wǎng)絡(luò)上傳遞信號(hào)，獲得各節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的影響向量，從而把網(wǎng)絡(luò)中節(jié)點(diǎn)的拓?fù)湫再|(zhì)轉(zhuǎn)化為代數(shù)空間上向量的幾何關(guān)系，即每個(gè)節(jié)點(diǎn)由其相應(yīng)的影響向量來(lái)表

4、示，然后用結(jié)合模塊度的層次聚類方法對(duì)向量進(jìn)行聚類，從而挖掘出網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。
　　(2)提出了基于相異性系數(shù)和譜分析的社團(tuán)發(fā)現(xiàn)算法(DSC算法):DSC算法基于網(wǎng)絡(luò)的標(biāo)準(zhǔn)化矩陣計(jì)算特征值，把網(wǎng)絡(luò)映射到特征向量空間上。給出了相異性系數(shù)的定義，其中用歐式距離替代布朗粒子的運(yùn)動(dòng)步數(shù)，然后通過(guò)計(jì)算各個(gè)節(jié)點(diǎn)對(duì)的相異性系數(shù)，用層次聚類方法得出網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)。而 Luca Donetti算法是基于Laplacian矩陣計(jì)算特征值，用角距離衡量