復(fù)雜網(wǎng)絡(luò)深度重疊結(jié)構(gòu)的發(fā)現(xiàn)

摘要： 為了更好地了解網(wǎng)絡(luò)，以相似度為基礎(chǔ)，讓節(jié)點(diǎn)選擇多個(gè)相似節(jié)點(diǎn)形成相似節(jié)點(diǎn)對(duì)，通過蒙卡模擬結(jié)果提出了基于最大節(jié)點(diǎn)相似度和度的配對(duì)算法發(fā)現(xiàn)了網(wǎng)絡(luò)的重疊社團(tuán)結(jié)構(gòu)。利用多級(jí)最相似度繼續(xù)優(yōu)化社團(tuán)結(jié)構(gòu)，找出了網(wǎng)絡(luò)社團(tuán)的深層重疊結(jié)構(gòu)和子社團(tuán)結(jié)構(gòu)。提出的算法從真實(shí)網(wǎng)絡(luò)形成社團(tuán)的原因出發(fā)發(fā)現(xiàn)了網(wǎng)絡(luò)的重疊結(jié)構(gòu)，并且進(jìn)一步優(yōu)化社團(tuán)結(jié)構(gòu)，發(fā)現(xiàn)了網(wǎng)絡(luò)的深層重疊社團(tuán)結(jié)構(gòu)和其中的子社團(tuán)結(jié)構(gòu)。

關(guān)鍵詞： 復(fù)雜網(wǎng)絡(luò)；社團(tuán)結(jié)構(gòu)；深度重疊結(jié)構(gòu)；子社團(tuán)結(jié)構(gòu)

中圖分類號(hào)： TP391;O157文獻(xiàn)標(biāo)識(shí)碼： A

Discovery of Deep Overlapping Structures in Complex Networks

GAO Feng

（College of Science， China Three Gorges University， Yichang 443002，China）

Abstract：In order to better understand the network， based on the similarity， let the nodes select multiple similar nodes to form similar node pairs. Through the Monte Carlo simulation results， a pairing algorithm based on the maximum node similarity and degree is proposed to discover the overlapping community structure of the network. Using multi-level most similarity to continue to optimize the community structure， find out the deep overlapping structure and sub-community structure of the network community. The proposed algorithm discovers the overlapping structure of the network based on the reason why the real network forms a community， and further optimizes the community structure， discovering the deep overlapping community structure of the network and its sub-community structure.

Keywords： complex network; community structure; deep overlapping structure; sub-community structure

0 引言

網(wǎng)絡(luò)已成為理解系統(tǒng)間的相互作用（包括對(duì)生物有機(jī)體和人類社會(huì)中多種現(xiàn)象的研究）的一種關(guān)鍵性手段［14］。為了了解復(fù)雜系統(tǒng)中節(jié)點(diǎn)的結(jié)構(gòu)及不同節(jié)點(diǎn)對(duì)于網(wǎng)絡(luò)功能的影響，復(fù)雜網(wǎng)絡(luò)已經(jīng)在各個(gè)領(lǐng)域引起了相當(dāng)大的關(guān)注。復(fù)雜網(wǎng)絡(luò)將個(gè)體抽象成節(jié)點(diǎn)，節(jié)點(diǎn)間的相互作用關(guān)系理解成連邊，利用復(fù)雜網(wǎng)絡(luò)的方法為復(fù)雜系統(tǒng)的分析提供了上帝視角。通過復(fù)雜網(wǎng)絡(luò)模型，科學(xué)家可以利用圖論、統(tǒng)計(jì)物理、控制論、矩陣論等研究、分析復(fù)雜系統(tǒng)的結(jié)構(gòu)、功能和動(dòng)力學(xué)特征，最終實(shí)現(xiàn)對(duì)系統(tǒng)的干預(yù)和控制［45］。

