基于最大團(tuán)的層次化重疊社區(qū)發(fā)現(xiàn)算法

孫成成，席景科，占文威，李 懂

中國礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116

1 引言

早期很多傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法在挖掘社區(qū)結(jié)構(gòu)時(shí)都是基于網(wǎng)絡(luò)中節(jié)點(diǎn)的唯一性的，即每個(gè)節(jié)點(diǎn)都從屬于某一個(gè)社區(qū)。然而，近些年研究發(fā)現(xiàn)，大量真實(shí)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)并非如此涇渭分明，很多社區(qū)在某些方面彼此具有較為緊密的聯(lián)系，社區(qū)之間存在交叉重疊現(xiàn)象，因此，社區(qū)結(jié)構(gòu)通常具有重疊性和層次性。

現(xiàn)有的能夠檢測重疊結(jié)構(gòu)的社區(qū)發(fā)現(xiàn)算法主要包括基于派系過濾的算法[1]、基于連邊劃分的算法[2]和基于局部挖掘的算法[3]，這三類算法分別以團(tuán)（最大完全子圖）、邊以及節(jié)點(diǎn)為研究對象來挖掘社區(qū)結(jié)構(gòu)。以邊為研究對象難以挖掘網(wǎng)絡(luò)的層次結(jié)構(gòu)，因此不予考慮。以節(jié)點(diǎn)為對象不斷向外擴(kuò)展最后形成層次樹圖是層次聚類算法中最為常見的做法[4-6]，這種做法最大的弊端是穩(wěn)定性問題，主要體現(xiàn)在初始節(jié)點(diǎn)的選擇上，少數(shù)情況下，初始節(jié)點(diǎn)不同會導(dǎo)致算法最終結(jié)果不同，大多數(shù)情況下算法的結(jié)果不依賴于初始節(jié)點(diǎn)，但算法的復(fù)雜度會隨其變化，另外，在具有重疊結(jié)構(gòu)的網(wǎng)絡(luò)中，若一開始就選擇了重疊節(jié)點(diǎn)，那么對最終結(jié)果的影響就比較大了。因此，可以結(jié)合派系過濾算法的思想，將最大團(tuán)（也稱為派系、極大團(tuán)、最大團(tuán)等，本文統(tǒng)稱為最大團(tuán)）作為擴(kuò)展對象，由于最大團(tuán)本身內(nèi)部結(jié)構(gòu)非常緊密（任意兩個(gè)節(jié)點(diǎn)間均有邊相連），因此由最大團(tuán)組成的社區(qū)也具有較高的內(nèi)聚性，社區(qū)結(jié)構(gòu)的質(zhì)量有一定程度的保證。另外，每個(gè)最大團(tuán)雖然各不相同，但同一個(gè)節(jié)點(diǎn)卻可以出現(xiàn)在多個(gè)最大團(tuán)中，這樣就能檢測出網(wǎng)絡(luò)中的重疊節(jié)點(diǎn)?；谝陨戏治?，本文提出一種基于最大團(tuán)的層次化重疊社區(qū)發(fā)現(xiàn)算法（Hierarchical Overlapping Community Detection Algorithm Based on Maximum Clique），簡稱HOMA算法，該算法首先找出網(wǎng)絡(luò)中的最大團(tuán)，然后對最大團(tuán)進(jìn)行擴(kuò)展，不斷合并最大團(tuán)直到網(wǎng)絡(luò)中只剩下一個(gè)社區(qū)，這個(gè)過程形成了一個(gè)層次樹圖，通過選擇合適的方法對該樹狀圖進(jìn)行剪枝，就能得到社區(qū)劃分結(jié)果。

2 基于最大團(tuán)的層次化重疊社區(qū)發(fā)現(xiàn)算法

2.1 最大團(tuán)問題求解

