基于Fast-Newman算法的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)分解

1、 B007青島科技大學(xué)第八屆“校長(zhǎng)杯”數(shù)學(xué)知識(shí)競(jìng)賽暨2013年全國(guó)研究生、大學(xué)生數(shù)學(xué)建模競(jìng)賽選拔賽評(píng) 閱 專 用 頁(yè)評(píng)閱記錄：評(píng)閱人評(píng)分備注目錄一摘 要2二問題的提出4三問題的分析5四基本理論與算法思想64.1復(fù)雜網(wǎng)絡(luò)的基本概念與性質(zhì)64.1.1真實(shí)網(wǎng)絡(luò)的圖表示64.1.2度分布64.1.3網(wǎng)絡(luò)的平均最短路徑和頂點(diǎn)的介數(shù)64.1.4網(wǎng)絡(luò)的簇系數(shù)74.2復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)定義74.3 GN算法與Fast-Newman算法84.3.1 GN算法84.3.2 Fast-Newman算法9五建模過程115.1問題一115.1.1第一題第1個(gè)網(wǎng)絡(luò)115.1.2第一題第2個(gè)網(wǎng)絡(luò)135.2.3第一題

2、第3個(gè)網(wǎng)絡(luò)145.2 問題215六模型的評(píng)價(jià)與改進(jìn)15七參考文獻(xiàn)16 青島科技大學(xué)第八屆“校長(zhǎng)杯”數(shù)學(xué)知識(shí)競(jìng)賽暨2013年全國(guó)研究生、大學(xué)生數(shù)學(xué)建模競(jìng)賽選拔賽題 目 基于Fast-Newman算法的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)分解 一摘 要社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)極其重要的特性，網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)分解在生物學(xué)、計(jì)算機(jī)科學(xué)和社會(huì)學(xué)等多個(gè)領(lǐng)域都具有很重要的意義。復(fù)雜網(wǎng)絡(luò)通常會(huì)呈現(xiàn)出社團(tuán)結(jié)構(gòu)特性，如何在實(shí)際網(wǎng)絡(luò)中高效地發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)是近年來復(fù)雜網(wǎng)絡(luò)的研究熱點(diǎn)之一。近年來，針對(duì)不同類型的大規(guī)模復(fù)雜網(wǎng)絡(luò)，提出了很多尋找社團(tuán)結(jié)構(gòu)的算法。本模型基于貪婪算法的思想，根據(jù)Newman在GN算法上改進(jìn)優(yōu)化的一種凝聚算法Fast

3、-Newman算法，對(duì)問題中的多種復(fù)雜網(wǎng)絡(luò)進(jìn)行了社團(tuán)結(jié)構(gòu)分解，建立一種針對(duì)復(fù)雜網(wǎng)絡(luò)社團(tuán)分解的標(biāo)準(zhǔn)化方法，取得了不錯(cuò)的效果。最后，還分析了本算法的優(yōu)缺點(diǎn)，提出了如何改進(jìn)準(zhǔn)確度。關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò) 社團(tuán)結(jié)構(gòu) 分解 凝聚算法GN算法 Fast-Newman算法Decomposition of Network Community Structure Based on the Fast - Newman Algorithm AbstractCommunity structure is a very important property of complex networksDetecting commun

4、ities in networks is of great importance in biology，computer science，sociology and so onCommunity structure exists in many real networksHow to find such communities effectively is one of focuses of many recent researches in the branch of complex networksIn recent years，a lot of community discovery a

5、lgorithms have been proposed aiming at different kinds of large scale complex networksIn this paper, we based on greedy algorithm,According to a condensation algorithm which Newman in designed.the GN algorithm on optimization-Fast Newman algorithm.We decomposition a variety of complex network commun

6、ity structure in problems, good results have been achieved.Key words: complex network；community structure; GN Algorithm; Fast-Newman Algorithm二問題的提出 隨著小世界網(wǎng)絡(luò)模型和無標(biāo)度網(wǎng)絡(luò)模型的提出，國(guó)內(nèi)外掀起了研究復(fù)雜網(wǎng)絡(luò)的熱潮。復(fù)雜網(wǎng)絡(luò)的研究以系統(tǒng)的觀點(diǎn)來看待真實(shí)系統(tǒng)，如Internet網(wǎng)絡(luò)、電力網(wǎng)、新陳代謝網(wǎng)絡(luò)等。復(fù)雜網(wǎng)絡(luò)通常會(huì)呈現(xiàn)出社區(qū)結(jié)構(gòu)特性，如何在實(shí)際網(wǎng)絡(luò)中高效地發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)是近年來復(fù)雜網(wǎng)絡(luò)的研究熱點(diǎn)之一。近年來，人們提出了許多算法來尋找復(fù)雜網(wǎng)