社團(tuán)結(jié)構(gòu)對(duì)于不同的網(wǎng)絡(luò)有著不同的作用，從2002年Girvan和Newman［6］基于復(fù)雜網(wǎng)絡(luò)的邊介數(shù)提出GN算法開始，來(lái)自各個(gè)領(lǐng)域的學(xué)者圍繞社團(tuán)檢測(cè)開展了深入研究。Macropol等［7］提出了一種基于重復(fù)隨機(jī)游走（RRW），用于發(fā)現(xiàn)功能模塊，例如，在大規(guī)模蛋白質(zhì)網(wǎng)絡(luò)中復(fù)合物或通路，RRW考慮了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、邊權(quán)和網(wǎng)絡(luò)之間的遠(yuǎn)程交互關(guān)系。Li J等［8］采用深度搜索和面包搜索相結(jié)合的算法提取小團(tuán)，然后通過一定的規(guī)則，將這些團(tuán)合并成一個(gè)更大的子圖，所提出的算法成功地找到了重疊頂點(diǎn)和橋接頂點(diǎn)社區(qū)。Mahdi等［9］提出了IEDC算法，通過集成框架進(jìn)行一般社區(qū)檢測(cè)，以提取重疊和非重疊的社區(qū)結(jié)構(gòu)，而無(wú)需假設(shè)網(wǎng)絡(luò)上的先前結(jié)構(gòu)連接。

本文首先從社團(tuán)的節(jié)點(diǎn)相似度角度去研究復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的劃分算法，然后根據(jù)數(shù)據(jù)深度優(yōu)化模型發(fā)現(xiàn)社團(tuán)的深度重疊結(jié)構(gòu)，這個(gè)方法同時(shí)解釋了網(wǎng)絡(luò)的重疊結(jié)構(gòu)和社團(tuán)中的子社團(tuán)結(jié)構(gòu)，對(duì)實(shí)際的網(wǎng)絡(luò)結(jié)構(gòu)有很好的解釋分析效果，具有一定的現(xiàn)實(shí)意義。

1 算法：基于最大節(jié)點(diǎn)的度和相似度配對(duì)算法

隨著科學(xué)研究進(jìn)程，越來(lái)越多的研究說明大多數(shù)復(fù)雜網(wǎng)絡(luò)具有社團(tuán)結(jié)構(gòu)，這也就產(chǎn)生了一個(gè)新的研究方向，尋找復(fù)雜網(wǎng)絡(luò)中具有相似特點(diǎn)或關(guān)系密切的小社團(tuán)。這些小社團(tuán)普遍具有內(nèi)部聯(lián)系密切，外部關(guān)聯(lián)稀疏的特點(diǎn)。本文提出了一種算法，來(lái)揭示復(fù)雜網(wǎng)絡(luò)的重疊結(jié)構(gòu)。該算法分析了自然網(wǎng)絡(luò)中社團(tuán)的形成。社團(tuán)的形成是由于個(gè)體具有相似或相同的性質(zhì)，這也說明社團(tuán)是因?yàn)閭€(gè)體的自然選擇形成的。在該算法中定義節(jié)點(diǎn)間的相似度為個(gè)體之間相同的鄰居數(shù)：

Sij=Aij1+∑kAik*Akj（1）

其中，Aij等于0或1，Aij=1表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在連邊，相反Aij=0則表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間不存在連邊。根據(jù)個(gè)體最有可能選擇與其相似或者滿足其期望的個(gè)體形成社團(tuán)，定義節(jié)點(diǎn)之間的相似度Sij。相似度Sij保證了兩個(gè)個(gè)體如果相連，它們的相似度大于1，即它們之間一定存在對(duì)方作為鄰居，同時(shí)個(gè)體只會(huì)選擇與它直接相連的個(gè)體。

本文以23節(jié)點(diǎn)的網(wǎng)絡(luò)為例，網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示，根據(jù)相似度定義計(jì)算任意兩節(jié)點(diǎn)的相似度Sij。每個(gè)節(jié)點(diǎn)選擇相似度最大的節(jié)點(diǎn)形成相似節(jié)點(diǎn)對(duì)，同樣地這些節(jié)點(diǎn)可以存在多個(gè)選擇，形成多個(gè)節(jié)點(diǎn)對(duì)如表1所示。從相似度最大的相似節(jié)點(diǎn)對(duì)開始構(gòu)建社團(tuán)，當(dāng)最大相似度相同時(shí)，優(yōu)先考慮節(jié)點(diǎn)度大的節(jié)點(diǎn)形成的節(jié)點(diǎn)對(duì)，認(rèn)為相似節(jié)點(diǎn)對(duì)是一個(gè)單向選擇關(guān)系，將節(jié)點(diǎn)i加入到節(jié)點(diǎn)j所有社團(tuán)中，因?yàn)楣?jié)點(diǎn)19的多個(gè)選擇，這樣也就形成了重疊的社團(tuán)結(jié)構(gòu)。然后重復(fù)上個(gè)步驟到最后一個(gè)相似節(jié)點(diǎn)對(duì)。

