引言

許多實(shí)際網(wǎng)絡(luò)中都包含著一些群體，這些群體內(nèi)部的節(jié)點(diǎn)連接緊密，我們稱這些群體叫做團(tuán)簇、社團(tuán)或者模塊。社團(tuán)內(nèi)連接緊密，社團(tuán)外連接稀疏。對(duì)社團(tuán)結(jié)構(gòu)的探測(cè)是復(fù)雜網(wǎng)絡(luò)研究的重要課題之一。在過去的幾年中，出現(xiàn)了許多針對(duì)非鄰域重疊網(wǎng)絡(luò)的社團(tuán)探測(cè)算法。而在現(xiàn)實(shí)世界里，許多網(wǎng)絡(luò)的社團(tuán)之間存在鄰域重疊結(jié)構(gòu)。所謂鄰域，就是設(shè)A是拓?fù)淇臻g(X,T)的一個(gè)子集，點(diǎn)x∈A。如果存在集合U，滿足：

U是開集，即U∈T；

點(diǎn)x∈U；

U是A的子集。

則稱點(diǎn)x是A的一個(gè)內(nèi)點(diǎn)，并稱A是點(diǎn)x的一個(gè)鄰域。所謂重疊結(jié)構(gòu)，就是存在一些特殊的節(jié)點(diǎn)，它們不僅僅屬于一個(gè)社團(tuán)，可能是多個(gè)社團(tuán)共有的，我們稱這些特殊的節(jié)點(diǎn)叫做重疊節(jié)點(diǎn)。如在進(jìn)行科學(xué)家合作網(wǎng)中的生物網(wǎng)絡(luò)的蛋白質(zhì)網(wǎng)絡(luò)研究中，就發(fā)現(xiàn)有重疊節(jié)點(diǎn)的存在。

1鄰域重疊網(wǎng)絡(luò)

圖1所示是一個(gè)鄰域重疊網(wǎng)絡(luò)模型。其中黃色區(qū)域的社團(tuán)與藍(lán)色區(qū)域的社團(tuán)之間有一個(gè)重疊節(jié)點(diǎn)，黃色區(qū)域的社團(tuán)與綠色區(qū)域的社團(tuán)之間有三個(gè)重疊節(jié)點(diǎn)。

圖1鄰域重疊網(wǎng)絡(luò)模型

重疊節(jié)點(diǎn)在復(fù)雜網(wǎng)絡(luò)中扮演著特殊的角色，大部分社團(tuán)探測(cè)算法又無法探測(cè)它們。近年來，各種關(guān)于鄰域重疊的社

團(tuán)探測(cè)算法被廣泛使用。Baumes等人提出了兩個(gè)有效的算法，即用有效的啟發(fā)式RaRe算法和IS算法來尋找局部最優(yōu)簇。這些算法對(duì)研究隨機(jī)網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)都是有效的。

Lancichmetti等人提出了基于適應(yīng)函數(shù)優(yōu)化的算法來探測(cè)重疊社團(tuán)％FiedlerM.則提出了基于Laplacian矩陣特征向量的二分算法。KernighanB.W.等人提出Kernighan-Lin算法，通過優(yōu)化社團(tuán)內(nèi)部和之間的邊數(shù)來實(shí)現(xiàn)社團(tuán)的劃分。Newman提出了模塊度最大化的快速貪婪算法。這些算法都適用于比較復(fù)雜的大型網(wǎng)絡(luò)。但是，這些算法卻無法處理大型網(wǎng)絡(luò)中遍布眾多完全子圖(clique)的網(wǎng)絡(luò)結(jié)構(gòu)，如蛋白質(zhì)網(wǎng)絡(luò)中有眾多蛋白質(zhì)都是重疊節(jié)點(diǎn)。這些問題自從Palla等人提出clique過濾算法(CliquePercolationMethod，以下簡(jiǎn)稱CPM算法)后，問題才得以解決。

CPM算法以完全子圖為基礎(chǔ)。從某種意義上，通過CPM算法可以把網(wǎng)絡(luò)看作是許多小的完全子圖集合。采用從大到小、迭代回歸的算法來尋找完全子圖。因?yàn)樵贑PM算法中定義clique是相對(duì)嚴(yán)格的，網(wǎng)絡(luò)中往往存在不屬于clique的節(jié)點(diǎn)，所以不能完整地找到社團(tuán)結(jié)構(gòu)。為了能夠解決這一問題，學(xué)者又提出了使用k-means聚類、基于GN算法的COGNA算法，該算法不僅可以探測(cè)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，而且可以找到連接社團(tuán)的“橋節(jié)點(diǎn)”，但是，對(duì)于孤立節(jié)點(diǎn)的處理，則穩(wěn)定性不高。