7、絡(luò)中的社團(tuán)結(jié)構(gòu)。然而，當(dāng)網(wǎng)絡(luò)的規(guī)模過于龐大時(shí)，尋找整個(gè)網(wǎng)絡(luò)的全局社團(tuán)結(jié)構(gòu)的計(jì)算量是極大的。另外，在很多情況下關(guān)心的并不是整個(gè)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，而是網(wǎng)絡(luò)中某一部分的社團(tuán)結(jié)構(gòu)。比如，通常只關(guān)心社會(huì)網(wǎng)絡(luò)中某個(gè)人所在的社團(tuán)的結(jié)構(gòu)，或者是萬(wàn)維網(wǎng)中某個(gè)網(wǎng)站所在社團(tuán)的局部拓?fù)浣Y(jié)構(gòu)。在這種情況下，就不希望消耗過多的時(shí)間來尋找全部的社團(tuán)結(jié)構(gòu)。 揭示網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，對(duì)于深入了解網(wǎng)絡(luò)結(jié)構(gòu)與分析網(wǎng)絡(luò)特性是很重要的。如社會(huì)網(wǎng)絡(luò)中的社團(tuán)代表根據(jù)興趣和背景而形成的真實(shí)的社會(huì)團(tuán)體；引文網(wǎng)絡(luò)中的社團(tuán)代表針對(duì)同一主題的相關(guān)論文；萬(wàn)維網(wǎng)中的社團(tuán)就是討論相關(guān)主題的若干網(wǎng)站；而生物化學(xué)網(wǎng)絡(luò)或者電子電路中的網(wǎng)絡(luò)社團(tuán)可以是某一類功能單元。發(fā)

8、現(xiàn)這些網(wǎng)絡(luò)中的社團(tuán)有助于我們更加有效的理解和開發(fā)這些網(wǎng)絡(luò)。 盡管復(fù)雜網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)問題得到了大量的研究，但還存在一些尚未解決的基本問題，如社團(tuán)概念雖然大量使用，但卻缺少嚴(yán)格的數(shù)學(xué)定義；大多數(shù)社團(tuán)發(fā)現(xiàn)算法雖然性能優(yōu)越，但所需計(jì)算量卻很大。這說明復(fù)雜網(wǎng)絡(luò)中社團(tuán)發(fā)現(xiàn)的研究還需要付出大量的努力。 三問題的分析由題意可知，本題的目的就是建立一種模型，將復(fù)雜網(wǎng)絡(luò)中社團(tuán)進(jìn)行分解。在復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)劃分的研究中，社團(tuán)結(jié)構(gòu)劃分算法所要?jiǎng)澐值木W(wǎng)絡(luò)大致可分為兩類，一類是比較常見的網(wǎng)絡(luò)，即僅包含正聯(lián)系的網(wǎng)絡(luò)(網(wǎng)絡(luò)中邊的權(quán)值為正實(shí)數(shù))；另一類是符號(hào)社會(huì)網(wǎng)絡(luò)，即網(wǎng)絡(luò)中既包含正向聯(lián)系的邊，也包含負(fù)向聯(lián)系的邊。因此劃分網(wǎng)絡(luò)中

9、社團(tuán)結(jié)構(gòu)的算法相應(yīng)分為兩大類，而對(duì)于第一類網(wǎng)絡(luò)又提出了許多不同的社團(tuán)結(jié)構(gòu)劃分算法，劃分第一類網(wǎng)絡(luò)社團(tuán)的傳統(tǒng)算法可分為兩大類，第一類是基于圖論的算法，比如KL算法、譜平分法、隨機(jī)游走算法和派系過濾法等；第二類是層次聚類算法，比如基于相似度度量的凝聚算法和基于邊介數(shù)度量的分裂算法等。2001年，Girvan和Newman提出了一種基于邊介數(shù)的分裂算法，簡(jiǎn)稱GN算法。該算法的基本思想是不斷地從網(wǎng)絡(luò)中移除介數(shù)最大的邊。邊介數(shù)定義為網(wǎng)絡(luò)中經(jīng)過每條邊的最短路徑數(shù)目，該算法的復(fù)雜度非常高。2004年，Newman提出一種基于貪婪法思想的凝聚算法，并稱這種算法為Fast-Newman算法。該算法是在使得模塊度