每個(gè)節(jié)點(diǎn)選擇相似度最大的節(jié)點(diǎn)形成相似節(jié)點(diǎn)對(duì)后，按照節(jié)點(diǎn)相似度大小進(jìn)行排序形成社團(tuán)，當(dāng)可以用隨機(jī)的方式選擇節(jié)點(diǎn)。23節(jié)點(diǎn)的網(wǎng)絡(luò)中，節(jié)點(diǎn)通過選擇最大相似度形成節(jié)點(diǎn)對(duì)后，隨機(jī)選擇節(jié)點(diǎn)對(duì)形成社團(tuán)的順序運(yùn)行一萬(wàn)次，統(tǒng)計(jì)用這個(gè)模型得到的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的結(jié)果。如圖2為出現(xiàn)概率最大的劃分結(jié)果（其中相同形狀的節(jié)點(diǎn)屬于同一社團(tuán)，紅色六邊形的節(jié)點(diǎn)表示重疊節(jié)點(diǎn)），圖3為出現(xiàn)頻率第二大的結(jié)果。如圖4，圖5所示，當(dāng)隨機(jī)選擇不同的順序時(shí)，會(huì)有不同的分組結(jié)果。但是其中以最大相似度排序后形成的社團(tuán)結(jié)構(gòu)相同的結(jié)果出現(xiàn)的次數(shù)最多，這也說明了對(duì)于真實(shí)自然的網(wǎng)絡(luò)，社團(tuán)的形成會(huì)優(yōu)先選擇最大相似度大的節(jié)點(diǎn)對(duì)先形成社團(tuán)，同樣由于順序不同網(wǎng)絡(luò)會(huì)具有社團(tuán)結(jié)構(gòu)的多樣化。

真實(shí)網(wǎng)絡(luò)可能由于不同的選擇順序形成不同程度的重疊社團(tuán)現(xiàn)象，為了定量描述這些網(wǎng)絡(luò)的重疊社團(tuán)劃分好壞，這里引入網(wǎng)絡(luò)的擴(kuò)展模塊度EQ［10］。EQ是基于模塊度提出的用來(lái)評(píng)價(jià)重疊社團(tuán)劃分好壞的參數(shù)，當(dāng)每個(gè)頂點(diǎn)只屬于一個(gè)社區(qū)時(shí)，EQ降為模塊度Q，當(dāng)所有節(jié)點(diǎn)都屬于同一個(gè)社區(qū)時(shí)，EQ為0。另外EQ值越高，表示社區(qū)結(jié)構(gòu)重疊越明顯。EQ的計(jì)算公式為

EQ=12m∑i∑v∈Ci，w∈Ci1OvOwAvw－kvkw2m（2）

其中，m=12∑vwAvw為網(wǎng)絡(luò)的總邊數(shù)，kv為節(jié)點(diǎn)v的度，Ov為節(jié)點(diǎn)v所在的社團(tuán)數(shù)量，計(jì)算所有不同的社團(tuán)劃分EQ的大小，因?yàn)榻^大多數(shù)社團(tuán)結(jié)構(gòu)出現(xiàn)的概率很小，這里只取出現(xiàn)次數(shù)最多的6個(gè)社團(tuán)劃分結(jié)果，如表2所示可以看出本文中的模型劃分社團(tuán)結(jié)構(gòu)的出現(xiàn)概率和EQ最大。