本文提出了基于完全子圖的社團(tuán)探測(cè)算法。該算法在合并完全子圖團(tuán)簇時(shí)，計(jì)算每一對(duì)完全子圖的連接度重疊節(jié)點(diǎn)個(gè)數(shù)，并設(shè)置合并完全子圖的閾值，如果大于閾值，則合并。在處理不在團(tuán)簇內(nèi)的其他節(jié)點(diǎn)時(shí)，按照比例系數(shù)大小為劃分規(guī)則進(jìn)行劃分，同時(shí)計(jì)算其模塊度值，并驗(yàn)證鄰域重疊劃分算法的可行性。

2基于k-clique算法的重疊社團(tuán)結(jié)構(gòu)劃分算法的改進(jìn)

2.1模塊度

Newman和Girvan提出了用模塊度值來衡量社團(tuán)劃分質(zhì)量的方案:

Q=/(es-a2(1)

=1

其中，e”表示所有社團(tuán)，中的邊權(quán)總和;表示社團(tuán)i與其它社團(tuán)的連邊權(quán)度之和。如果是無權(quán)網(wǎng)絡(luò)，則邊權(quán)為1。盡管這種測(cè)量方法在社會(huì)網(wǎng)絡(luò)中得到了廣泛應(yīng)用，但其仍然面臨著一些問題。Q函數(shù)傾向于找到粗糙的而不是精細(xì)的網(wǎng)絡(luò)簇結(jié)構(gòu)，因而無法應(yīng)用于鄰域重疊網(wǎng)絡(luò)社團(tuán)質(zhì)量的探測(cè)［22］。因此，ShenH.W.等人又提出了擴(kuò)展的度量方法,具體如下：

Q。=2m//dcudcv(Auv-緊)°)

c!Puv其中，4表示節(jié)點(diǎn)u和節(jié)點(diǎn)v之間的權(quán)度；表示節(jié)點(diǎn)u與相鄰節(jié)點(diǎn)之間的權(quán)度之和；表示整個(gè)網(wǎng)絡(luò)的權(quán)度之和用來判斷節(jié)點(diǎn)u是否在社團(tuán)C之中，如果節(jié)點(diǎn)u在社團(tuán)C內(nèi)部，則毎=1,否則毎=0；表示所劃分的所有社團(tuán)。

在非鄰域重疊網(wǎng)絡(luò)中，一個(gè)節(jié)點(diǎn)僅屬于一個(gè)社團(tuán)。然而，在鄰域重疊網(wǎng)絡(luò)中，一個(gè)節(jié)點(diǎn)可能屬于多個(gè)社團(tuán)。因此，應(yīng)該將毎替換為??，表示重疊節(jié)點(diǎn)u所屬社團(tuán)的個(gè)數(shù)。重新定義模塊度如下：

TOC \o "1-5" \h \z

6c!P

2.2算法的流程與改進(jìn)

在網(wǎng)絡(luò)中，i 代表一個(gè)節(jié)點(diǎn)，mi 代表節(jié)點(diǎn) i 所屬的社團(tuán)個(gè)數(shù)。社團(tuán) α 和社團(tuán) β 共有 Sα,β 個(gè)節(jié)點(diǎn)，可以定義 Sα,β 為社團(tuán)的重疊大小。社團(tuán) α 的連邊數(shù)量可以稱為社團(tuán)度，用 da com 來表示。社團(tuán) α 內(nèi)部的節(jié)點(diǎn)個(gè)數(shù)定義為社團(tuán) α 的大小，用Sa com來表示。本文對(duì)社團(tuán)結(jié)構(gòu)的定義以完全子圖為網(wǎng)絡(luò)核心，所劃分出來的團(tuán)簇是由許多 k-cliques 所組成的集合。

本文的算法由三部分組成：第一是尋找網(wǎng)絡(luò)中所有的最大完全子圖；第二是將完全子圖合并成為更大的團(tuán)簇；第三是處理不在團(tuán)簇里面的剩余節(jié)點(diǎn)，實(shí)現(xiàn)社團(tuán)結(jié)構(gòu)的劃分。其算法流程圖如圖2所示。

圖2社團(tuán)探測(cè)算法流程圖

第一步：尋找網(wǎng)絡(luò)中所有的最大完全子圖。具體操作時(shí)可以把k-clique作為網(wǎng)絡(luò)核心，將兩兩節(jié)點(diǎn)之間的相關(guān)系數(shù)矩陣設(shè)置閾值轉(zhuǎn)化為0-1矩陣，然后輸入0-1矩陣，這樣就可以輸出最大完全子圖序列，其流程圖如圖3所示。

圖3k-clique算法流程圖

具體實(shí)現(xiàn)時(shí),首先給出一個(gè)節(jié)點(diǎn)為i的圖G,中有社團(tuán)C如果社團(tuán)C沒有連接節(jié)點(diǎn)，則輸出C。反之，則社團(tuán)C并聯(lián)連接節(jié)點(diǎn)V,記做{C}U{V)。把{C}U{V}的鄰接節(jié)點(diǎn)的數(shù)目記為t({C}U{V})；然后，再給一個(gè)節(jié)點(diǎn)為j的簡(jiǎn)單圖G,社團(tuán)c最大時(shí)為max(C)?如果max(C)沒有鄰居節(jié)點(diǎn)，則輸出max(C)o若max(C)與連接節(jié)點(diǎn)V不是一個(gè)團(tuán)，則刪除C與V之間的連接。

第二步：主要是合并完全子圖。在找到網(wǎng)絡(luò)中所有最大完全子圖之后，將連接緊密的完全子圖合并為更大的團(tuán)簇。傳統(tǒng)的合并方法是在完全子圖之間沒有重疊節(jié)點(diǎn)的情況下，計(jì)算完全子圖之間的連接度，即完全子圖之間的連接邊數(shù)。設(shè)置用來判斷團(tuán)簇間連接是否緊密的閾值，如果連接度大于設(shè)定閾值，則合并。圖4所示是兩種雙10-cliques連接情況的比較。其中圖4(a)是沒有重疊節(jié)點(diǎn)的雙10-cliques。而本文的研究對(duì)象是具有高連接性的網(wǎng)絡(luò)，在尋找出完全子圖之后發(fā)現(xiàn)，大多數(shù)完全子圖之間具有如圖4(b)所示的重疊節(jié)點(diǎn)，僅僅考慮連接度是不可行的，所以，本文對(duì)其進(jìn)行了改進(jìn)。具體步驟是:首先計(jì)算每一對(duì)clique的連接度，用C表示；然后設(shè)置合并完全子圖的閾值如果CmNCC,則將這對(duì)完全子圖合并,然后重復(fù)上面的工作，直到C<CC。

第三步：處理不在團(tuán)簇里面的剩余節(jié)點(diǎn)。將孤立節(jié)點(diǎn)劃分在團(tuán)簇中，并實(shí)現(xiàn)社團(tuán)結(jié)構(gòu)的劃分。本文提出用連接度(Cg)的規(guī)則來劃分。如果一個(gè)節(jié)點(diǎn)與多個(gè)團(tuán)簇相連，則定義一個(gè)節(jié)點(diǎn)與團(tuán)簇的邊數(shù)為C(u,c),其中，"代表節(jié)點(diǎn)，c代表團(tuán)簇。團(tuán)簇的大小，也就是團(tuán)簇中節(jié)點(diǎn)的個(gè)數(shù)為S，則可定義劃分閾值為C(u,c)/S。這個(gè)閾值叫做連接度，用CG(ConnectingDegree)來表示。

(a)沒有重疊節(jié)點(diǎn)的雙10-cliques(b)高重疊性雙10-cliques

圖4兩種雙10-cliques連接情況比較

圖5所示是處理不在團(tuán)簇里面的剩余節(jié)點(diǎn)的示意圖。圖中,節(jié)點(diǎn)11是不在團(tuán)簇里面的剩余節(jié)點(diǎn)。粉色圓圈節(jié)點(diǎn)和黃色三角形節(jié)點(diǎn)分別表示不同的團(tuán)簇。按照連接度大小(CN)來劃分,節(jié)點(diǎn)11與粉色圓圈節(jié)點(diǎn)的團(tuán)簇的連接度CN=2/7,其中2表示節(jié)點(diǎn)11與粉色圓圈節(jié)點(diǎn)的團(tuán)簇的邊數(shù)為2,7表示粉色圓圈節(jié)點(diǎn)的團(tuán)簇的大小，即節(jié)點(diǎn)個(gè)數(shù)為7用同樣的方法可計(jì)算節(jié)點(diǎn)11與黃色三角形節(jié)點(diǎn)的團(tuán)簇的連接度SF=1/3。顯然1/3>2/7,那么節(jié)點(diǎn)11與粉色圓圈團(tuán)簇的連接性就比黃色三角形團(tuán)簇要強(qiáng)，所以將節(jié)點(diǎn)11劃分在了黃色三角形節(jié)點(diǎn)的團(tuán)簇當(dāng)中。

圖5不在團(tuán)簇里面的剩余節(jié)點(diǎn)處理示意圖

3空手道網(wǎng)絡(luò)和科學(xué)家合作網(wǎng)的劃分

將本文的算法應(yīng)用到空手道網(wǎng)絡(luò)當(dāng)中的重疊社團(tuán)結(jié)構(gòu)劃分示意圖如圖6所示。其中，粉色圓圈節(jié)點(diǎn)和綠色三角符號(hào)節(jié)點(diǎn)分別代表兩個(gè)不同的社團(tuán)，藍(lán)色正方形節(jié)點(diǎn)代表兩個(gè)社團(tuán)的重疊節(jié)點(diǎn)。這個(gè)美國(guó)大學(xué)空手道網(wǎng)絡(luò)當(dāng)中包含34個(gè)節(jié)點(diǎn)、78條邊。由于俱樂部主管和指導(dǎo)員發(fā)生了矛盾，所以俱樂部分裂為分別以主管和指導(dǎo)員為核心的兩個(gè)團(tuán)體。

設(shè)置閾值CC為0.5,實(shí)現(xiàn)鄰域重疊社團(tuán)劃分。粉色圓形節(jié)點(diǎn)分別是1,2,3,4,5,6,7,8,11,12,13,14,17,18,20,22；綠色三角形節(jié)點(diǎn)分別是9,15,16,19,21,23,24,25,26,27,28,29,30,31,32,33,34；藍(lán)色正方形為兩社團(tuán)之間的重疊節(jié)點(diǎn)10。計(jì)算其模塊度值為0.3881。

若將算法應(yīng)用到科學(xué)家合作網(wǎng)當(dāng)中，圖7所示是劃分科學(xué)家合作網(wǎng)當(dāng)中由393個(gè)節(jié)點(diǎn)組成的網(wǎng)絡(luò)拓?fù)鋱D，其中不同顏色圓圈節(jié)點(diǎn)代表不同的社團(tuán)劃分。按照該算法可劃分出27個(gè)社團(tuán)結(jié)構(gòu)，有72個(gè)重疊節(jié)點(diǎn)，模塊度值為0.8217,算法復(fù)雜度為0(1)。圖7中展示了科學(xué)家合作網(wǎng)社團(tuán)的劃分情況。