10、不斷增加的基礎(chǔ)上進(jìn)行，即每次合并沿著使模塊度增多最大和減小最少的方向進(jìn)行。算法總的復(fù)雜度為，對(duì)于稀疏網(wǎng)絡(luò)則為，其中n為網(wǎng)絡(luò)中結(jié)點(diǎn)的個(gè)數(shù)，m為網(wǎng)絡(luò)中邊的條數(shù)。在本題中，我們選擇了更為先進(jìn)的Fast-Newman算法，通過把所給網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)化處理，在MATLAB上實(shí)現(xiàn)了復(fù)雜網(wǎng)絡(luò)的社團(tuán)分解。四基本理論與算法思想4.1復(fù)雜網(wǎng)絡(luò)的基本概念與性質(zhì)4.1.1真實(shí)網(wǎng)絡(luò)的圖表示 首先，簡(jiǎn)單介紹有關(guān)圖的定義和基本概念。圖可以表示為集合，表示圖的頂點(diǎn)集合，表示網(wǎng)絡(luò)的頂點(diǎn)總數(shù)，代表邊集合，表示總邊數(shù)，如果，則圖是無向圖，否則為有向圖。當(dāng)網(wǎng)絡(luò)是無向無權(quán)網(wǎng)絡(luò)時(shí)，鄰接矩陣是一個(gè)對(duì)稱矩陣，表示圖中頂點(diǎn)之間的連接關(guān)系。如果頂點(diǎn)

11、之間有連接，則：否則。當(dāng)網(wǎng)絡(luò)是有向圖時(shí)，鄰接矩陣是非對(duì)稱的矩陣：當(dāng)網(wǎng)絡(luò)是加權(quán)網(wǎng)絡(luò)時(shí)，中的非元素代表邊的權(quán)重。4.1.2度分布 度分布是描述網(wǎng)絡(luò)性質(zhì)的一個(gè)重要統(tǒng)計(jì)量。結(jié)點(diǎn)的度定義為與結(jié)點(diǎn)連接的邊的數(shù)目。度分布定義為隨機(jī)地選擇一個(gè)結(jié)點(diǎn)，度為的概率，或者等價(jià)地描述為網(wǎng)絡(luò)中度為后的結(jié)點(diǎn)數(shù)占網(wǎng)絡(luò)結(jié)點(diǎn)總數(shù)的比例。當(dāng)然，對(duì)于有向網(wǎng)絡(luò)，其度分布還可細(xì)致地分為網(wǎng)絡(luò)的入度分布（in-degree distribution）和出度分布(out-degree distribution)。4.1.3網(wǎng)絡(luò)的平均最短路徑和頂點(diǎn)的介數(shù)網(wǎng)絡(luò)的平均最短距離(average path length)定義為網(wǎng)絡(luò)中任意一對(duì)結(jié)點(diǎn)之間的最