最大團(tuán)問題（Maximum Clique Problem，MCP）是圖論中一個(gè)傳統(tǒng)的組合優(yōu)化問題，同時(shí)也是一個(gè)NP完全問題[7]，不過由于求解最大團(tuán)問題算法的不斷改進(jìn)再加上真實(shí)網(wǎng)絡(luò)的稀疏性，這種NP完全問題基本得以解決。經(jīng)典的最大團(tuán)挖掘算法如Bron_Kerbosch算法[8]，首先選擇一個(gè)初始節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)，并將其加入集合R，再從舊的P和X集合中刪掉與該擴(kuò)展節(jié)點(diǎn)相連的節(jié)點(diǎn)，這樣就產(chǎn)生了新的P和X集合，舊的P和X集合依舊保留，接下來對新集合中的節(jié)點(diǎn)遞歸執(zhí)行上述操作，算法返回后將擴(kuò)展節(jié)點(diǎn)從舊的P集合中移除，并加入X集合。Bron_Kerbosch算法效率不高，因?yàn)檫f歸搜索了所有情況，其中有些不是最大團(tuán)的也進(jìn)行了搜索，后續(xù)出現(xiàn)了很多對于該算法的改進(jìn)[9-10]。文獻(xiàn)[9]針對此問題提出了關(guān)鍵點(diǎn)選取策略，通過縮小擴(kuò)展節(jié)點(diǎn)的范圍來提高效率。因此，在本文中采用改進(jìn)的Bron_Kerbosch算法來挖掘網(wǎng)絡(luò)中的最大團(tuán)，不過在細(xì)微處作些調(diào)整，首先是過濾掉節(jié)點(diǎn)數(shù)較少的最大團(tuán)，通過設(shè)置一個(gè)參數(shù)k來控制最大團(tuán)的最少節(jié)點(diǎn)個(gè)數(shù)。一般而言，一個(gè)最大團(tuán)包含的節(jié)點(diǎn)個(gè)數(shù)應(yīng)不少于3個(gè)，這是因?yàn)楣?jié)點(diǎn)數(shù)較少的最大團(tuán)容易成為冗余的團(tuán)，這種團(tuán)的每個(gè)節(jié)點(diǎn)都來源于其他最大團(tuán)，將這種團(tuán)考慮在內(nèi)就意味著進(jìn)行了多余的擴(kuò)展操作。此外，算法挖掘到的最大團(tuán)很可能沒有涵蓋網(wǎng)絡(luò)中所有的節(jié)點(diǎn)，對于這些節(jié)點(diǎn)不能排除在外，可以將其視為節(jié)點(diǎn)數(shù)為1的特殊的團(tuán)。

2.2 社區(qū)的擴(kuò)展合并

HOMA算法的第二部分就是對最大團(tuán)或單個(gè)節(jié)點(diǎn)構(gòu)成的社區(qū)進(jìn)行合并擴(kuò)展形成層次樹圖，這一部分是整個(gè)算法最關(guān)鍵的地方，如何迭代合并社區(qū)直接關(guān)系到算法的最終結(jié)果，首先介紹幾個(gè)與擴(kuò)展過程相關(guān)的定義。

定義1（重疊節(jié)點(diǎn)集合）兩個(gè)社區(qū)間相同節(jié)點(diǎn)構(gòu)成的重疊節(jié)點(diǎn)集合可表示為：

其中，Ci表示社區(qū)i，V(Ci)表示社區(qū)i所包含的節(jié)點(diǎn)集合。

定義2（共同鄰居節(jié)點(diǎn)集合）兩個(gè)社區(qū)間的共同鄰居節(jié)點(diǎn)集合可表示為：

其中，N(Ci)表示與社區(qū)i內(nèi)部節(jié)點(diǎn)相連但不屬于該社區(qū)的節(jié)點(diǎn)集合。

定義3（社區(qū)間橋接邊）兩個(gè)社區(qū)間的橋接邊是指兩個(gè)端點(diǎn)分別在不同社區(qū)內(nèi)所構(gòu)成的邊，可表示為：

在2.1節(jié)通過調(diào)用改進(jìn)的Bron_Kerbosch算法得到最大團(tuán)集并初始化為社區(qū)后，現(xiàn)在要將其進(jìn)行合并擴(kuò)展。首先，要解決穩(wěn)定性問題，即不能隨機(jī)選擇一個(gè)社區(qū)為擴(kuò)展起點(diǎn)，而應(yīng)該根據(jù)某種標(biāo)準(zhǔn)進(jìn)行選擇，這種標(biāo)準(zhǔn)也可稱為合并兩個(gè)社區(qū)的原則，在合并兩個(gè)節(jié)點(diǎn)時(shí)可以依據(jù)節(jié)點(diǎn)相似度，那么這里可以依據(jù)社區(qū)相似度，只是節(jié)點(diǎn)相似度已經(jīng)有很多經(jīng)典算法對其進(jìn)行研究，而社區(qū)相似度則并無一個(gè)較為權(quán)威的定義，也沒有固定的計(jì)算公式，為了便于區(qū)分節(jié)點(diǎn)相似度，本文將社區(qū)間的相似度稱為社區(qū)的耦合強(qiáng)度。

