利用堆數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)鄰域重疊社團(tuán)結(jié)構(gòu)挖掘

任成磊, 韓定定, 蒲　鵬, 張嘉誠

(華東師范大學(xué)信息科學(xué)技術(shù)學(xué)院, 上海 200241)

?

利用堆數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)鄰域重疊社團(tuán)結(jié)構(gòu)挖掘

任成磊, 韓定定, 蒲鵬, 張嘉誠

(華東師范大學(xué)信息科學(xué)技術(shù)學(xué)院, 上海 200241)

摘要:基于當(dāng)前復(fù)雜網(wǎng)絡(luò)中社團(tuán)劃分算法普遍存在算法復(fù)雜度過高以及重疊節(jié)點(diǎn)挖掘不準(zhǔn)確的局限性，提出了一種高效、快速、準(zhǔn)確的社團(tuán)劃分算法?；谪澙匪惴?，建立最大模塊度矩陣，并采用堆數(shù)據(jù)結(jié)構(gòu)，劃分非鄰域重疊社團(tuán)。通過分析局部網(wǎng)絡(luò)的連邊情況，計(jì)算鄰域社團(tuán)的劃分密度，以準(zhǔn)確挖掘社團(tuán)間的重疊節(jié)點(diǎn)。新算法經(jīng)過仿真分析和實(shí)證研究表明，算法復(fù)雜度降到近線性。

關(guān)鍵詞：社團(tuán)挖掘；鄰域重疊；模塊度；劃分密度；時間復(fù)雜度

0引言

隨著對網(wǎng)絡(luò)性質(zhì)的物理意義和數(shù)學(xué)特性的深入研究，人們發(fā)現(xiàn)在社會網(wǎng)、神經(jīng)網(wǎng)、蛋白質(zhì)網(wǎng)、萬維網(wǎng)、通信網(wǎng)等網(wǎng)絡(luò)中，普遍存在著一種特性——社團(tuán)結(jié)構(gòu)[1-4]。網(wǎng)絡(luò)是由若干個團(tuán)簇構(gòu)成的，每個團(tuán)簇內(nèi)部的節(jié)點(diǎn)之間的連接非常緊密，但是各個團(tuán)簇之間的連接卻相對比較稀疏。這些子團(tuán)簇就被稱為社團(tuán)，社團(tuán)結(jié)構(gòu)可以直觀形象地揭示一個網(wǎng)絡(luò)內(nèi)部是如何自組織的，以及各個團(tuán)簇之間的關(guān)系。因此，復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的探測研究，對于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)分析、功能的理解和網(wǎng)絡(luò)行為動力學(xué)預(yù)測等有著重要的意義[5-6]。