12、短距離的平均值，數(shù)學(xué)表達(dá)式為：其中為結(jié)點(diǎn)之間的最短路徑的長(zhǎng)度。所有結(jié)點(diǎn)間的最短路徑長(zhǎng)度的最大值稱為網(wǎng)絡(luò)半徑(network diameter)。 網(wǎng)絡(luò)中不相鄰的結(jié)點(diǎn)和之間的路徑主要依賴于連接結(jié)點(diǎn)和的路徑上所經(jīng)過的結(jié)點(diǎn)，如果某個(gè)結(jié)點(diǎn)被其它許多路徑經(jīng)過，則表示該結(jié)點(diǎn)在網(wǎng)絡(luò)中很重要。定量地描某個(gè)結(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力或重要性可以用頂點(diǎn)的介數(shù)(node betweeness)來衡量，這一定義最早由Freeman在1977年提出。頂點(diǎn)的介數(shù)定義為： 其中表示結(jié)點(diǎn)、之間的最短路徑的個(gè)數(shù)，表示結(jié)點(diǎn)、之間的最短路徑中經(jīng)過結(jié)點(diǎn)的個(gè)數(shù)。4.1.4網(wǎng)絡(luò)的簇系數(shù) 網(wǎng)絡(luò)的簇系數(shù)(clustering coefficien

13、t)是衡量網(wǎng)絡(luò)集團(tuán)化程度的重要參數(shù)，是一個(gè)局部特征量。結(jié)點(diǎn)的簇系數(shù)定義為結(jié)點(diǎn)的鄰接點(diǎn)之間實(shí)際存在的邊數(shù)與所有可能的邊數(shù)的比值，數(shù)學(xué)表達(dá)為： 其中，表示結(jié)點(diǎn)的度，表示結(jié)點(diǎn)的鄰接點(diǎn)之間實(shí)際存在的邊數(shù)。網(wǎng)絡(luò)的簇系數(shù)定義為對(duì)所有結(jié)點(diǎn)的簇系數(shù)做和求平均： 許多真實(shí)網(wǎng)絡(luò)具有較大的簇系數(shù)和較小的平均最短距離。這里“較大的簇系數(shù)指真實(shí)網(wǎng)絡(luò)的簇系數(shù)遠(yuǎn)遠(yuǎn)大于相同規(guī)模的隨機(jī)網(wǎng)絡(luò)的簇系數(shù)。“較小的平均最短距離指平均最短距離隨網(wǎng)絡(luò)規(guī)模的增加呈對(duì)數(shù)或者更小增長(zhǎng)。4.2復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)定義 近幾年來，復(fù)雜網(wǎng)絡(luò)的研究正處于蓬勃發(fā)展的階段，其思想已經(jīng)充斥到科學(xué)和社會(huì)的每一個(gè)角落。隨著對(duì)網(wǎng)絡(luò)性質(zhì)的物理意義和數(shù)學(xué)特性的深入研究，人

14、們發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)都具有一個(gè)共同性質(zhì)社團(tuán)結(jié)構(gòu)。也就是說，網(wǎng)絡(luò)是由若干個(gè)“群(Group)"或“團(tuán)(Cluster)構(gòu)成的。每個(gè)群內(nèi)的結(jié)點(diǎn)之間的連接非常緊密，而群之間的連接卻相對(duì)比較稀疏，如圖3.2所示。圖中的網(wǎng)絡(luò)包含三個(gè)社團(tuán)，分別對(duì)應(yīng)圖中三個(gè)虛線圓圈包圍的部分。在這些社團(tuán)內(nèi)部，結(jié)點(diǎn)之間的聯(lián)系非常緊密，而社團(tuán)之間的聯(lián)系就稀疏得多。一般而言，社團(tuán)可以包含模塊、類、群和組等各種含義。例如，萬(wàn)維網(wǎng)可以看成是由大量網(wǎng)站社團(tuán)組成，其中同一個(gè)社團(tuán)內(nèi)部的各個(gè)網(wǎng)站所討論的都是一些有共同興趣的話題。類似地，在生物網(wǎng)絡(luò)或者電路網(wǎng)絡(luò)中，同樣可以將各個(gè)結(jié)點(diǎn)根據(jù)其不同的性質(zhì)劃分為不同的社團(tuán)。揭示網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)

15、，對(duì)于了解網(wǎng)絡(luò)結(jié)構(gòu)與分析網(wǎng)絡(luò)特性具有極為重要的意義。社團(tuán)結(jié)構(gòu)分析在生物學(xué)、物理學(xué)、計(jì)算機(jī)圖形學(xué)和社會(huì)學(xué)中都有廣泛的應(yīng)用。圖3.24.3 GN算法與Fast-Newman算法4.3.1 GN算法 GN算法是最典型的分裂算法。它的基本思想是通過不斷地從網(wǎng)絡(luò)中移除介數(shù)(Betweenness)最大的邊將整個(gè)網(wǎng)絡(luò)分解為各個(gè)社團(tuán)。其中，邊介數(shù)定義為網(wǎng)絡(luò)中經(jīng)過該邊的最短路徑的數(shù)目。它為區(qū)分一個(gè)社團(tuán)的內(nèi)部邊和連接社團(tuán)之間的邊提供了一種有效的度量標(biāo)準(zhǔn)。GN算法的基本流程如下： 步驟1計(jì)算網(wǎng)絡(luò)中所有邊的介數(shù)； 步驟2找到介數(shù)最高的邊并將它從網(wǎng)絡(luò)中移除； 重復(fù)步驟1和2，直到每個(gè)結(jié)點(diǎn)就是一個(gè)退化的社團(tuán)為止。 GN