社區(qū)的耦合強(qiáng)度反映了兩個(gè)社區(qū)間的關(guān)聯(lián)程度，關(guān)于節(jié)點(diǎn)相似度已有很多算法進(jìn)行研究[11-12]，社區(qū)間的關(guān)聯(lián)程度并沒有一個(gè)權(quán)威的定義，兩個(gè)社區(qū)間聯(lián)系越緊密，則耦合強(qiáng)度越大，而兩個(gè)社區(qū)間的關(guān)聯(lián)程度又取決于重疊節(jié)點(diǎn)、共同鄰居節(jié)點(diǎn)和社區(qū)間橋接邊等因素，分析如下：

（1）重疊節(jié)點(diǎn)，兩個(gè)社區(qū)間的重疊節(jié)點(diǎn)越多，其耦合強(qiáng)度越大，當(dāng)小于臨界值時(shí)，這兩個(gè)社區(qū)即為同一個(gè)社區(qū)。此外，如果一個(gè)社區(qū)包含相對較少的節(jié)點(diǎn)，而另一個(gè)社區(qū)擁有更多的節(jié)點(diǎn)，那么可認(rèn)為節(jié)點(diǎn)少的社區(qū)是另一個(gè)社區(qū)的子社區(qū)，則可將兩個(gè)社區(qū)進(jìn)行合并。

（2）共同鄰居節(jié)點(diǎn)，共同鄰居是影響節(jié)點(diǎn)相似度大小的因素之一，而社區(qū)是由節(jié)點(diǎn)組成的，那么共同鄰居也是社區(qū)耦合強(qiáng)度的影響因素之一，共同鄰居越多，則社區(qū)耦合強(qiáng)度越大。

（3）社區(qū)間橋接邊，社區(qū)間的橋接邊反映了社區(qū)間連接的緊密程度，因此，兩個(gè)社區(qū)間的橋接邊越多，那么社區(qū)的耦合強(qiáng)度越大。

基于以上分析，綜合考慮兩個(gè)社區(qū)間的重疊節(jié)點(diǎn)、共同鄰居節(jié)點(diǎn)和橋接邊這三種因素，定義社區(qū)耦合強(qiáng)度如下所示：

其中，CS是耦合強(qiáng)度，α是調(diào)節(jié)系數(shù)，其值在0至1之間，V(Ci)是社區(qū)i的節(jié)點(diǎn)集合，則表示社區(qū)i和 j共同擁有的節(jié)點(diǎn)即重疊節(jié)點(diǎn)占其中較小社區(qū)的節(jié)點(diǎn)個(gè)數(shù)的比例。N(Ci)表示社區(qū)i的鄰居節(jié)點(diǎn)集合，表示社區(qū)i和 j社區(qū)的共同鄰居節(jié)點(diǎn)個(gè)數(shù)占所有鄰居節(jié)點(diǎn)個(gè)數(shù)的比例。E(Ci,Cj)表示社區(qū)i和 j之間的橋接邊的集合，sum(Ei,Ej)表示社區(qū)i和社區(qū) j的邊數(shù)和。

α是介于0和1之間的調(diào)節(jié)參數(shù)，作用是為了應(yīng)對不同的情況，社區(qū)中除了存在最大團(tuán)還有許多單個(gè)節(jié)點(diǎn)。當(dāng)計(jì)算單個(gè)節(jié)點(diǎn)社區(qū)與其他社區(qū)的耦合強(qiáng)度時(shí)，只需考慮該節(jié)點(diǎn)與其他社區(qū)之間連邊的數(shù)量，那么這時(shí)候通過設(shè)置α的值可以只計(jì)算橋接邊的比例或共同鄰居比例。