近幾年，復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的挖掘得到了各個領(lǐng)域科學(xué)家的廣泛研究。Kernighan等[7]基于貪婪算法的基本原理，通過優(yōu)化兩個社團(tuán)之間的連邊，準(zhǔn)確地將網(wǎng)絡(luò)劃分為兩個已知大小的社團(tuán)。Giran等[8]基于各個節(jié)點(diǎn)間的連接強(qiáng)度，提出了一種分裂方法，通過不斷地從網(wǎng)絡(luò)中移除介數(shù)最大的邊，把網(wǎng)絡(luò)自然地劃分為不同的社團(tuán)結(jié)構(gòu)。Newman等[9]基于模塊度，提出了一種快速凝聚算法，算法具有較低的復(fù)雜度，可以實(shí)現(xiàn)大規(guī)模網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的快速劃分。Clauset等[10]在Newman快速算法的基礎(chǔ)上，通過更新網(wǎng)絡(luò)的模塊度，提出了一種新的貪婪算法，該算法的復(fù)雜度只有O(nlog2n)，已接近線性，是目前在事先不知道社團(tuán)數(shù)目的情況下，最快的社團(tuán)劃分算法。以上諸多算法可以將網(wǎng)絡(luò)劃分為若干個互相分離的社團(tuán)，而現(xiàn)實(shí)中很多網(wǎng)絡(luò)并不存在絕對的彼此獨(dú)立的社團(tuán)結(jié)構(gòu)；相反，他們是由許多彼此重疊的社團(tuán)構(gòu)成。比如，我們每個人根據(jù)不同的分類方法都會屬于多個不同的社團(tuán)(如學(xué)校、家庭、不同的興趣小組等)，因此以上的社團(tuán)劃分算法并不適合重疊社團(tuán)結(jié)構(gòu)的劃分[11]。近幾年，重疊社團(tuán)結(jié)構(gòu)的豐富性引起了眾多學(xué)者的廣泛研究，很多重疊社團(tuán)結(jié)構(gòu)挖掘算法被提出。Palla等[12]提出了一種派系過濾算法，通過挖掘網(wǎng)絡(luò)中的全耦合子圖，實(shí)現(xiàn)重疊社團(tuán)結(jié)構(gòu)劃分。楊歡等[13]基于完全子圖的社團(tuán)探測算法，通過計(jì)算每一對完全子圖的重疊節(jié)點(diǎn)個數(shù)，設(shè)置合并完全子圖的閾值，快速地實(shí)現(xiàn)網(wǎng)絡(luò)中重疊社團(tuán)結(jié)構(gòu)挖掘。Ahn等[14]通過對網(wǎng)絡(luò)中的邊進(jìn)行社團(tuán)劃分，而不是傳統(tǒng)方法中的節(jié)點(diǎn)，以劃分密度D為重疊社團(tuán)的檢測標(biāo)準(zhǔn)，有效地實(shí)現(xiàn)了網(wǎng)絡(luò)中重疊節(jié)點(diǎn)的挖掘。張忠元等[15]提出一種二元對稱矩陣分解方法，首先利用非負(fù)對稱矩陣算法對網(wǎng)絡(luò)的社團(tuán)成員矩陣初始化，然后對初始成員矩陣進(jìn)行優(yōu)化，最后統(tǒng)計(jì)各個社團(tuán)中的連邊數(shù)以及節(jié)點(diǎn)數(shù)并計(jì)算整個網(wǎng)絡(luò)的劃分密度，從而準(zhǔn)確地挖掘出社團(tuán)間的重疊部分。鄰域重疊社團(tuán)劃分算法雖然可以準(zhǔn)確地挖掘網(wǎng)絡(luò)中的重疊節(jié)點(diǎn)，但是在網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的劃分上卻存在模糊性，社團(tuán)劃分不夠準(zhǔn)確，此外算法復(fù)雜度較高，難以實(shí)現(xiàn)大規(guī)模網(wǎng)絡(luò)重疊節(jié)點(diǎn)挖掘。針對上述問題，本文將二者的優(yōu)勢揉合到一起，利用堆的數(shù)據(jù)結(jié)構(gòu)，快速地實(shí)現(xiàn)非鄰域社團(tuán)結(jié)構(gòu)劃分，并通過分析局部網(wǎng)絡(luò)的連邊情況，利用劃分密度準(zhǔn)確地挖掘出網(wǎng)絡(luò)中的重疊節(jié)點(diǎn)。

1模塊度Q和劃分密度D

為了衡量網(wǎng)絡(luò)社團(tuán)劃分結(jié)果的合理性，科學(xué)家提出了一系列衡量標(biāo)準(zhǔn)。其中，在非鄰域社團(tuán)結(jié)構(gòu)劃分方面，Newman等[8]引進(jìn)了一個衡量網(wǎng)絡(luò)劃分質(zhì)量的標(biāo)準(zhǔn)——模塊度Q。Q值表征了網(wǎng)絡(luò)社團(tuán)劃分的質(zhì)量，Q值越大，表明社團(tuán)內(nèi)部的連邊越多，而社團(tuán)之間的連邊越少，此時社團(tuán)劃分質(zhì)量也越高。模塊度值Q的公式為

(1)