16、算法彌補(bǔ)了一些傳統(tǒng)算法的不足，但是，在不知道社團(tuán)數(shù)目的情況下，GN算法也不知道這種分解要進(jìn)行到哪一步終止。為解決這個(gè)問題，Newman等人引進(jìn)了一個(gè)衡量網(wǎng)絡(luò)劃分質(zhì)量的標(biāo)準(zhǔn)模塊度。它是基于同型混合(Associativd Mixing)來定義的。考慮某種劃分形式，它將網(wǎng)絡(luò)劃分為個(gè)社團(tuán)。定義一個(gè)維的對(duì)稱矩陣，其中元素，表示網(wǎng)絡(luò)中連接兩個(gè)不同社團(tuán)的結(jié)點(diǎn)的邊在所有邊中占的比例；這兩個(gè)結(jié)點(diǎn)分別位于第個(gè)社區(qū)和第個(gè)社團(tuán)。注意，在這里所說的所有的邊是在原始網(wǎng)絡(luò)中的，而不必考慮是否被社團(tuán)結(jié)構(gòu)算法移除。因此，該模塊度的衡量標(biāo)準(zhǔn)是利用完整的網(wǎng)絡(luò)來計(jì)算的。 設(shè)矩陣中對(duì)角線上各元素之和為。它給出了網(wǎng)絡(luò)中連接某一個(gè)社團(tuán)內(nèi)

17、部各結(jié)點(diǎn)的邊在所有邊的數(shù)目中所占比例。定義每行(或者列)中各元素之和為它表示與第個(gè)社團(tuán)中的結(jié)點(diǎn)相連的邊在所有邊中所占的比例。在此基礎(chǔ)上，用下式來定義模塊度的衡量標(biāo)準(zhǔn)： 上式的物理意義是：網(wǎng)絡(luò)中連接兩個(gè)同種類型的結(jié)點(diǎn)的邊(即社區(qū)內(nèi)部邊)的比例減去在同樣的社團(tuán)結(jié)構(gòu)下任意連接這兩個(gè)結(jié)點(diǎn)的邊的比例的期望值。如果社團(tuán)內(nèi)部邊的比例不大于任意連接時(shí)的期望值，則有。一般認(rèn)為，的最大值對(duì)應(yīng)的社團(tuán)結(jié)構(gòu)就是網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)。的上限為，越接近這個(gè)值，就說明網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)越明顯。實(shí)際網(wǎng)絡(luò)中，該值通常位于0.3到0.7之間。經(jīng)過Newman等人的改進(jìn)以后，GN算法不必依賴多余的信息來判斷得到的社區(qū)結(jié)構(gòu)是否具有實(shí)際意義，而是

18、可以直接從網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)來進(jìn)行分析。但是該算法的耗時(shí)比較大，為，因此它僅僅適用于中等規(guī)模的大型網(wǎng)絡(luò)(n=10000以下)。為了解決這個(gè)問題，人們?cè)贕N算法的基礎(chǔ)上提出了多種改進(jìn)的算法，主要包括采用結(jié)點(diǎn)集的GN算法、自包含GN算法等。4.3.2 Fast-Newman算法 GN算法雖然準(zhǔn)確度比較高，分析社團(tuán)結(jié)構(gòu)的效果比原有的一些算法好，但是它的算法復(fù)雜度比較大，因此僅僅局限于研究中等規(guī)模的復(fù)雜網(wǎng)絡(luò)?，F(xiàn)在，對(duì)于Internet、WWW和電子郵件網(wǎng)絡(luò)等網(wǎng)絡(luò)的研究越來越多，面這些網(wǎng)絡(luò)通常都包含幾百萬(wàn)個(gè)以上的結(jié)點(diǎn)。在這種情況下，傳統(tǒng)的GN算法就不能滿足要求。基于這個(gè)原因，Newman在GN算法的基礎(chǔ)上提