基于節(jié)點(diǎn)的度和相似度配對(duì)算法認(rèn)為所有節(jié)點(diǎn)只能選擇最相似節(jié)點(diǎn)形成相似節(jié)點(diǎn)對(duì)，這樣可以揭示實(shí)際社團(tuán)的重疊結(jié)構(gòu)，但是對(duì)于不同網(wǎng)絡(luò)來(lái)說這種選擇可能是更深層的，節(jié)點(diǎn)也可以選擇相似度不是那么大的節(jié)點(diǎn)同樣形成節(jié)點(diǎn)對(duì)。我們讓節(jié)點(diǎn)可以選擇更多不同相似度的節(jié)點(diǎn)形成節(jié)點(diǎn)對(duì)，進(jìn)一步更新本文的社團(tuán)結(jié)構(gòu)，找到重疊程度更大的社團(tuán)結(jié)構(gòu)。

2 深層重疊結(jié)構(gòu)

對(duì)于真實(shí)網(wǎng)絡(luò)來(lái)講，讓所有的節(jié)點(diǎn)去選擇最大相似度節(jié)點(diǎn)形成節(jié)點(diǎn)對(duì)，然后根據(jù)節(jié)點(diǎn)對(duì)形成社團(tuán)。但是對(duì)于實(shí)際網(wǎng)絡(luò)個(gè)體可能不僅僅只選擇最相似的節(jié)點(diǎn)，同樣的也會(huì)選擇其他相似度較小的節(jié)點(diǎn)形成節(jié)點(diǎn)對(duì)，但是這些節(jié)點(diǎn)對(duì)只會(huì)讓劃分的社團(tuán)數(shù)量減少，社團(tuán)的重疊性增加。為了找到重疊程度更大的結(jié)構(gòu)，本文利用多級(jí)相似度進(jìn)一步優(yōu)化社團(tuán)，算法流程如圖6所示。

根據(jù)本文的算法得到了最相似節(jié)點(diǎn)對(duì)形成的社團(tuán)后，計(jì)算各個(gè)節(jié)點(diǎn)與社團(tuán)的聯(lián)系度，社團(tuán)的聯(lián)系度為該節(jié)點(diǎn)與各個(gè)社團(tuán)中所有的連邊條數(shù)。從圖8中可以看19號(hào)節(jié)點(diǎn)與社團(tuán)3中的20號(hào)、21號(hào)和22號(hào)直接相連，與社團(tuán)4中的13號(hào)、14號(hào)和16號(hào)節(jié)點(diǎn)直接相連，所以19號(hào)節(jié)點(diǎn)與社團(tuán)3和社團(tuán)4的聯(lián)系度都為3。圖7給出了所有節(jié)點(diǎn)的社團(tuán)聯(lián)系度。

從圖7（其社團(tuán)結(jié)構(gòu)的劃分情況見圖8一級(jí)相似度社團(tuán)劃分）看到，19號(hào)節(jié)點(diǎn)與社團(tuán)3和社團(tuán)4的聯(lián)系度相同，所以在第一步用最大相似度劃分社團(tuán)時(shí)只發(fā)現(xiàn)了19號(hào)節(jié)點(diǎn)為重疊節(jié)點(diǎn)。但是9號(hào)、17號(hào)、18號(hào)節(jié)點(diǎn)都和兩個(gè)或多個(gè)社團(tuán)聯(lián)系度相近，它們可能也是重疊的節(jié)點(diǎn)。用最相似節(jié)點(diǎn)對(duì)算法并沒有發(fā)現(xiàn)它們，可能是使用數(shù)據(jù)的深度不夠，網(wǎng)絡(luò)中的個(gè)體不僅僅只會(huì)選擇最相似的節(jié)點(diǎn)形成社團(tuán)，如果只用最相似節(jié)點(diǎn)對(duì)可能會(huì)丟掉了一些重要的信息。鑒于此，本文引入二級(jí)最大相似度，進(jìn)一步改進(jìn)劃分的社團(tuán)。讓節(jié)點(diǎn)選擇第二相似的節(jié)點(diǎn)形成節(jié)點(diǎn)對(duì)，按照上文的步驟進(jìn)行。劃分結(jié)果如圖9所示。