定義了社區(qū)耦合強(qiáng)度后，需要計(jì)算所有社區(qū)間的耦合強(qiáng)度，構(gòu)造耦合強(qiáng)度鄰接矩陣，然后從中選擇最大值對應(yīng)的兩個(gè)社區(qū)進(jìn)行合并，生成一個(gè)新的社區(qū)，再將兩個(gè)舊社區(qū)從社區(qū)集合中刪除并計(jì)算新社區(qū)與其他社區(qū)間的耦合強(qiáng)度，之后更新耦合強(qiáng)度矩陣，然后再次選擇最大值對應(yīng)的兩個(gè)社區(qū)進(jìn)行合并，重復(fù)上述操作，由于每次總能找到耦合強(qiáng)度的最大值，因此合并操作能夠一直繼續(xù)下去直到網(wǎng)絡(luò)中只剩下一個(gè)社區(qū)為止。在這個(gè)過程中，通過記錄每次合并社區(qū)的序號可構(gòu)造一個(gè)層次結(jié)構(gòu)樹狀圖，樹狀圖的每一層都代表算法得到的一種結(jié)果，選擇哪一層作為算法結(jié)果取決于采用的社區(qū)結(jié)構(gòu)質(zhì)量評價(jià)函數(shù)，這里將其稱為剪枝函數(shù)。模塊度最大化問題是一個(gè)經(jīng)典的最優(yōu)化問題，其最大值對應(yīng)的社區(qū)劃分即為近似的最優(yōu)社區(qū)劃分，本文中依然采用模塊度函數(shù)，由于涉及到重疊結(jié)構(gòu)，因此采用文獻(xiàn)[13]提出的適用于重疊社區(qū)結(jié)構(gòu)的模塊度函數(shù)，其定義如下：

其中，Ov表示節(jié)點(diǎn)v所從屬的社區(qū)個(gè)數(shù)；Avw表示節(jié)點(diǎn)v和w間是否有邊相連，值為1說明有邊相連，反之則無；kv表示節(jié)點(diǎn)i的度；Ci表示i所屬的社區(qū)；m為網(wǎng)絡(luò)中的總邊數(shù)。模塊度表示社區(qū)劃分的精確程度，基于模塊度最優(yōu)思想，模塊度值越接近1，劃分的社區(qū)結(jié)構(gòu)越好。當(dāng)模塊度值達(dá)到最大時(shí)，說明此時(shí)的社區(qū)劃分結(jié)構(gòu)近似最佳[13-15]。需要注意的是，盡管是最后進(jìn)行剪枝操作，但模塊度的計(jì)算不應(yīng)放在最后，而是在每次合并社區(qū)導(dǎo)致社區(qū)結(jié)構(gòu)發(fā)生變化時(shí)更新模塊度，這樣在生成層次樹圖的同時(shí)，每一層對應(yīng)的模塊度也都計(jì)算完畢，這時(shí)只需要選擇模塊度最大的一層作為算法的最終結(jié)果，算法終止。

2.3 基于最大團(tuán)的層次化重疊社區(qū)發(fā)現(xiàn)算法

HOMA算法能夠同時(shí)檢測網(wǎng)絡(luò)中的層次結(jié)構(gòu)和重疊結(jié)構(gòu)，其主要包括提取最大團(tuán)、擴(kuò)展社區(qū)生成樹狀圖以及對樹狀圖進(jìn)行剪枝這三個(gè)步驟：

（1）采用改進(jìn)的Bron_Kerbosch算法提取網(wǎng)絡(luò)中所有的最大團(tuán)，由于節(jié)點(diǎn)個(gè)數(shù)小于3的最大團(tuán)較多且容易成為附屬最大團(tuán)（團(tuán)中的節(jié)點(diǎn)都來源于其他團(tuán)），因此可設(shè)置一個(gè)參數(shù)k來控制最大團(tuán)的最少節(jié)點(diǎn)個(gè)數(shù)，即提高了正確度同時(shí)降低了計(jì)算量。然后將所有的最大團(tuán)以及未出現(xiàn)在任何團(tuán)中的單個(gè)節(jié)點(diǎn)初始化為獨(dú)立的社區(qū)。