19、出了一種快速算法Fast-Newman算法，它實(shí)際上是基于貪婪算法思想的一種凝聚算法，可以用于分析結(jié)點(diǎn)數(shù)達(dá)100萬(wàn)的復(fù)雜網(wǎng)絡(luò)。 Fast-Newman算法如下： 步驟1初始化網(wǎng)絡(luò)為個(gè)社團(tuán)，即每個(gè)結(jié)點(diǎn)就是一個(gè)獨(dú)立社團(tuán)。則在GN算法中討論過的矩陣中，初始的和滿足： 其中為結(jié)點(diǎn)的度，為網(wǎng)絡(luò)中總的邊數(shù)。 步驟2依次合并有邊相連的社團(tuán)對(duì)，并計(jì)算合并后的模塊度增量 根據(jù)貪婪算法的原理，每次合并應(yīng)該沿著Q增大最多或者減小最少的方向進(jìn)行，其算法復(fù)雜度為。每次合并以后，對(duì)相應(yīng)的元素更新，并將與社團(tuán)相關(guān)的行和列相加，其時(shí)間復(fù)雜度為。因此，步驟2總的時(shí)間復(fù)雜度為。 步驟3重復(fù)執(zhí)行步驟2，不斷合并社團(tuán)，直到整個(gè)網(wǎng)絡(luò)都

20、合并成為一個(gè)社團(tuán)。最多要執(zhí)行n-1次合并。該算法總的算法復(fù)雜度為，對(duì)于稀疏網(wǎng)絡(luò)則為。 整個(gè)算法完成后可以得到一個(gè)社區(qū)結(jié)構(gòu)分解的樹狀圖。再通過選擇在不同位置斷開可以得到不同的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。在這些社區(qū)結(jié)構(gòu)中，選擇一個(gè)對(duì)應(yīng)著局部最大值的，就得到最好的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。五建模過程通過我們對(duì)問題的分析，我們發(fā)現(xiàn)，可以將問題1的三個(gè)復(fù)雜網(wǎng)絡(luò)圖，通過標(biāo)號(hào)，寫成類似于問題2的數(shù)據(jù)形式，這樣我們只需編寫一個(gè)算法程序即可一次性解決問題1與問題2。通過閱讀大量文獻(xiàn)，我們選擇了Fast-Newman算法，除了它比一些傳統(tǒng)算法外，還有在算法結(jié)束后它可以直接得到一個(gè)社團(tuán)分解結(jié)構(gòu)圖。5.1問題一5.1.1第一題第1個(gè)網(wǎng)絡(luò)圖1觀

21、察圖1，我們發(fā)現(xiàn)網(wǎng)絡(luò)中標(biāo)號(hào)雖然有30個(gè)點(diǎn)，但實(shí)際只有19個(gè)點(diǎn)，其中又只有15個(gè)點(diǎn)在網(wǎng)絡(luò)上。為了便于處理，我們對(duì)網(wǎng)絡(luò)1上的點(diǎn)進(jìn)行重新賦值。如圖1.1圖1.1 按照附件3所給數(shù)據(jù)格式，我們將圖1.1的信息轉(zhuǎn)化成鄰接矩陣數(shù)據(jù)（見“B題：附件2.1.txt”）。我們將Fast-Newman算法編寫成MATLAB程序，見附錄1、2。由于16、17、18、19四點(diǎn)已獨(dú)立于網(wǎng)絡(luò)之外，故只需考慮點(diǎn)115。運(yùn)行程序，得到社團(tuán)分解結(jié)構(gòu)圖：圖1.2 我們只需將原來點(diǎn)的標(biāo)記代換回去，即可得到圖1的結(jié)構(gòu)分解樹狀圖。5.1.2第一題第2個(gè)網(wǎng)絡(luò)圖2 由于網(wǎng)絡(luò)2沒有進(jìn)行標(biāo)記，我們利用作圖軟件將每個(gè)點(diǎn)進(jìn)行標(biāo)記，如圖2.1：圖2