當(dāng)同時(shí)使用一級(jí)最大相似度和二級(jí)最大相似度后，原來(lái)的社團(tuán)5{17，18}消失了，變成了社團(tuán)3和社團(tuán)4的重疊節(jié)點(diǎn)，17號(hào)和18號(hào)節(jié)點(diǎn)對(duì)于社團(tuán)3和社團(tuán)4的聯(lián)系密切并且聯(lián)系度相似，在二級(jí)相似度的作用下17號(hào)和18號(hào)節(jié)點(diǎn)順利地進(jìn)入到兩個(gè)社團(tuán)中。在社團(tuán)3和社團(tuán)4中我們認(rèn)為，并不是所有的節(jié)點(diǎn)聯(lián)系一樣密切，由于17號(hào)節(jié)點(diǎn)和18號(hào)節(jié)點(diǎn)是通過二級(jí)最大相似度進(jìn)入的，所以明顯在這兩個(gè)社團(tuán)中17號(hào)和18號(hào)他們兩個(gè)關(guān)系更加親密。將原來(lái)處于同一社團(tuán)的節(jié)點(diǎn)加入到另一個(gè)相同社團(tuán)中形成的結(jié)構(gòu)稱為這個(gè)社團(tuán)的子社團(tuán)，如{17，18}。

為了找到更深層次的重疊結(jié)構(gòu)和更多的子社團(tuán)結(jié)構(gòu)，本文引入更多的最大相似度去劃分社團(tuán)，對(duì)于社團(tuán)劃分過程具體思路與二級(jí)最大相似度相似，按照本文提出的算法的步驟進(jìn)行劃分社團(tuán)，社團(tuán)結(jié)構(gòu)演化結(jié)果如圖8～圖11所示。具體的算法流程：

第1步：找到所有節(jié)點(diǎn)的最相似節(jié)點(diǎn)，其中單個(gè)節(jié)點(diǎn)可能存在多個(gè)最相似節(jié)點(diǎn)形成節(jié)點(diǎn)對(duì)。

第2步：對(duì)于所有節(jié)點(diǎn)對(duì)按照相似度大小和節(jié)點(diǎn)度的大小排序，將節(jié)點(diǎn)對(duì)視為單向選擇關(guān)系，節(jié)點(diǎn)對(duì)的相似度和節(jié)點(diǎn)的度越大越快形成社團(tuán)。最大相似度形成節(jié)點(diǎn)對(duì)用完后得到一級(jí)重疊社團(tuán)結(jié)構(gòu)。

第3步：根據(jù)相似度大小讓所有節(jié)點(diǎn)選擇相似度第二大的節(jié)點(diǎn)形成新的節(jié)點(diǎn)對(duì)，按照第1步、第2步重新更新社團(tuán)結(jié)構(gòu)。利用第二大相似度更新社團(tuán)得到新二級(jí)社團(tuán)結(jié)構(gòu)。

第4步：利用節(jié)點(diǎn)間的不同相似度依次得到更深層次的社團(tuán)結(jié)構(gòu)。

從圖10得到3號(hào)、4號(hào)節(jié)點(diǎn)分別通過三級(jí)、四級(jí)最大相似度加入社團(tuán)4，由圖7可以看出，3號(hào)節(jié)點(diǎn)對(duì)于社團(tuán)2和社團(tuán)4的聯(lián)系度差異小于3號(hào)節(jié)點(diǎn)與社團(tuán)2和社團(tuán)4的聯(lián)系度差異，這也說明了節(jié)點(diǎn)對(duì)于多個(gè)社團(tuán)聯(lián)系度差異越小，那么這個(gè)節(jié)點(diǎn)的重疊性就越明顯。這里定義區(qū)分不同的重疊節(jié)點(diǎn)類型，按照這些重疊節(jié)點(diǎn)是在第幾級(jí)最大相似度被發(fā)現(xiàn)出來(lái)的，如19號(hào)節(jié)點(diǎn)為一級(jí)重疊節(jié)點(diǎn)，17號(hào)、18號(hào)、9號(hào)、7號(hào)、8號(hào)節(jié)點(diǎn)為二級(jí)重疊節(jié)點(diǎn)。不同級(jí)數(shù)的重疊節(jié)點(diǎn)代表兩個(gè)社團(tuán)之間因?yàn)檫@些節(jié)點(diǎn)的重疊性不同。