（2）計(jì)算網(wǎng)絡(luò)中任意兩個(gè)社區(qū)間的耦合強(qiáng)度，構(gòu)造耦合強(qiáng)度矩陣，然后矩陣中最大值對應(yīng)的兩個(gè)社區(qū)進(jìn)行合并，得到新的社區(qū)，再計(jì)算新社區(qū)和其他社區(qū)間的耦合強(qiáng)度，更新耦合強(qiáng)度矩陣。這樣每次總是合并矩陣中耦合強(qiáng)度最大的兩個(gè)社區(qū)，然后更新矩陣，直到最后只剩下一個(gè)社區(qū)，在這個(gè)過程中就生成了一個(gè)層次樹圖。

（3）利用重疊模塊度函數(shù)對樹狀圖進(jìn)行剪枝，選擇模塊度最大的一層作為社區(qū)劃分結(jié)果。

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

通過展示HOMA算法在不同網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果來驗(yàn)證HOMA算法發(fā)現(xiàn)層次結(jié)構(gòu)和重疊結(jié)構(gòu)社區(qū)的準(zhǔn)確度，實(shí)驗(yàn)網(wǎng)絡(luò)包括真實(shí)網(wǎng)絡(luò)和LFR人工基準(zhǔn)網(wǎng)絡(luò)。實(shí)驗(yàn)中采用NMI（Normalised Mutual Information）[16]作為社區(qū)結(jié)構(gòu)質(zhì)量優(yōu)劣的參考標(biāo)準(zhǔn)。NMI的值介于0和1之間，值越大說明兩個(gè)社區(qū)劃分的結(jié)果越相似，值為1時(shí)則兩個(gè)社區(qū)劃分結(jié)果完全相同。實(shí)驗(yàn)環(huán)境為：四核1.4 GHz處理器；內(nèi)存4 GB；操作系統(tǒng)為Windows 7；使用MATLAB及Java編程。

3.1 空手道俱樂部網(wǎng)絡(luò)

空手道俱樂部網(wǎng)絡(luò)又稱Zachary’s Karate網(wǎng)絡(luò)，該網(wǎng)絡(luò)是從現(xiàn)實(shí)世界的一個(gè)空手道俱樂部抽象化得到的。該俱樂部由34個(gè)成員組成，將成員之間的聯(lián)系抽象為邊，則一共有78條邊。

HOMA算法的第一步是提取網(wǎng)絡(luò)中的最大團(tuán)，將k值設(shè)置為3，即只提取節(jié)點(diǎn)數(shù)不少于3的最大團(tuán)，這一階段一共生成了25個(gè)最大團(tuán)，然后將沒有被最大團(tuán)集合涵蓋在內(nèi)的兩個(gè)節(jié)點(diǎn)即10號節(jié)點(diǎn)和12號節(jié)點(diǎn)初始化為社區(qū)，則一共有27個(gè)社區(qū)，所有社區(qū)節(jié)點(diǎn)的分布情況如表1所示。

表1 HOMA算法在Zachary’s Karate網(wǎng)絡(luò)提取的最大團(tuán)集合

算法的第二階段是利用公式（4）計(jì)算這27個(gè)社區(qū)間的社區(qū)耦合強(qiáng)度，構(gòu)造耦合強(qiáng)度矩陣，然后選擇最大值對應(yīng)的兩個(gè)社區(qū)進(jìn)行合并，接下來更新耦合強(qiáng)度矩陣并重復(fù)上述步驟直到最終只剩下一個(gè)社區(qū)，這個(gè)過程生成了層次樹圖，如圖1所示。

圖1 HOMA算法在空手道俱樂部網(wǎng)絡(luò)上生成的層次樹狀圖

由圖1可以看出，初始的27個(gè)社區(qū)一共進(jìn)行了26次合并操作，在最后一次的合并操作后，整個(gè)網(wǎng)絡(luò)中只剩下一個(gè)社區(qū)，這個(gè)社區(qū)包含了最開始的27個(gè)社區(qū)。在每次合并后，更新一次整個(gè)網(wǎng)絡(luò)的重疊模塊度EQ，結(jié)果如圖2所示。圖2中，在第25次合并時(shí)，模塊度值達(dá)到最大值，即此時(shí)社區(qū)結(jié)構(gòu)劃分最為理想，因此將這一層作為該網(wǎng)絡(luò)的近似最優(yōu)劃分結(jié)果。此時(shí)劃分，則一共得到2個(gè)社區(qū)，這與Zachary’s Karate網(wǎng)絡(luò)原本的社區(qū)數(shù)量吻合。進(jìn)一步分析發(fā)現(xiàn)，節(jié)點(diǎn)3和9均出現(xiàn)在兩個(gè)社區(qū)內(nèi)，因此這兩個(gè)節(jié)點(diǎn)為重疊節(jié)點(diǎn)。