其中，m為網(wǎng)絡(luò)中的邊數(shù)，vw為節(jié)點(diǎn)，Avw為網(wǎng)絡(luò)的連接矩陣中的元素，若節(jié)點(diǎn)v和節(jié)點(diǎn)w之間有邊相連接則值為1，否則為0，kv表示節(jié)點(diǎn)v的度值，kw表示節(jié)點(diǎn)w的度值，若節(jié)點(diǎn)v和節(jié)點(diǎn)w屬于一個社團(tuán)，則δ(cv，cw)函數(shù)值為1，否則為0。式(1)的物理意義是：網(wǎng)絡(luò)中連接兩個同種類型的節(jié)點(diǎn)的邊(即社團(tuán)內(nèi)部邊)的比例，減去在同樣的社團(tuán)結(jié)構(gòu)下任意連接這兩個節(jié)點(diǎn)的邊的比例的期望值。如果社團(tuán)內(nèi)部邊的比例不大于任意連接時的期望值，則有Q=0。Q的上限值是1，Q越接近這個值，就說明社團(tuán)結(jié)構(gòu)越明顯。實(shí)際網(wǎng)絡(luò)中，該值通常位于0.3～0.7之間。在以往的非鄰域重疊社團(tuán)劃分研究工作中，模塊度Q被作為一個重要的衡量標(biāo)準(zhǔn)，用以衡量社團(tuán)劃分結(jié)果的準(zhǔn)確性。

隨著復(fù)雜網(wǎng)絡(luò)社團(tuán)挖掘研究的深入，人們發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中很多社團(tuán)之間都存在著鄰域重疊結(jié)構(gòu)。因?yàn)閭鹘y(tǒng)的社團(tuán)劃分算法難以實(shí)現(xiàn)鄰域重疊結(jié)構(gòu)劃分，所以許多針對網(wǎng)絡(luò)鄰域重疊社團(tuán)結(jié)構(gòu)的挖掘算法被提出。傳統(tǒng)的模塊度Q已經(jīng)難以準(zhǔn)確衡量鄰域重疊社團(tuán)劃分算法的準(zhǔn)確性，Ahn等[14]基于局部網(wǎng)絡(luò)的連邊情況，提出了一個衡量網(wǎng)絡(luò)鄰域社團(tuán)劃分質(zhì)量的標(biāo)準(zhǔn)——劃分密度D。在一個有M條邊，N個節(jié)點(diǎn)的網(wǎng)絡(luò)中，社團(tuán)c的劃分密度為

(2)

其中，Dc為社團(tuán)c的劃分密度，mc為社團(tuán)c中的邊數(shù)，nc為社團(tuán)c中的節(jié)點(diǎn)數(shù)。整個網(wǎng)絡(luò)的劃分密度是所有子社團(tuán)密度值之和的平均值，對應(yīng)的公式為

(3)

2基于堆數(shù)據(jù)結(jié)構(gòu)的社團(tuán)挖掘

堆數(shù)據(jù)結(jié)構(gòu)是一種數(shù)組對象，可以被認(rèn)為是一棵完全二叉樹。根據(jù)完全二叉樹中節(jié)點(diǎn)的優(yōu)先級可以將堆分為最大堆和最小堆兩種類型。最大堆中父節(jié)點(diǎn)的值大于兩個子節(jié)點(diǎn)的值，而最小堆中父節(jié)點(diǎn)的值小于兩個子節(jié)點(diǎn)的值。圖1是最大堆與最小堆的一個例子。

圖1　最大堆與最小堆示例圖

由于堆具有獨(dú)特的數(shù)據(jù)結(jié)構(gòu)，常被用于實(shí)現(xiàn)數(shù)據(jù)排序，算法簡單，復(fù)雜度低。在本文中，首先采用最大堆數(shù)據(jù)排序法來計(jì)算和更新網(wǎng)絡(luò)的模塊度，快速地實(shí)現(xiàn)網(wǎng)絡(luò)的非鄰域社團(tuán)結(jié)構(gòu)劃分，并以此作為初始的社團(tuán)成員矩陣；然后，再對網(wǎng)絡(luò)中的邊進(jìn)行分析，若一條邊中的兩個節(jié)點(diǎn)在兩個不同的社團(tuán)中，那么這兩個節(jié)點(diǎn)中有一個節(jié)點(diǎn)應(yīng)該是鄰域社團(tuán)的重疊節(jié)點(diǎn)，結(jié)合當(dāng)前合理的鄰域重疊社團(tuán)衡量標(biāo)準(zhǔn)——劃分密度D，分析該對節(jié)點(diǎn)中哪一個節(jié)點(diǎn)算作重疊節(jié)點(diǎn)更加合理。