如圖9利用二級(jí)最大相似度更新社團(tuán)后，發(fā)現(xiàn)17號(hào)，18號(hào)節(jié)點(diǎn)同時(shí)加入到了社團(tuán)3和社團(tuán)4中，讓社團(tuán)3和社團(tuán)4重疊程度變大，并且對(duì)于社團(tuán)3來(lái)講17號(hào)，18號(hào)節(jié)點(diǎn)就是社團(tuán)的子社團(tuán)結(jié)構(gòu)。同樣的17號(hào)，18號(hào)也是社團(tuán)4的子社團(tuán)結(jié)構(gòu)。處于同一社團(tuán)的節(jié)點(diǎn)比其他社團(tuán)節(jié)點(diǎn)的聯(lián)系密切，對(duì)于社團(tuán)中存在的子社團(tuán)結(jié)構(gòu)它們的親近程度要大于和其他同一社團(tuán)的節(jié)點(diǎn)。

隨著相似度級(jí)數(shù)增加數(shù)據(jù)深度越深，可用的最大相似度節(jié)點(diǎn)對(duì)數(shù)量就越少，這是由于只有小部分節(jié)點(diǎn)的相似節(jié)點(diǎn)對(duì)比較多，并且越到后面節(jié)點(diǎn)對(duì)數(shù)據(jù)對(duì)于社團(tuán)結(jié)構(gòu)的影響就越小。當(dāng)?shù)阶詈笠患?jí)的相似節(jié)點(diǎn)對(duì)用完后得到的社團(tuán)結(jié)構(gòu)就是這個(gè)網(wǎng)絡(luò)最可能存在重疊度最大的穩(wěn)定結(jié)構(gòu)。

3 真實(shí)網(wǎng)絡(luò)的應(yīng)用結(jié)果

本文選取4個(gè)真實(shí)網(wǎng)絡(luò)，如表3所示，美國(guó)跆拳道俱樂部（34節(jié)點(diǎn)），海豚社交網(wǎng)絡(luò)（62節(jié)點(diǎn)），美國(guó)足球比賽網(wǎng)絡(luò)（115節(jié)點(diǎn)），Hamsterster社會(huì)網(wǎng)絡(luò)（2 426節(jié)點(diǎn)），將算法應(yīng)用到這個(gè)網(wǎng)絡(luò)中得到了一些結(jié)果。對(duì)于大多數(shù)的網(wǎng)絡(luò)只需要利用較少的相似度級(jí)數(shù)，就能找到EQ最大的社團(tuán)結(jié)構(gòu)，但是對(duì)于級(jí)數(shù)的增加可以找到網(wǎng)絡(luò)深層次的社團(tuán)結(jié)構(gòu)更多的重疊節(jié)點(diǎn)更大規(guī)模的子社團(tuán)結(jié)構(gòu)。

將本文的算法應(yīng)用到Hamsterster社會(huì)網(wǎng)絡(luò)中得到了網(wǎng)絡(luò)的深度重疊結(jié)構(gòu)。圖12a可以看出級(jí)數(shù)越大相似節(jié)點(diǎn)數(shù)越少，因?yàn)楣?jié)點(diǎn)選擇相似節(jié)點(diǎn)形成節(jié)點(diǎn)對(duì)，在真實(shí)網(wǎng)絡(luò)中只有少部分節(jié)點(diǎn)的度較大，這少部分節(jié)點(diǎn)可以有多級(jí)選擇形成節(jié)點(diǎn)對(duì)，其他節(jié)點(diǎn)的選擇就會(huì)很少。同時(shí)當(dāng)級(jí)數(shù)增加時(shí)，網(wǎng)絡(luò)的社團(tuán)也在合并使得社團(tuán)數(shù)目減少，但是只有前幾級(jí)節(jié)點(diǎn)對(duì)數(shù)據(jù)對(duì)于社團(tuán)數(shù)目影響較大，后面就不改變社團(tuán)的數(shù)目了，這也說明了只需要少部分相似節(jié)點(diǎn)對(duì)級(jí)數(shù)就可以讓網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)達(dá)到穩(wěn)定的深度重疊狀態(tài)。