22、.1同樣，我們將第2個(gè)網(wǎng)絡(luò)的信息轉(zhuǎn)化成鄰接矩陣（“B題：附件2.2.txt”），在MATLAB程序中更換相應(yīng)數(shù)據(jù)，得到結(jié)構(gòu)分解樹狀圖2.2:圖第一題第3個(gè)網(wǎng)絡(luò) 圖3.1（圖中點(diǎn)84應(yīng)更正為64） 參照網(wǎng)絡(luò)1、網(wǎng)絡(luò)2處理步驟，我們同樣得到了鄰接矩陣數(shù)據(jù)（“B題：附件2.3.txt ”）。 在MATLAB程序中更換相應(yīng)數(shù)據(jù)，得到結(jié)構(gòu)分解樹狀圖3.2圖3.2至此，第一問三個(gè)復(fù)雜網(wǎng)絡(luò)都進(jìn)行了社團(tuán)結(jié)構(gòu)分解，得到了3個(gè)結(jié)構(gòu)分解樹狀圖，F(xiàn)ast-Newman算法程序運(yùn)行速度較快。5.2 問題2對(duì)于問題2，我們觀察附件3中數(shù)據(jù)，發(fā)現(xiàn)在第二列中出現(xiàn)了數(shù)字0。即表明電力網(wǎng)絡(luò)從0開始，到4940結(jié)束

23、，共計(jì)4941個(gè)點(diǎn)。為了能夠生成稀疏矩陣（生成稀疏矩陣要求數(shù)據(jù)都大于零），我們將附件3中所給數(shù)據(jù)每列都加1，這樣我們得到了一組新的數(shù)據(jù)。然后按照問題1的處理方法，在MATLAB中進(jìn)行社團(tuán)結(jié)構(gòu)分解，即可得到結(jié)果。由于硬件原因，問題2在MATLAB中運(yùn)行時(shí)間過長(zhǎng)。程序見附錄一與程序說明文件。六模型的評(píng)價(jià)與改進(jìn) 復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)分析是一個(gè)非常具有挑戰(zhàn)性和前景性的研究領(lǐng)域。本文介紹了復(fù)雜網(wǎng)絡(luò)的一些基本性質(zhì)，網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的定義和研究歷史及其意義，并且詳細(xì)分析了尋找網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的算法的優(yōu)劣。我們通過Fast-Newman算法，對(duì)復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)進(jìn)行了成功的分解，并得到了樹狀圖。本模型最主要的優(yōu)點(diǎn)在

24、與復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)分解速度較快，尤其在復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)不超過100個(gè)的時(shí)候，可以迅速直接的得到社團(tuán)結(jié)構(gòu)的樹狀圖。另外在數(shù)據(jù)處理與MATLAB程序方面，給出了一套接近于標(biāo)準(zhǔn)化的社團(tuán)結(jié)構(gòu)分解方法，可以處理各種復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)分解問題。本模型同樣存在一些弊端，首先在處理大規(guī)模復(fù)雜網(wǎng)絡(luò)的時(shí)候，對(duì)計(jì)算機(jī)硬件要求較高，得出社團(tuán)結(jié)構(gòu)分解的速度較慢。我們同復(fù)旦大學(xué)席裕庚教授的最新成果進(jìn)行了對(duì)比，席教授在分解30個(gè)節(jié)點(diǎn)的復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的時(shí)候大約花費(fèi)了6秒鐘，我們分解速度略慢。此外，我們的模型不能直接將某一社團(tuán)直接分離，而是一次性顯示整個(gè)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，這也是程序運(yùn)行花費(fèi)時(shí)間較長(zhǎng)的原因之一。對(duì)于復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)

25、劃分方法的進(jìn)一步研究可以從以下幾個(gè)方面考慮：(1)尋找劃分大規(guī)模復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的有效算法；(2)尋找快速而且更為可靠的網(wǎng)絡(luò)多社團(tuán)結(jié)構(gòu)分析算法以及對(duì)劃分結(jié)果的優(yōu)化處理方法；(3)提升計(jì)算機(jī)CPU處理效率； (4)對(duì)不同的復(fù)雜網(wǎng)絡(luò)，運(yùn)用不同的算法模型。七參考文獻(xiàn)1Kernighan B W，Lin SAn efficient heuristic procedure for portioning graphsJBellSystem Techni cal Journal，1970，49：2913072Fiedler MAlgebraic connectivity of graphsJCzechosl

26、ovak Mathematical Journal，1973，23(98)：2983053PothenA，Simon n，Liou K PPartitioning sparse matrices with eigenvectors of graphsJSIAM Journal on Matrix hnalysiS and Applications1990，11(3)：4304524Pons P and Latapy MComputing Communities in Large Networks Using Random WalksJComputer and Information Sc ie