在本文中，鄰域重疊社團(tuán)結(jié)構(gòu)挖掘算法一共用到了3種數(shù)據(jù)結(jié)構(gòu)：

1)模塊度增量矩陣ΔQij：它與網(wǎng)絡(luò)的鄰接矩陣A一樣，是一個稀疏矩陣，初始化公式如下所示：

(4)

其中，m為網(wǎng)絡(luò)中的總邊數(shù)，ki為節(jié)點(diǎn)i的度，kj為節(jié)點(diǎn)j的度。

2)最大堆H。最大堆H中存儲的是模塊度增量矩陣ΔQij每一行的最大元素，以及最大元素對應(yīng)的兩個社團(tuán)的編號i和j。

3)輔助向量α1：輔助向量初始化公式為

(5)

其中，m為網(wǎng)絡(luò)中的總邊數(shù)，ki為節(jié)點(diǎn)i的度。

基于以上3種數(shù)據(jù)結(jié)構(gòu)，鄰域重疊社團(tuán)挖掘算法流程為

1)初始化。利用公式(4)、(5)計(jì)算網(wǎng)絡(luò)初始化模塊度增量矩陣ΔQij和輔助向量i，得到了初始化的模塊度增量矩陣以后，利用最大堆排序法，讀取增量矩陣中的每一行最大元素ΔQij構(gòu)成最大堆H。

2)從最大堆H中選擇最大的ΔQij，合并相應(yīng)的社團(tuán)i和社團(tuán)j，標(biāo)記合并后的社團(tuán)序號為j；并更新模塊度增量矩陣ΔQij、最大堆H和輔助向量αi，以及合并之后的模塊度值Q+ΔQij。

(1)ΔQij的更新：刪除第i行和第i列的元素，更新第j行和第j列的元素：

(6)

(2)H的更新：每次更新ΔQij后，更新最大堆中相應(yīng)行的最大元素。

(3)αi的更新：

(7)

3)重復(fù)步驟2)，直到最大堆H中的元素全部變成負(fù)值，此時得到的就是網(wǎng)絡(luò)最佳的非鄰域重疊社團(tuán)結(jié)構(gòu)。

4)讀取網(wǎng)絡(luò)連邊Lsd，若當(dāng)前邊對應(yīng)的兩個節(jié)點(diǎn)從屬于不同的社團(tuán)，分別將源節(jié)點(diǎn)(s)和目標(biāo)節(jié)點(diǎn)(d)作為重疊節(jié)點(diǎn)，重新統(tǒng)計(jì)各個社團(tuán)中的連邊數(shù)和節(jié)點(diǎn)數(shù)，利用劃分密度公式計(jì)算得到源節(jié)點(diǎn)的劃分密度DS和目標(biāo)節(jié)點(diǎn)的劃分密度Dd。若DS大于Dd，則源節(jié)點(diǎn)是兩個社團(tuán)間的重疊節(jié)點(diǎn)，反之目標(biāo)節(jié)點(diǎn)是兩個社團(tuán)間的重疊節(jié)點(diǎn)，記錄重疊節(jié)點(diǎn)。

5)重復(fù)步驟4)，直到網(wǎng)絡(luò)中的所有邊都被檢測完畢，將非鄰域重疊社團(tuán)成員矩陣和重疊節(jié)點(diǎn)結(jié)合，實(shí)現(xiàn)網(wǎng)絡(luò)的鄰域重疊社團(tuán)結(jié)構(gòu)挖掘。

3算法復(fù)雜度近線性

