基于最大團的層次化重疊社區發現算法

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

中國礦業大學 計算機科學與技術學院，江蘇 徐州 221116

1 引言

早期很多傳統的社區發現算法在挖掘社區結構時都是基于網絡中節點的唯一性的，即每個節點都從屬于某一個社區。然而，近些年研究發現，大量真實網絡的社區結構并非如此涇渭分明，很多社區在某些方面彼此具有較為緊密的聯系，社區之間存在交叉重疊現象，因此，社區結構通常具有重疊性和層次性。

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

2 基于最大團的層次化重疊社區發現算法

2.1 最大團問題求解

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

2.2 社區的擴展合并

HOMA算法的第二部分就是對最大團或單個節點構成的社區進行合并擴展形成層次樹圖，這一部分是整個算法最關鍵的地方，如何迭代合并社區直接關系到算法的最終結果，首先介紹幾個與擴展過程相關的定義。

定義1（重疊節點集合）兩個社區間相同節點構成的重疊節點集合可表示為：

其中，Ci表示社區i，V(Ci)表示社區i所包含的節點集合。

定義2（共同鄰居節點集合）兩個社區間的共同鄰居節點集合可表示為：

其中，N(Ci)表示與社區i內部節點相連但不屬于該社區的節點集合。

定義3（社區間橋接邊）兩個社區間的橋接邊是指兩個端點分別在不同社區內所構成的邊，可表示為：

在2.1節通過調用改進的Bron_Kerbosch算法得到最大團集并初始化為社區后，現在要將其進行合并擴展。首先，要解決穩定性問題，即不能隨機選擇一個社區為擴展起點，而應該根據某種標準進行選擇，這種標準也可稱為合并兩個社區的原則，在合并兩個節點時可以依據節點相似度，那么這里可以依據社區相似度，只是節點相似度已經有很多經典算法對其進行研究，而社區相似度則并無一個較為權威的定義，也沒有固定的計算公式，為了便于區分節點相似度，本文將社區間的相似度稱為社區的耦合強度。

社區的耦合強度反映了兩個社區間的關聯程度，關于節點相似度已有很多算法進行研究[11-12]，社區間的關聯程度并沒有一個權威的定義，兩個社區間聯系越緊密，則耦合強度越大，而兩個社區間的關聯程度又取決于重疊節點、共同鄰居節點和社區間橋接邊等因素，分析如下：

（1）重疊節點，兩個社區間的重疊節點越多，其耦合強度越大，當小于臨界值時，這兩個社區即為同一個社區。此外，如果一個社區包含相對較少的節點，而另一個社區擁有更多的節點，那么可認為節點少的社區是另一個社區的子社區，則可將兩個社區進行合并。

（2）共同鄰居節點，共同鄰居是影響節點相似度大小的因素之一，而社區是由節點組成的，那么共同鄰居也是社區耦合強度的影響因素之一，共同鄰居越多，則社區耦合強度越大。

（3）社區間橋接邊，社區間的橋接邊反映了社區間連接的緊密程度，因此，兩個社區間的橋接邊越多，那么社區的耦合強度越大。

基于以上分析，綜合考慮兩個社區間的重疊節點、共同鄰居節點和橋接邊這三種因素，定義社區耦合強度如下所示：

其中，CS是耦合強度，α是調節系數，其值在0至1之間，V(Ci)是社區i的節點集合，則表示社區i和 j共同擁有的節點即重疊節點占其中較小社區的節點個數的比例。N(Ci)表示社區i的鄰居節點集合，表示社區i和 j社區的共同鄰居節點個數占所有鄰居節點個數的比例。E(Ci,Cj)表示社區i和 j之間的橋接邊的集合，sum(Ei,Ej)表示社區i和社區 j的邊數和。

α是介于0和1之間的調節參數，作用是為了應對不同的情況，社區中除了存在最大團還有許多單個節點。當計算單個節點社區與其他社區的耦合強度時，只需考慮該節點與其他社區之間連邊的數量，那么這時候通過設置α的值可以只計算橋接邊的比例或共同鄰居比例。

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

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

2.3 基于最大團的層次化重疊社區發現算法

HOMA算法能夠同時檢測網絡中的層次結構和重疊結構，其主要包括提取最大團、擴展社區生成樹狀圖以及對樹狀圖進行剪枝這三個步驟：

（1）采用改進的Bron_Kerbosch算法提取網絡中所有的最大團，由于節點個數小于3的最大團較多且容易成為附屬最大團（團中的節點都來源于其他團），因此可設置一個參數k來控制最大團的最少節點個數，即提高了正確度同時降低了計算量。然后將所有的最大團以及未出現在任何團中的單個節點初始化為獨立的社區。

（2）計算網絡中任意兩個社區間的耦合強度，構造耦合強度矩陣，然后矩陣中最大值對應的兩個社區進行合并，得到新的社區，再計算新社區和其他社區間的耦合強度，更新耦合強度矩陣。這樣每次總是合并矩陣中耦合強度最大的兩個社區，然后更新矩陣，直到最后只剩下一個社區，在這個過程中就生成了一個層次樹圖。

