1、近年來(lái)復(fù)雜網(wǎng)絡(luò)的研究受到了越來(lái)越廣泛的關(guān)注，在計(jì)算機(jī)科學(xué)、物理學(xué)、生物學(xué)、數(shù)學(xué)乃至社會(huì)學(xué)和管理學(xué)等領(lǐng)域都產(chǎn)生了重大的意義和深遠(yuǎn)的影響。過(guò)去由于技術(shù)上的限制，科學(xué)家的研究往往都停留在只有幾十、幾百個(gè)節(jié)點(diǎn)的小網(wǎng)絡(luò)上，研究方法大多是比較直觀的圖論方法。然而，隨著信息技術(shù)的高速發(fā)展，科學(xué)家所面臨的網(wǎng)絡(luò)數(shù)據(jù)規(guī)模呈現(xiàn)爆炸式的增長(zhǎng)，獲取上億規(guī)模的網(wǎng)絡(luò)已經(jīng)變得非常容易。在大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的驅(qū)動(dòng)下，網(wǎng)絡(luò)科學(xué)得到了長(zhǎng)足的發(fā)展，并在未來(lái)?yè)碛懈蟮陌l(fā)展?jié)摿?。社團(tuán)

2、結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)所特有的一種中觀結(jié)構(gòu)，在真實(shí)世界中，它往往對(duì)應(yīng)著不同網(wǎng)絡(luò)的不同功能或結(jié)構(gòu)單元。由于社團(tuán)結(jié)構(gòu)不僅是網(wǎng)絡(luò)的一種壓縮表示形式，更為網(wǎng)絡(luò)的其他分析挖掘提供了中觀尺度的分析視角，因而在大規(guī)模復(fù)雜網(wǎng)絡(luò)的各項(xiàng)研究中，社團(tuán)結(jié)構(gòu)研究是一項(xiàng)非常重要而基礎(chǔ)的工作。社團(tuán)的重疊是真實(shí)世界網(wǎng)絡(luò)中常見(jiàn)的一種現(xiàn)象，例如一個(gè)人可以屬于多個(gè)興趣小組、一個(gè)蛋白質(zhì)可以屬于多個(gè)蛋白復(fù)合體等等，因此發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社團(tuán)結(jié)構(gòu)更能準(zhǔn)確地獲取網(wǎng)絡(luò)中真實(shí)的中觀結(jié)構(gòu)信息。但是

3、，目前常見(jiàn)的各種重疊社團(tuán)發(fā)現(xiàn)算法往往面臨著復(fù)雜度較高或準(zhǔn)確率較低等問(wèn)題。此外，重疊社團(tuán)發(fā)現(xiàn)中重疊程度的控制及結(jié)果的穩(wěn)定性等問(wèn)題也仍然有待解決。
　　本研究主要內(nèi)容包括：⑴提出一種可控重疊程度的重疊社團(tuán)發(fā)現(xiàn)算法。利用邊圖發(fā)現(xiàn)重疊社團(tuán)是一種重要的研究思路，然而簡(jiǎn)單的邊圖重疊社團(tuán)發(fā)現(xiàn)方法并不能保證高質(zhì)量的結(jié)果。本文在邊圖重疊社團(tuán)發(fā)現(xiàn)思想的基礎(chǔ)上，進(jìn)一步發(fā)現(xiàn)，盡管每條邊都可以通過(guò)邊圖下社團(tuán)發(fā)現(xiàn)獲得社團(tuán)標(biāo)簽，但是處于社團(tuán)之間的邊用于標(biāo)識(shí)節(jié)點(diǎn)