本文提出的鄰域重疊社團(tuán)結(jié)構(gòu)挖掘算法主要是由兩部分組成：非鄰域重疊社團(tuán)結(jié)構(gòu)劃分和社團(tuán)間重疊節(jié)點(diǎn)挖掘。本文基于堆數(shù)據(jù)結(jié)構(gòu)快速實(shí)現(xiàn)社團(tuán)成員矩陣的初始化，對于一個有n個節(jié)點(diǎn)，m條邊的網(wǎng)絡(luò)，算法復(fù)雜度為O(mdlogn)(d表示網(wǎng)絡(luò)的深度)[9]。而現(xiàn)實(shí)中很多網(wǎng)絡(luò)都是稀疏網(wǎng)絡(luò)，則有m≈n、d≈logn，在這種情況下，非鄰域重疊社團(tuán)劃分算法的復(fù)雜度近似為O(nlog2n)。此時算法復(fù)雜度近似為線性，運(yùn)行速度快。此外，算法本身基于模塊度值，通過更新模塊度增量矩陣得到整個網(wǎng)絡(luò)的最大模塊度值，所以最終的社團(tuán)劃分結(jié)果也是最佳結(jié)果。在最優(yōu)的非鄰域社團(tuán)結(jié)構(gòu)基礎(chǔ)上，遍歷網(wǎng)絡(luò)中的m條邊，分析網(wǎng)絡(luò)中的連邊信息。若當(dāng)前邊上的一對節(jié)點(diǎn)從屬于不同的社團(tuán)，則需要把其中的源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別作為重疊節(jié)點(diǎn)，統(tǒng)計(jì)對應(yīng)的社團(tuán)中新出現(xiàn)的邊，并計(jì)算網(wǎng)絡(luò)的劃分密度D，其中較大值對應(yīng)的節(jié)點(diǎn)即為重疊節(jié)點(diǎn)。將網(wǎng)絡(luò)信息以鄰接表的形式存儲，當(dāng)社團(tuán)中增加一個節(jié)點(diǎn)，判斷該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)是否也在當(dāng)前社團(tuán)中，此時整個過程的算法復(fù)雜度為O(k)(其中k為網(wǎng)絡(luò)的平均度)。假設(shè)在最壞的情況下，每條邊對應(yīng)的節(jié)點(diǎn)對都從屬于不同的社團(tuán)，則社團(tuán)重疊結(jié)構(gòu)挖掘過程的算法復(fù)雜度為O(mk)，在稀疏網(wǎng)絡(luò)中m≈n，此時算法的復(fù)雜度近似為O(nk)。綜上所述，本文提出的鄰域重疊社團(tuán)結(jié)構(gòu)挖掘算法的復(fù)雜度近似為O(n(log2n+k))，近似為線性，因此可以將它應(yīng)用到大規(guī)模網(wǎng)絡(luò)鄰域重疊社團(tuán)結(jié)構(gòu)挖掘。

圖2　模擬網(wǎng)絡(luò)驗(yàn)證鄰域重疊社團(tuán)結(jié)構(gòu)挖掘算法的有效性

4實(shí)驗(yàn)結(jié)果與分析

4.1利用模擬網(wǎng)絡(luò)驗(yàn)證算法

本文利用一個模擬網(wǎng)絡(luò)來驗(yàn)證算法的準(zhǔn)確性，在圖2中，一個模擬網(wǎng)絡(luò)中有兩個社團(tuán)，其中節(jié)點(diǎn)5和節(jié)點(diǎn)6是兩個社團(tuán)所共有的重疊節(jié)點(diǎn)。首先，我們對網(wǎng)絡(luò)進(jìn)行初始化，計(jì)算得到模塊度增量矩陣ΔQij和輔助向量αi以及最大堆H；然后利用堆的數(shù)據(jù)結(jié)構(gòu)計(jì)算和更新網(wǎng)絡(luò)的模塊度，快速地實(shí)現(xiàn)非鄰域社團(tuán)結(jié)構(gòu)劃分；最后遍歷網(wǎng)絡(luò)中的所有邊，基于劃分密度D挖掘出社團(tuán)之間的重疊節(jié)點(diǎn)，并將重疊節(jié)點(diǎn)與非鄰域社團(tuán)結(jié)構(gòu)相結(jié)合，得到鄰域重疊社團(tuán)結(jié)構(gòu)。從圖2中可以看到，鄰域重疊社團(tuán)挖掘算法準(zhǔn)確地將網(wǎng)絡(luò)劃分成兩個重疊的社團(tuán)，其中1表示該節(jié)點(diǎn)屬于社團(tuán)，0表示不屬于社團(tuán)。