27、nces2005，2842935Palla G，Derenyi I，F(xiàn)arkas I et a1Uncovering the Overlapping Community Structure ofComplex Networks in Nature and SocietyJNature，2005 435(7043)：814-8186Palla G，F(xiàn)arkas I，Pollner P，Derenyi I et a1Directed network modulesJPhysNewJ，2007，1867Newman M E JFast algorithm for detecting communit

28、y structure in networksJPhysicalReview E，2004，69(6)：0661338Girvan M，Newman M E JCommunity structure in social and biological networksJPNAS，2001，99(12)：7821-78269Tyler J，Wilkinson D，Huberman BEmail as spectroscopy：Automated discovery of community structure within organizationsCInternational Conferenc

29、e on Communitiesand Techn0109ies，2003，819610Radicchi F，Castellano C，Cecconi F et a1Defining and identifying communities in networksJEurPhys。JB，2004，101：2658266311Fell D A，Wagner AThe small world of metabolismJNature(Biotechnology，2000，(18)：1121-112212Pool l，Kochen MContacts and InfluenceJSocial Netw

30、orks，1978，(1)：l-4813Milgram SThe small world problemJPsychology Today，1967，(2)：60-6714Freeman LSociometryG1977，40：35-4115Gleiser P，Danon LCommunity structure in jazzJAdvances in Complex Systems，2003，6：565-57316Newman M E J，Girvan MFinding and evaluating community structure in networksJPhysical Revie

31、w E，2004，69(2)：02611317汪小帆，李翔，陳關(guān)榮復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用M北京：清華大學(xué)出版社，2006，162-19118王冰復(fù)雜網(wǎng)絡(luò)的演化機(jī)制及若干動(dòng)力學(xué)行為研究D大連：大連理工大學(xué)，200619郭崇惹，張亮基于PCA的復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)分析方法J運(yùn)籌與管理，2008，17(6)，14414920王林，戴冠中復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)理論與應(yīng)用J科技導(dǎo)報(bào)，2005，23(8)：626621張光衛(wèi)，康建初，夏傳良，李鶴松復(fù)雜網(wǎng)絡(luò)集團(tuán)特征研究綜述J計(jì)算機(jī)科學(xué)，2006，33(10)：1-4附錄一：function Z H = FastNewman(adjacent_matrix)% Fa

32、stNewman算法實(shí)現(xiàn)社團(tuán)發(fā)現(xiàn)% 該算法參見文獻(xiàn)Fast algorithm for detecting community structure in networks(2003)% 輸入% adjacent_matrix - 鄰接矩陣% 輸出% Z - n-1*3矩陣，第i行表示第i次合并，第1列和第2列表示合并的社團(tuán)標(biāo)號(hào)，第3列是合并后的模塊度% H - 聚類樹圖的句柄u,v=textread('B題：附件2.2.txt');m=length(u);A=zeros(85);for i=1:m A(u(i),v(i)=1;endadjacent_matrix=A;n = s

33、ize(adjacent_matrix,1); % 節(jié)點(diǎn)數(shù)目max_id = n;Z = ;clusters = 1:n; zeros(1,n); 1:n; % 初始劃分，第1行是節(jié)點(diǎn)標(biāo)號(hào)，第2行是社團(tuán)標(biāo)號(hào)的變換，第3行是社團(tuán)標(biāo)號(hào)step = 1;while numel(unique(clusters(3,:) = 1 % while step < n Q e a clusters = GetModularity(adjacent_matrix, clusters); k = size(e,1); % 社團(tuán)數(shù)目 DeltaQs = ; for i = 1:size(e,1) for j

34、= 1:size(e,1) if i = j DeltaQ = 2*(e(i,j)-a(i)*a(j); DeltaQs = DeltaQs i;j;DeltaQ; end end end maxDeltaQ,id = max(DeltaQs(3,:); id = id(1); i = DeltaQs(1,id); j = DeltaQs(2,id); % 找出DeltaQ最大的社團(tuán)對(duì)的序號(hào) max_id = max_id + 1; c_id1 = find(clusters(2,:) = i); c_id2 = find(clusters(2,:) = j); id1 = unique(clusters(3,c_id1); id2 = unique(clusters(3,c