從圖12b中容易看出Hamsterster社會(huì)網(wǎng)絡(luò)中級(jí)數(shù)增大社團(tuán)的節(jié)點(diǎn)數(shù)目、重疊節(jié)點(diǎn)比例以及與該社團(tuán)有重疊的社團(tuán)比例同時(shí)增多，并且在十級(jí)相似度之后這3個(gè)都趨于一個(gè)穩(wěn)定值。對(duì)于得到的深度重疊結(jié)構(gòu)看到它重疊節(jié)點(diǎn)的比例達(dá)到了80%左右，社團(tuán)中幾乎大部分節(jié)點(diǎn)都是與其他社團(tuán)的重疊節(jié)點(diǎn)，對(duì)于真實(shí)網(wǎng)絡(luò)來(lái)說大部分的個(gè)體都會(huì)有多個(gè)選擇，這也導(dǎo)致了社團(tuán)的重疊率比較大。

圖13是最大的一個(gè)社團(tuán)隨著級(jí)數(shù)增加發(fā)現(xiàn)的子社團(tuán)，其中圖13a給出了第2，3，4和5級(jí)相似節(jié)點(diǎn)對(duì)發(fā)現(xiàn)的子社團(tuán)規(guī)模，圖13b為第2級(jí)子社團(tuán)節(jié)點(diǎn)在前一級(jí)所屬的社團(tuán)，亮點(diǎn)表示屬于這一社團(tuán)，在第2級(jí)中發(fā)現(xiàn)了65個(gè)子社團(tuán)，其中最大的子社團(tuán)有20個(gè)節(jié)點(diǎn)同屬于上一級(jí)相同的社團(tuán)，同一社團(tuán)中的節(jié)點(diǎn)聯(lián)系密切，屬于同一社團(tuán)的子社團(tuán)具有更密切的關(guān)系。所以對(duì)于重疊網(wǎng)絡(luò)中的子社團(tuán)發(fā)現(xiàn)具有一定的意義。

圖14展現(xiàn)了最大的一個(gè)社團(tuán)和其他社團(tuán)的重疊情況，其中圓圈里面的數(shù)字表示節(jié)點(diǎn)數(shù)的大小，這里只考慮與最大社團(tuán)重疊的社團(tuán)。當(dāng)一個(gè)社團(tuán)與最大社團(tuán)有重疊時(shí)，它們之間就會(huì)有連邊，連邊的權(quán)重表示兩個(gè)社團(tuán)重疊的節(jié)點(diǎn)數(shù)目。圖14a是第一級(jí)相似節(jié)點(diǎn)對(duì)最大社團(tuán)的重疊情況，圖14b為最后一級(jí)相似節(jié)點(diǎn)對(duì)最大社團(tuán)的重疊情況（忽略了重疊節(jié)點(diǎn)數(shù)小于十的社團(tuán)）。比較第一級(jí)和最后一級(jí)明顯看到最大的社團(tuán)重疊程度增大了很多，這也是網(wǎng)絡(luò)的深度重疊結(jié)構(gòu)。

4 結(jié)論

本文從真實(shí)網(wǎng)絡(luò)形成社團(tuán)的原因出發(fā)，假設(shè)社團(tuán)的形成是節(jié)點(diǎn)選擇最相似節(jié)點(diǎn)的結(jié)果，并且具有更大相似度和度的節(jié)點(diǎn)對(duì)會(huì)優(yōu)先形成社團(tuán)，每一個(gè)節(jié)點(diǎn)可以對(duì)多個(gè)社團(tuán)有選擇權(quán)力，發(fā)現(xiàn)了網(wǎng)絡(luò)中社團(tuán)的重疊結(jié)構(gòu)，合理地說明了重疊節(jié)點(diǎn)的物理意義。然后通過增加相似度級(jí)數(shù)，利用多級(jí)最相似度繼續(xù)優(yōu)化社團(tuán)，找出了網(wǎng)絡(luò)中的深度重疊結(jié)構(gòu)和重疊社團(tuán)的子社團(tuán)結(jié)構(gòu)，解釋了網(wǎng)絡(luò)是由節(jié)點(diǎn)對(duì)到小社團(tuán)再到交疊社團(tuán)的一個(gè)演變過程。本文的模型揭示了網(wǎng)絡(luò)的深度重疊結(jié)構(gòu)，并發(fā)現(xiàn)了社團(tuán)的子結(jié)構(gòu)，對(duì)實(shí)際網(wǎng)絡(luò)結(jié)構(gòu)有很好的解釋分析效果。