4.2實(shí)證網(wǎng)絡(luò)驗(yàn)證算法

在本節(jié)，我們將本文所提出的鄰域重疊社團(tuán)結(jié)構(gòu)劃分算法應(yīng)用到已知社團(tuán)結(jié)構(gòu)的空手道俱樂部網(wǎng)和海豚網(wǎng)中，實(shí)現(xiàn)網(wǎng)絡(luò)中的鄰域社團(tuán)結(jié)構(gòu)挖掘，以驗(yàn)證鄰域社團(tuán)劃分算法的準(zhǔn)確性。

20世紀(jì)70年代，Zachary[16]基于美國一所大學(xué)中的空手道俱樂部成員間的相互社會關(guān)系，構(gòu)造了他們之間的關(guān)系網(wǎng)。在他研究過程中，該俱樂部的主管與校長之間因是否提高俱樂部收費(fèi)的問題產(chǎn)生了爭執(zhí)，導(dǎo)致俱樂部分裂成了兩個分別以主管和校長為核心的小俱樂部。因此空手道俱樂部網(wǎng)成為復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分方面的一個經(jīng)典網(wǎng)絡(luò)，被廣泛用于檢驗(yàn)社團(tuán)劃分算法的準(zhǔn)確度。圖3為利用本文所提出的鄰域重疊社團(tuán)結(jié)構(gòu)劃分算法對經(jīng)典的空手道俱樂部網(wǎng)絡(luò)進(jìn)行鄰域社團(tuán)劃分所得結(jié)果。

其中，橙色節(jié)點(diǎn)和淡粉色節(jié)點(diǎn)分別屬于不同的社團(tuán)，中間的紫色節(jié)點(diǎn)是兩個社團(tuán)之間的重疊節(jié)點(diǎn)?；谀K度Q，利用堆數(shù)據(jù)結(jié)構(gòu)合理地將空手道網(wǎng)絡(luò)劃分為彼此不重疊的兩部分，其社團(tuán)結(jié)構(gòu)與現(xiàn)實(shí)中的空手道俱樂部網(wǎng)絡(luò)幾乎一致。通過分析網(wǎng)絡(luò)中的連邊情況，利用劃分密度D，準(zhǔn)確地挖掘出網(wǎng)絡(luò)中的重疊節(jié)點(diǎn)，其中節(jié)點(diǎn)1,3,9,34不但與左邊社團(tuán)中多個節(jié)點(diǎn)相連，而且還與右邊多個節(jié)點(diǎn)之間有聯(lián)系，因此應(yīng)該是兩個社團(tuán)之間的共有部分。而節(jié)點(diǎn)31雖然只與左邊社團(tuán)中的一個節(jié)點(diǎn)相連，但是起到了橋梁作用，兩個社團(tuán)可以通過節(jié)點(diǎn)31進(jìn)行交流，所以節(jié)點(diǎn)31也應(yīng)該是兩個社團(tuán)之間的重疊節(jié)點(diǎn)。

圖3　空手道俱樂部重疊社團(tuán)劃分結(jié)果

圖4　海豚網(wǎng)重疊社團(tuán)劃分結(jié)果

Lusseau等[17]對生活在新西蘭神奇海灣中的一群海豚做了跟蹤調(diào)查，發(fā)現(xiàn)它們之間同樣存在著社團(tuán)結(jié)構(gòu)。圖4是利用本文所提出的鄰域重疊社團(tuán)結(jié)構(gòu)劃分算法對海豚網(wǎng)絡(luò)進(jìn)行鄰域社團(tuán)劃分所得結(jié)果。紅色節(jié)點(diǎn)和綠色節(jié)點(diǎn)分別屬于不同的社團(tuán)，中間的藍(lán)色節(jié)點(diǎn)是兩個社團(tuán)之間的重疊節(jié)點(diǎn)。節(jié)點(diǎn)2,29,31不但與左邊社團(tuán)中多個節(jié)點(diǎn)相連，而且還與右邊多個節(jié)點(diǎn)之間存在關(guān)系，因此也應(yīng)該是兩個社團(tuán)之間的共有部分。節(jié)點(diǎn)8,58雖然只與右邊社團(tuán)中的一個節(jié)點(diǎn)相連，但是這兩個節(jié)點(diǎn)同樣也起到了橋梁作用，使得左右兩個社團(tuán)可以通過節(jié)點(diǎn)8,58進(jìn)行交流，所以節(jié)點(diǎn)8,58也應(yīng)該是兩個社團(tuán)之間的重疊節(jié)點(diǎn)。