圖6空手道網(wǎng)絡(luò)鄰域重疊社團(tuán)結(jié)構(gòu)劃分

圖7科學(xué)家合作網(wǎng)鄰域重疊社團(tuán)結(jié)構(gòu)劃分示意圖

圖8所示是大小為8的社團(tuán)和節(jié)點(diǎn)數(shù)為4的社團(tuán)代表科學(xué)家的連接情況。從圖8中可以看出，科學(xué)家VicsekT.是重疊節(jié)點(diǎn)。又因?yàn)樗沁@個(gè)團(tuán)簇中連邊最多的，其聚類系數(shù)也最大，因而起到了"橋梁"的作用。BrandesU.,CarlsonJ.和VespignaniA.:AlbaR.,MooreC.和TurskiP.分別組成了3-cliques關(guān)系。

本文對(duì)基于完全子圖的社團(tuán)探測(cè)算法進(jìn)行改進(jìn)。在合并完全子圖團(tuán)簇時(shí)，計(jì)算每一對(duì)完全子圖的連接度重疊節(jié)點(diǎn)個(gè)數(shù),設(shè)置合并完全子圖的閾值，如果大于閾值，則合并。在處理不在團(tuán)簇內(nèi)的其他節(jié)點(diǎn)時(shí)，提出用比例系數(shù)大小來劃分。本文同時(shí)將改進(jìn)算法應(yīng)用在空手道俱樂部網(wǎng)絡(luò)和科學(xué)家合作網(wǎng)當(dāng)中，從而驗(yàn)證了改進(jìn)算法的可行性。

20210915_61417bc2641b6__完全子圖的鄰域重疊社團(tuán)結(jié)構(gòu)探測(cè)