為了能夠更直觀地分析HOMA算法發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)的質(zhì)量，將其與LFM算法以及CPM算法在Zachary’s Karate網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果進(jìn)行比較，結(jié)果如表2所示。CPM算法用K-clique（大小為K的完全子圖）來表示社區(qū)，通過某種策略來合并相鄰K-clique，那些屬于多個(gè)K-clique的節(jié)點(diǎn)即為重疊節(jié)點(diǎn)[1，17]。Lancichinetti等人于2008年提出了可以同時(shí)檢測網(wǎng)絡(luò)重疊結(jié)構(gòu)和層次結(jié)構(gòu)的LFM算法，算法是一個(gè)將隨機(jī)種子節(jié)點(diǎn)進(jìn)行迭代擴(kuò)展形成社區(qū)的過程，擴(kuò)展策略是優(yōu)化適應(yīng)度函數(shù)，即適應(yīng)度函數(shù)達(dá)到局部最大值時(shí)才進(jìn)行擴(kuò)展[18]。

圖2 空手道俱樂部網(wǎng)絡(luò)層次樹圖對應(yīng)的重疊模塊度值

表2 HOMA、LFM以及CPM算法在空手道俱樂部網(wǎng)絡(luò)上的結(jié)果

從表2可以看出，LFM算法與HOMA算法均得到了2個(gè)社區(qū)，而CPM算法則為3個(gè)，并且發(fā)現(xiàn)的重疊節(jié)點(diǎn)即1號節(jié)點(diǎn)是原本網(wǎng)絡(luò)中的兩個(gè)核心節(jié)點(diǎn)之一，不應(yīng)該被歸為重疊節(jié)點(diǎn)，因此，CPM算法在Zachary’s Karate網(wǎng)絡(luò)上的結(jié)果不太理想。進(jìn)一步分析發(fā)現(xiàn)，LFM算法和HOMA算法得到的兩個(gè)社區(qū)與原本社區(qū)均出入不大，但LFM算法發(fā)現(xiàn)了5個(gè)重疊節(jié)點(diǎn)，因此，NMI值和EQ值比HOMA算法低，但結(jié)果也較為理想。綜上所述，HOMA算法在3個(gè)算法中實(shí)驗(yàn)結(jié)果最好，能夠發(fā)現(xiàn)重疊節(jié)點(diǎn)，挖掘到的社區(qū)結(jié)構(gòu)質(zhì)量較好，在Zachary’s Karate網(wǎng)絡(luò)上的實(shí)驗(yàn)效果較為理想。

3.2 LFR重疊網(wǎng)絡(luò)

第二個(gè)實(shí)驗(yàn)采用LFR人工網(wǎng)絡(luò)來驗(yàn)證HOMA算法檢測重疊節(jié)點(diǎn)的準(zhǔn)確率，LFR人工網(wǎng)絡(luò)的具體設(shè)定參數(shù)如表3所示。

表3 LFR重疊網(wǎng)絡(luò)設(shè)定參數(shù)

按照表3設(shè)定參數(shù)生成的LFR網(wǎng)絡(luò)共有5個(gè)社區(qū)和12個(gè)重疊節(jié)點(diǎn)，其社區(qū)劃分及重疊節(jié)點(diǎn)如表4所示。