在空手道俱樂部網(wǎng)和海豚網(wǎng)中，利用本文提出的鄰域重疊社團(tuán)結(jié)構(gòu)劃分算法，得到的社團(tuán)結(jié)構(gòu)與實(shí)際情況相一致，進(jìn)一步證實(shí)了算法的準(zhǔn)確性。此外，本文還將鄰域重疊社團(tuán)結(jié)構(gòu)劃分算法運(yùn)用到科學(xué)家合作網(wǎng)中[8]。圖5是對科學(xué)家合作網(wǎng)進(jìn)行鄰域社團(tuán)劃分所得結(jié)果。

圖5　科學(xué)家合作網(wǎng)重疊社團(tuán)劃分結(jié)果

數(shù)據(jù)集名稱節(jié)點(diǎn)數(shù)邊數(shù)運(yùn)行時間/sSBMF9220.004Karateclub34780.006Dolphins621590.010Sciencenet158927420.388

在圖5中，科學(xué)家合作網(wǎng)中的最大連通網(wǎng)被劃分成8個社團(tuán)，不同顏色的團(tuán)簇代表了一個社團(tuán)結(jié)構(gòu)，社團(tuán)之間的紅色的節(jié)點(diǎn)表示的是重疊節(jié)點(diǎn)。從圖5可以看出，社團(tuán)內(nèi)部的節(jié)點(diǎn)之間聯(lián)系非常緊密，而社團(tuán)之間的連接卻相對比較稀疏。社團(tuán)間的重疊節(jié)點(diǎn)大多是度值比較大的節(jié)點(diǎn)或者是與度值較大的重疊節(jié)點(diǎn)關(guān)系緊密的小度值節(jié)點(diǎn)。圖5中的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)合理地反映了科學(xué)家之間的合作模式：相同研究方向的科學(xué)家之間的合作非常緊密，具有明顯的聚簇現(xiàn)象；同時不同研究方向的科學(xué)家之間也存在著學(xué)術(shù)交流，但這往往發(fā)生在學(xué)科代表的身上以及他的研究團(tuán)隊(duì)中。比如，在復(fù)雜網(wǎng)絡(luò)領(lǐng)域，Mark Newman是一名偉大的物理學(xué)教授，其團(tuán)隊(duì)主要從事網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)功能的研究。由于Newman團(tuán)隊(duì)取得的成績非常突出，導(dǎo)致很多領(lǐng)域的科學(xué)家都會與他的團(tuán)隊(duì)進(jìn)行合作，此時他的團(tuán)隊(duì)就成為不同研究領(lǐng)域的社團(tuán)之間的重疊節(jié)點(diǎn)。在圖5中，Newman及其團(tuán)隊(duì)對應(yīng)的是藍(lán)色社團(tuán)中的度值較大的紅色節(jié)點(diǎn)以及度值較小的紅色節(jié)點(diǎn)。

由于本文采用了堆數(shù)據(jù)結(jié)構(gòu)，從計(jì)算科學(xué)的角度優(yōu)化了社團(tuán)結(jié)構(gòu)的劃分，極大程度上降低了算法復(fù)雜度，加快了社團(tuán)結(jié)構(gòu)的劃分，表1是程序在不同的數(shù)據(jù)集中的運(yùn)行時間。

從表1可以看到，本文所提出的社團(tuán)劃分算法可以快速地實(shí)現(xiàn)鄰域社團(tuán)結(jié)構(gòu)劃分，當(dāng)網(wǎng)絡(luò)規(guī)模增大時，程序耗時仍然較低。因?yàn)楸疚乃岢龅纳鐖F(tuán)劃分算法的算法復(fù)雜度近似線性，所以其適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)，可以快速實(shí)現(xiàn)網(wǎng)絡(luò)的鄰域社團(tuán)結(jié)構(gòu)挖掘。