4、的社團(tuán)標(biāo)簽時(shí)可能帶來(lái)噪音干擾。由此，我們提出一種在邊圖社團(tuán)發(fā)現(xiàn)結(jié)果的基礎(chǔ)上迭代刪除社團(tuán)間邊標(biāo)簽的算法----CDAEO算法，一方面可以實(shí)現(xiàn)重疊社團(tuán)發(fā)現(xiàn)結(jié)果準(zhǔn)確率的提升，另一方面利用算法中的參數(shù)可以在一定范圍內(nèi)調(diào)節(jié)社區(qū)團(tuán)間的交叉重疊程度。⑵提出一種基于非重疊社團(tuán)的節(jié)點(diǎn)中介度指標(biāo)----社團(tuán)中介度（communitybetweenness），并利用該指標(biāo)設(shè)計(jì)了一種基于節(jié)點(diǎn)分裂的重疊社團(tuán)發(fā)現(xiàn)算法一CBS算法。在社會(huì)網(wǎng)絡(luò)分析的研究中具有高中介度

5、的邊被認(rèn)為是網(wǎng)絡(luò)中具有“橋”屬性的邊，著名的GN算法通過(guò)反復(fù)割斷中介度高的邊而達(dá)到非重疊社團(tuán)發(fā)現(xiàn)的目的。之后有學(xué)者將GN算法延伸到分裂中介度較高的節(jié)點(diǎn)，從而發(fā)現(xiàn)重疊社團(tuán)。盡管這些方法可以在許多真實(shí)網(wǎng)絡(luò)中得到有意義的社團(tuán)結(jié)構(gòu)，但是由于中介度指標(biāo)的計(jì)算復(fù)雜度太高從而限制了它們?cè)诖缶W(wǎng)絡(luò)上的應(yīng)用。針對(duì)這一問(wèn)題，提出一種基于非重疊社團(tuán)結(jié)構(gòu)的局部中介度指標(biāo)，即僅在一對(duì)社團(tuán)的范圍內(nèi)計(jì)算社團(tuán)間節(jié)點(diǎn)的中介度，從而將中介度的計(jì)算限制在一個(gè)有意義的局部網(wǎng)絡(luò)之

6、內(nèi)，大幅降低了中介度計(jì)算的時(shí)間復(fù)雜度，進(jìn)而得到一種高效的重疊社團(tuán)發(fā)現(xiàn)算法。⑶提出一種基于重疊節(jié)點(diǎn)條件的重疊社團(tuán)發(fā)現(xiàn)算法----CONA算法。本文認(rèn)為一個(gè)節(jié)點(diǎn)從非重疊節(jié)點(diǎn)變?yōu)橹丿B節(jié)點(diǎn)應(yīng)該滿足社團(tuán)結(jié)構(gòu)的模塊化程度不被破壞這一基本條件，即社團(tuán)結(jié)構(gòu)的模塊化函數(shù)值至少不會(huì)降低?；谶@一發(fā)現(xiàn)，在選取EQ函數(shù)為重疊社團(tuán)模塊度量函數(shù)的基礎(chǔ)上，我們通過(guò)理論推導(dǎo)得出了非重疊社團(tuán)間及社團(tuán)內(nèi)的潛在重疊節(jié)點(diǎn)應(yīng)滿足的條件，并利用該推導(dǎo)結(jié)果設(shè)計(jì)了一種高效的重疊社團(tuán)發(fā)

7、現(xiàn)算法。實(shí)驗(yàn)表明，該方法在巨型網(wǎng)絡(luò)上具有明顯的速度優(yōu)勢(shì)，而結(jié)果質(zhì)量方面也往往優(yōu)于或至少近似于同類其他算法。⑷提出一種基于均衡多標(biāo)簽傳播的重疊社團(tuán)發(fā)現(xiàn)算法(BMLPA)。標(biāo)簽傳播算法(LPA)是一個(gè)著名的接近線性時(shí)間復(fù)雜度的快速非重疊社團(tuán)發(fā)現(xiàn)算法，其算法過(guò)程非常簡(jiǎn)單明了。Steve將LPA延伸為可發(fā)現(xiàn)重疊社團(tuán)結(jié)構(gòu)的COPRA算法，繼承了LPA快速的優(yōu)良特性，但是也遺傳了LPA結(jié)果穩(wěn)定性差的問(wèn)題。本文提出一種均衡多標(biāo)簽傳播算法，不僅可以在某