引言

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

U是開集，即U∈T；

點x∈U；

U是A的子集。

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

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

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

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

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

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

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

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

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

2基于k-clique算法的重疊社團結構劃分算法的改進

2.1模塊度

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

Q=/(es-a2(1)

=1

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

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

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

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

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

6c!P

2.2算法的流程與改進

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

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

圖2社團探測算法流程圖

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

圖3k-clique算法流程圖

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

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

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

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

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

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

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

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

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

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

若將算法應用到科學家合作網(wǎng)當中，圖7所示是劃分科學家合作網(wǎng)當中由393個節(jié)點組成的網(wǎng)絡拓撲圖，其中不同顏色圓圈節(jié)點代表不同的社團劃分。按照該算法可劃分出27個社團結構，有72個重疊節(jié)點，模塊度值為0.8217,算法復雜度為0(1)。圖7中展示了科學家合作網(wǎng)社團的劃分情況。

圖6空手道網(wǎng)絡鄰域重疊社團結構劃分

圖7科學家合作網(wǎng)鄰域重疊社團結構劃分示意圖

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

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

20210915_61417bc2641b6__完全子圖的鄰域重疊社團結構探測