5結(jié)語

本文提出了一種復(fù)雜度近似線性的鄰域重疊社團(tuán)結(jié)構(gòu)劃分算法，可以準(zhǔn)確、快速地實(shí)現(xiàn)網(wǎng)絡(luò)社團(tuán)劃分以及重疊節(jié)點(diǎn)挖掘?；谀K度Q，本文采用堆的數(shù)據(jù)結(jié)構(gòu)，快速地實(shí)現(xiàn)了非鄰域社團(tuán)劃分，利用得到的非鄰域社團(tuán)構(gòu)造初始社團(tuán)矩陣，逐一分析網(wǎng)絡(luò)中的連邊，結(jié)合劃分密度D，準(zhǔn)確地實(shí)現(xiàn)了社團(tuán)間重疊節(jié)點(diǎn)的挖掘。最后，本文利用模擬網(wǎng)絡(luò)和經(jīng)典的實(shí)證網(wǎng)絡(luò)進(jìn)一步證實(shí)了算法的高效性、準(zhǔn)確性。

參考文獻(xiàn):

[1]Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.

[2]Adamic L A, Adar E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3): 211-230.

[3]Holme P, Huss M, Jeong H. Subnetwork hierarchies of biochemical pathways[J]. Bioinformatics, 2003, 19(4): 532-538.

[4]Newman M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256.

[5]Guimera R, Amaral L A N. Functional cartography of complex metabolic networks[J]. Nature, 2005, 433(7028): 895-900.

[6]Flake G W, Lawrence S, Giles C L, et al. Self-organization and identification of web communities[J]. Computer, 2002, 35(3): 66-70.

[7]Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal, 1970, 49(2): 291-307.

[8]Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113.

[9]Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6): 066111.

[10] Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3): 036104.

[11] Zhang X S, Li Z, Wang R S, et al. A combinatorial model and algorithm for globally searching community structure in complex networks[J]. Journal of Combinatorial Optimization, 2012, 23(4): 425-442.

[12] Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.

[13] 楊歡，韓定定. 完全子圖的鄰域重疊社團(tuán)結(jié)構(gòu)探測[J]. 現(xiàn)代電子技術(shù), 2012, 35(18):122-126.

Yang H, Han D D. Improvement of neighbourhood overlapping community detection algorithm based on complete subgraph[J]. Modern Electronics Technique, 2012, 35(18):122-126.

[14] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multiscale complexity in networks, 2010[J]. Nature, 466: 761.

[15] Zhang Z Y, Wang Y, Ahn Y Y. Overlapping community detection in complex networks using symmetric binary matrix factorization[J]. Physical Review E, 2013, 87(6): 062803.

[16] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977: 452-473.

[17] Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology, 2003, 54(4): 396-405.

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

Finding Overlapping Community in Network by Using Modularity and Partition Density

REN Chenglei, HAN Dingding, PU Peng, ZHANG Jiacheng

(School of Information Science and Technology, East China Normal University, Shanghai 200241, China)

Abstract：The algorithms of detecting community in complex networks now have lots of disadvantages such as high complexity and ignorance of accurate overlapping nodes. This paper proposes a highly efficient, rapid and accurate community detection algorithm. Based on greedy algorithm, the community is divided by establishing the modularity matrix and adopting the data structure. Considering the edges between local communities, the overlapping community structure is accurately dug by computing the partition density. We evaluate our methods using both synthetic benchmarks and real-world networks, demonstrating the effectiveness of our approach. Our method runs in essentially linear time.

Key words：community mining; overlapping community; modularity; partition density; time complexity

文章編號：16723813(2016)01010206;

DOI:10.13306/j.1672-3813.2016.01.011

收稿日期：2015-07-09

作者簡介：任成磊(1990-)，男，山東煙臺人，碩士研究生，主要研究方向?yàn)橹悄苡?jì)算、復(fù)雜網(wǎng)絡(luò)。

中圖分類號：TP393.02

文獻(xiàn)標(biāo)識碼：A