本文的模型對(duì)于無(wú)權(quán)無(wú)向網(wǎng)絡(luò)的重疊社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)具有很好的效果，后續(xù)會(huì)嘗試對(duì)于有權(quán)重有方向的網(wǎng)絡(luò)進(jìn)行重疊社團(tuán)劃分，同時(shí)會(huì)嘗試擴(kuò)大網(wǎng)絡(luò)的規(guī)模，加入對(duì)人工基準(zhǔn)網(wǎng)絡(luò)［1113］的研究和分析。當(dāng)然本文的模型給出了復(fù)雜網(wǎng)絡(luò)的深度重疊結(jié)構(gòu)，提供了一種新的社團(tuán)發(fā)現(xiàn)思路，對(duì)于社團(tuán)中去尋找更小的子社團(tuán)，屬于同一社團(tuán)的節(jié)點(diǎn)會(huì)被更細(xì)致地進(jìn)行劃分，這種方式可以讓我們更深入地了解社團(tuán)結(jié)構(gòu)。更深層次的網(wǎng)絡(luò)結(jié)構(gòu)是接下來(lái)要進(jìn)一步研究的內(nèi)容。

參考文獻(xiàn)：

［1］PAWAN K， RAVINS D. Formalising and detecting community structures in real world complex networks［J］.Journal of Systems Science amp; Complexity，2021，34（1）：180205.

［2］李輝，陳福才，張建朋，等. 復(fù)雜網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)算法綜述［J］. 計(jì)算機(jī)應(yīng)用研究，2021，38（6）：16111618.

LI H，CHEN F，ZHANG J， et al. Survey of community detection algorithms in complex network［J］. Application Research of Computers，2021，38（6）：16111618.

［3］CHENG F， WANG C， ZHANG X， et al. A local-neighborhood information based overlapping community detection algorithm for large-scale complex networks［J］. IEEE/ACM Transactions on Networking， 2021，29（2）： 543556.

［4］CHAKRABORTY S， MUHURI S， Das D. Detection of constant member and overlapping community from dynamic literary network［J］. Social Network Analysis and Mining，2021，11（1）：77.

［5］李永寧， 吳曄， 張倫. 動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)研究綜述［J］. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 2021， 18（2）： 18.

LI Y， WU Y， ZHANG L. A review of dynamic community detection［J］. Complex Systems and Complexity Science， 2021， 18（2）： 18.

［6］NEWMAN M， GIRVAN M. Finding and evaluating community structure in networks［J］.Physical Review E， 2004， 69（2）：026113.

［7］KATHY M， TOLGA C， AMBUJ K. RRW： repeated random walks on genome-scale protein networks for local cluster discovery［J］. BMC Bioinformatics， 2009， 10（1）： 283.

［8］LI J， WANG X， CUI Y. Uncovering the overlapping community structure of complex networks by maximal cliques［J］. Physica A： Statistical Mechanics and Its Applications， 2014， 415（1）： 398406.

［9］HAJIABADI M，ZARE H， Bobarshad H. IEDC： An integrated approach for overlapping and non-overlapping community detection［J］. Knowledge-Based Systems， 2017， 123（1）：188199.

［10］ NICOSIA V， MANGIONI G， CARCHIOLO V， et al. Extending the definition of modularity to directed graphs with overlapping communities［J］. Journal of Statistical Mechanics Theory amp; Experiment， 2009， 2009（3）：31663168.

［11］ LIU H， LI G. Overlapping community detection method based on network representation learning and density peaks［J］.IEEE Access， 2020， 8（99）：1.

［12］ SHI P， HE K， BINDEL D， et al. Locally-biased spectral approximation for community detection［J］. Knowledge-Based Systems， 2019， 164（1）：459472.

［13］ DEVI J C， POOVAMMAL E. An analysis of overlapping community detection algorithms in social networks［J］. Procedia Computer Science， 2016， 89：349358.

（責(zé)任編輯 李 進(jìn)）