（3）利用重疊模塊度函數對樹狀圖進行剪枝，選擇模塊度最大的一層作為社區劃分結果。

3 實驗分析與結果

通過展示HOMA算法在不同網絡上的實驗結果來驗證HOMA算法發現層次結構和重疊結構社區的準確度，實驗網絡包括真實網絡和LFR人工基準網絡。實驗中采用NMI（Normalised Mutual Information）[16]作為社區結構質量優劣的參考標準。NMI的值介于0和1之間，值越大說明兩個社區劃分的結果越相似，值為1時則兩個社區劃分結果完全相同。實驗環境為：四核1.4 GHz處理器；內存4 GB；操作系統為Windows 7；使用MATLAB及Java編程。

3.1 空手道俱樂部網絡

空手道俱樂部網絡又稱Zachary’s Karate網絡，該網絡是從現實世界的一個空手道俱樂部抽象化得到的。該俱樂部由34個成員組成，將成員之間的聯系抽象為邊，則一共有78條邊。

HOMA算法的第一步是提取網絡中的最大團，將k值設置為3，即只提取節點數不少于3的最大團，這一階段一共生成了25個最大團，然后將沒有被最大團集合涵蓋在內的兩個節點即10號節點和12號節點初始化為社區，則一共有27個社區，所有社區節點的分布情況如表1所示。

表1 HOMA算法在Zachary’s Karate網絡提取的最大團集合

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

圖1 HOMA算法在空手道俱樂部網絡上生成的層次樹狀圖

由圖1可以看出，初始的27個社區一共進行了26次合并操作，在最后一次的合并操作后，整個網絡中只剩下一個社區，這個社區包含了最開始的27個社區。在每次合并后，更新一次整個網絡的重疊模塊度EQ，結果如圖2所示。圖2中，在第25次合并時，模塊度值達到最大值，即此時社區結構劃分最為理想，因此將這一層作為該網絡的近似最優劃分結果。此時劃分，則一共得到2個社區，這與Zachary’s Karate網絡原本的社區數量吻合。進一步分析發現，節點3和9均出現在兩個社區內，因此這兩個節點為重疊節點。

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

圖2 空手道俱樂部網絡層次樹圖對應的重疊模塊度值

表2 HOMA、LFM以及CPM算法在空手道俱樂部網絡上的結果

從表2可以看出，LFM算法與HOMA算法均得到了2個社區，而CPM算法則為3個，并且發現的重疊節點即1號節點是原本網絡中的兩個核心節點之一，不應該被歸為重疊節點，因此，CPM算法在Zachary’s Karate網絡上的結果不太理想。進一步分析發現，LFM算法和HOMA算法得到的兩個社區與原本社區均出入不大，但LFM算法發現了5個重疊節點，因此，NMI值和EQ值比HOMA算法低，但結果也較為理想。綜上所述，HOMA算法在3個算法中實驗結果最好，能夠發現重疊節點，挖掘到的社區結構質量較好，在Zachary’s Karate網絡上的實驗效果較為理想。

3.2 LFR重疊網絡

第二個實驗采用LFR人工網絡來驗證HOMA算法檢測重疊節點的準確率，LFR人工網絡的具體設定參數如表3所示。

表3 LFR重疊網絡設定參數

按照表3設定參數生成的LFR網絡共有5個社區和12個重疊節點，其社區劃分及重疊節點如表4所示。

將該網絡應用于HOMA算法，結果如表5所示。由表5中數據可以看出，HOMA算法在LFR網絡中挖掘出5個社區，與實際網絡社區個數一致，發現重疊節點15個，比實際網絡多了3個，這種情況屬于正常現象，因為網絡中存在一些社區隸屬度不高的節點，這些節點處于兩個或以上社區的中間層，當不考慮重疊情況時，那么這些節點就會被劃分到其中某一個社區，而HOMA算法是對最大團進行擴展的，那么這些節點就可能存在于不同的最大團，最終被若干社區同時包含在內，這也是為什么真實網絡如空手道俱樂部網絡和海豚社會網絡均能發現重疊節點的原因。在這15個節點中，共有10個節點與原本網絡相同，其正確率約為83.3%，因此，HOMA算法在該LFR網絡發現的重疊節點正確率較高。

表4 LFR重疊網絡社區分布

表5 HOMA算法在LFR網絡上檢測的社區分布

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

圖3 不同γ值下的重疊節點正確率

4 總結

本文提出一種最大團的層次化重疊社區發現算法，該算法首先提取網絡中的所有最大團，但是網絡中存在附屬最大團，附屬最大團中的所有節點全部來自其他最大團，顯然附屬最大團會對檢測結果產生干擾，為了消除其影響同時降低復雜度，對最大團的節點個數設置k值。其次，將網絡中的所有最大團和單個節點當作單獨社區，并用自定義的社區耦合強度對社區進行擴展合并，每次合并相似度最大的兩個社區，直到網絡中只剩下一個社區，這樣就形成了一個系統樹圖，最后用重疊模塊度對系統樹圖進行剪枝，得到重疊社區劃分結果。