將該網(wǎng)絡(luò)應(yīng)用于HOMA算法，結(jié)果如表5所示。由表5中數(shù)據(jù)可以看出，HOMA算法在LFR網(wǎng)絡(luò)中挖掘出5個(gè)社區(qū)，與實(shí)際網(wǎng)絡(luò)社區(qū)個(gè)數(shù)一致，發(fā)現(xiàn)重疊節(jié)點(diǎn)15個(gè)，比實(shí)際網(wǎng)絡(luò)多了3個(gè)，這種情況屬于正?，F(xiàn)象，因?yàn)榫W(wǎng)絡(luò)中存在一些社區(qū)隸屬度不高的節(jié)點(diǎn)，這些節(jié)點(diǎn)處于兩個(gè)或以上社區(qū)的中間層，當(dāng)不考慮重疊情況時(shí)，那么這些節(jié)點(diǎn)就會被劃分到其中某一個(gè)社區(qū)，而HOMA算法是對最大團(tuán)進(jìn)行擴(kuò)展的，那么這些節(jié)點(diǎn)就可能存在于不同的最大團(tuán)，最終被若干社區(qū)同時(shí)包含在內(nèi)，這也是為什么真實(shí)網(wǎng)絡(luò)如空手道俱樂部網(wǎng)絡(luò)和海豚社會網(wǎng)絡(luò)均能發(fā)現(xiàn)重疊節(jié)點(diǎn)的原因。在這15個(gè)節(jié)點(diǎn)中，共有10個(gè)節(jié)點(diǎn)與原本網(wǎng)絡(luò)相同，其正確率約為83.3%，因此，HOMA算法在該LFR網(wǎng)絡(luò)發(fā)現(xiàn)的重疊節(jié)點(diǎn)正確率較高。

表4 LFR重疊網(wǎng)絡(luò)社區(qū)分布

表5 HOMA算法在LFR網(wǎng)絡(luò)上檢測的社區(qū)分布

為進(jìn)一步探究不同模糊程度的社區(qū)結(jié)構(gòu)對重疊節(jié)點(diǎn)正確率的影響，通過改變γ的值，進(jìn)行多個(gè)網(wǎng)絡(luò)的實(shí)驗(yàn)，得到如圖3所示的曲線圖。從圖3可以看出，當(dāng)γ≤0.2時(shí)，由于社區(qū)結(jié)構(gòu)較為明顯，則HOMA算法識別正確重疊節(jié)點(diǎn)的比例較高；當(dāng)0.2<γ≤0.4時(shí)，此時(shí)HOMA算法隨著γ的增大其識別重疊節(jié)點(diǎn)的比例開始下降，但依然能夠發(fā)現(xiàn)大部分正確的重疊節(jié)點(diǎn)；當(dāng)γ＞0.4時(shí)，由于社區(qū)結(jié)構(gòu)逐漸模糊，重疊節(jié)點(diǎn)正確率下降較快，此時(shí)還能夠發(fā)現(xiàn)一小部分正確的重疊節(jié)點(diǎn)，而當(dāng)γ超過0.6時(shí)，社區(qū)結(jié)構(gòu)變得很不明顯，此時(shí)重疊節(jié)點(diǎn)正確率很低，說明HOMA算法在這種結(jié)構(gòu)的社區(qū)效果不理想。

圖3 不同γ值下的重疊節(jié)點(diǎn)正確率

4 總結(jié)

本文提出一種最大團(tuán)的層次化重疊社區(qū)發(fā)現(xiàn)算法，該算法首先提取網(wǎng)絡(luò)中的所有最大團(tuán)，但是網(wǎng)絡(luò)中存在附屬最大團(tuán)，附屬最大團(tuán)中的所有節(jié)點(diǎn)全部來自其他最大團(tuán)，顯然附屬最大團(tuán)會對檢測結(jié)果產(chǎn)生干擾，為了消除其影響同時(shí)降低復(fù)雜度，對最大團(tuán)的節(jié)點(diǎn)個(gè)數(shù)設(shè)置k值。其次，將網(wǎng)絡(luò)中的所有最大團(tuán)和單個(gè)節(jié)點(diǎn)當(dāng)作單獨(dú)社區(qū)，并用自定義的社區(qū)耦合強(qiáng)度對社區(qū)進(jìn)行擴(kuò)展合并，每次合并相似度最大的兩個(gè)社區(qū)，直到網(wǎng)絡(luò)中只剩下一個(gè)社區(qū)，這樣就形成了一個(gè)系統(tǒng)樹圖，最后用重疊模塊度對系統(tǒng)樹圖進(jìn)行剪枝，得到重疊社區(qū)劃分結(jié)果。