一種發現交疊社團的快速層次化算法

彭佳揚，楊路明，王建新，李敏，蔡娟

(中南大學 信息科學與工程學院，湖南 長沙，410083)

在現實世界中，很多自然、社會和科學系統都以網絡的形式存在，這些網絡很復雜，被稱為“復雜網絡”[1]。隨著人們對復雜網絡的拓撲結構、物理意義和數學特性的深入研究，發現許多實際網絡不但具有小世界性、無標度性等基本統計特性，還具有拓撲結構屬性——社團結構，具有同社團節點相互連接緊密、異社團節點相互連接稀疏的特點[2-6]。為了更好地分析復雜網絡的拓撲結構、理解復雜網絡的功能以及預測復雜網絡的行為，必須對網絡結構進行社團劃分。層次聚類算法作為社團發現最主要的一類方法，能夠展現復雜網絡中社團的層次化結構組成[7-9]。Newman[10]提出了基于局部搜索的快速復雜網絡聚類算法FN，其目的是使網絡模塊性(modularity)評價函數即Q函數極大化[11]。Q越高，意味著劃分的社團越有意義，很多社團劃分方法[12-15]的目的就是將Q極大化。Guimera等[3]提出了基于模擬退火算法的復雜網絡聚類算法GA，此算法具有跳過局部最優解、找到全局最優解的能力，從而具有很高的聚類精度。然而，Q函數是有偏的，并不能完全準確地刻畫最優的(或者說是真實的)網絡簇結構[1]。對于某些網絡，其真實的網絡簇結構對應的 Q是局部極大值，而非全局最大值。Guimera等[16]經進一步研究發現：對于某些隨機網絡，由于受到擾動的影響，明顯不好的網絡簇結構卻對應較高的Q。為此，Fortunato[17]研究了Q函數對聚類精度的影響，指出：對于大規模復雜網絡，采用這類優化方法傾向于找到粗糙的而不是精確的網絡社團結構。這意味著采用這類算法未必能找到大規模網絡中真正存在的全部社團，僅僅適合于小規模網絡的社團劃分。這種啟發式復雜網絡社團發現算法包括 MFC算法[18]、GN算法[2]及其改進算法[6,19]、WH算法[20]等。這些層次化社團發現算法將網絡劃分為不同的社團，每個點只屬于1個社團。然而，在許多實際網絡中，有些點可能屬于多個社團，所以，若能發現可交疊的社團結構，則更具有實際意義[1]。為了找到社團間重復的點，Palla等[4]提出基于k-團的算法CPM，能夠識別重疊網絡社團結構。其后提出k-dense[21]算法，也可以識別重疊的網絡社團結構，并且應用于各種實際網絡中。但是，這些方法又不能顯示出社團的層次化特性。Lancichinetti等[22]提出了 1種可以允許重疊的層次化社團發現算法。他們試圖找到合適函數的局部最優解來發現重疊的社團結構，圍繞1個種子節點來發現重疊社團的層次化結構。但是，由于種子節點是隨機選取的，不能保證所有重疊社團都有層次結構，為此，Shen等[23]提出了一種EAGLE算法[23]，用極大團作為初始社團，根據社團的相似性，應用凝聚法來合并社團，以此找到重疊的層次化社團結構。但是，由于要重復計算社團的相似度，算法復雜度極高，很難應用于大規模的實際網絡[11]。為了提高算法的運行效率，本文作者設計了一種發現層次化交疊社團的快速算法F-HOC：用極大團k-團作為初始社團，提出1個指標——社團連通性，以該指標為依據，用凝聚法對k-團進行弱社團檢測，將符合條件的社團進行遞歸合并，以達到網絡可交疊層次化快速聚類的目的。

1 發現層次化交疊社團的快速算法F-HOC

大多數層次化聚類算法在其凝聚過程中是對孤立的點進行擴展，本文提出的F-HOC算法則是從極大團開始進行擴展。由于初始的極大團中包含重復的點，所以，基于這些極大團擴展發現的社團很可能彼此交疊。在計算極大團時，有些極大團中的點分別屬于其它不同的極大團，這種極大團稱為附屬極大團(Subordinate maximal clique)[23]。附屬極大團容易誤導算法，本文不予考慮。實驗證明大多數附屬極大團的規模比較小，因此，F-HOC先找出所有大于等于k的極大團即k-團，這樣可以有效地剔除附屬極大團。但是，這樣可能會剔除一些比較小的非附屬極大團，k越大，越可能刪除更多的非附屬極大團，而k越小，則越可能保留附屬極大團。在實際網絡中，k一般取3～6[4,23]。在剔除小于k的附屬極大團后，有可能存在一些點不屬于任何極大團，這些點成為附屬點(Subordinate vertices)，將這些點作為單獨的初始社團參與合并過程。

EAGLE算法以社團的相似性作為合并兩社團的條件，但重復計算社團的相似性相當耗時；在大多數層次化聚類算法中，使用邊數之類的全局變量來劃分社團，而重復計算全局變量的算法時間復雜度非常高，很難應用于大型復雜網絡?？紤]到連接兩社團間的邊數越多，兩社團聯系越緊密，越有可能屬于1個社團，本文在F-HOC算法中采用1個新的指標——社團連通性，來評價2個社團連接是否緊密。

定義1 社團連通性CAB是評價2個社團連接是否緊密的1個指標：

式(1)中：分子 | EAB|+|EO′ |+2|EO|為連接兩社團的邊數；分母 | EAB|+|EA|+|EB|為兩社團的總邊數。CAB越大，則表示連接兩社團的邊占兩社團總邊數的比例越大，表明兩社團連接越緊密，兩者越有可能屬于同一個社團。

F-HOC以社團連通性指標為依據，用凝聚法對k-團進行合并判斷，最終目的是所發現的社團都滿足弱社團的定義。

定義 2 弱社團(Weak community)[6]是指子圖 H中所有節點與H內部節點的度之和大于H中所有節點與H外部節點連接的度之和。給定1個無向簡單圖G和1個子圖H( H ? G )，H滿足弱社團的定義，當且僅當：

其中：v為H中的節點；din(H,v)為v的內度；dout(H,v)為v的外度。

基于社團連通性和弱社團的量化定義，提出一種基于連通性的發現交疊社團的快速層次化算法F-HOC。

Input: 無向無權簡單圖G=(V,E)，初始極大團規模k；

Output: 可交疊的層次化社團。

步驟1 找出所有規?！輐的極大團，附屬點視為獨立初始社團。

步驟 2 對兩兩相連的社團采用 CAB進行判斷；對CAB進行降序排列，放入隊列CC中。

步驟3 依次判斷Cc中每2個社團是否合并。

(1) 若2個社團都不滿足弱社團的定義，則合并2個社團；

(2) 合并2個社團后，將這個CAB從隊列CC中移除，且將與新合并社團有連接的社團的CAB進行重新計算，將隊列CC重新排序；

步驟4 對不滿足合并條件的社團不進行處理。

步驟5 按CC的排序執行步驟3和4，直到隊列CC為空為止。

步驟6 輸出層次化合并的可交疊社團。

F-HOC的輸入是1個無向無權簡單圖G=(V,E)。首先用經典的Bron-Kerbosch算法[24]找到所有極大團，過濾圖中的規模小于k的極大團，剩下規模大于等于k的每個極大團視為1個初始社團，附屬點也視為獨立的初始社團。然后計算兩兩相連社團的社團連通性，其值越大，表明2個社團越有可能屬于同一個社團。根據計算所得的社團連通性值進行降序排列，放入隊列CC中，從大到小分別判斷兩社團是否滿足弱社團定義。只有在2個社團都不滿足時才合并，直到隊列CC為空為止，整個層次化聚類過程結束，輸出得到的所有的社團，包括合并過程和最終的社團?？筛鶕喜⑦^程畫出層次化社團樹狀圖，以展示復雜網絡中社團的層次化組織結構。

因為F-HOC算法是利用社團連通性進行判斷，只需計算局部變量，其時間復雜度比EAGLE用全局變量計算的低。EAGLE 的時間復雜度[23]為O(n2+(h+n)s+n2s) (不計計算極大團的時間，其中，n為點的個數，s為初始社團k-團的個數，h為鄰居社團對(兩兩相連社團對或者是相似社團對)的個數)。F-HOC中，計算所有鄰居社團對社團連通性的時間復雜度為 O(h)，重復合并的時間復雜度為 O(h2(s-1))，整個算法的時間復雜度為 O(h2s)(同樣不計計算極大團的時間)。比較EAGLE的時間復雜度，h遠小于n，所以，F-HOC更適用于大型的復雜網絡。

2 實驗結果及其分析

采用已知社團結構的隨機網絡進行測試[1]，比較F-HOC和EAGLE的精度和速度。已知社團結構的隨機網絡定義為RN(C, b, d, pin)(其中：C為網絡社團的個數；b為每個社團包含節點的個數；d為網絡中節點的平均度；pin為社團內連接密度(即社團內連接總數與網絡連接總數的比值))。pin越大，隨機網絡的社團結構越明顯，反之，社團結構越模糊。特別地，當pin＜0.5時，認為該隨機網絡不具有社團結構。實驗采用被普遍接受的基準隨機網絡RN(4, 32, 16, pin)作為標準數據，k取4，并設定了2個點為重疊點。

2.1 算法的敏感度

敏感度Sn是用來評估社團識別精度的重要指標[25]，是指已知社團中被算法發現出來的部分所占比例：

其中：PT(True positive)表示算法識別出來的社團 Cp與已知社團Ck匹配程度OS(Cp, Ck)超過匹配度閾值的數量；NF(False negative)表示已知社團中沒有被識別出來的數量。

算法識別出來的社團(Predicted community, Cp)與已知社團(Known community, Ck)的匹配程度OS(Cp, Ck)的計算公式[25-26]為：

若 Cp和 Ck的匹配程度 OS(Cp, Ck)超過給定的閾值，則稱這2個社團匹配。對于已知社團Ck，若識別出的社團Cp與之匹配程度OS(Cp, Ck)超過給定閾值，則稱該已知社團被標識；若OS(Cp, Ck)=1，則稱該社團被完全標識。

圖1所示表示pin取0.9，0.8和0.7時，F-HOC和EAGLE在不同匹配閾值OS下的匹配精度Sn，匹配精度用敏感度來表示，曲線上的每個數據點是兩算法識別 50個已知社團結構的隨機網絡得到的平均 Sn。從圖 1可以看出：在網絡社團性很強的情況下，即 pin為0.9和0.8時，F-HOC算法的敏感度與EAGLE算法的敏感度相差不多，都比較高。這也說明 F-HOC算法與EAGLE算法在網絡社團性較明顯的情況下，兩算法都能準確地識別出已知社團。當pin為0.7時，F-HOC算法的敏感度隨著匹配閾值的增加開始下降，這與大多數復雜網絡聚類算法的結果類似[1]，在網絡社團性不是很強的情況下，識別能力開始顯著降低。

圖1 不同匹配閾值下F-HOC與EAGLE的敏感度Sn的比較Fig.1 Comparison of Sn of F-HOC and EAGLE with respect to different overlapping score thresholds

2.2 算法的速度

算法的速度是評價聚類算法的重要指標。本文比較分析了F-HOC和EAGLE 2種算法在相同規模、不同社團性網絡下的運行時間以及不同規模網絡下的運行時間，如表1和圖2所示。表1所示表示pin取0.9～0.5時，F-HOC和EAGLE識別50個隨機網絡得到的平均時間；圖2所示為不同規模下算法的運行時間。選用的測試網絡是隨機網絡RN(4, b,16,0.8)。該網絡由社團結構確定，但其規?？捎蒪來調節，共包含4b個網絡節點，64b條網絡連接。當b =1 024時，EAGLE的運行時間超過了48 h還沒有得出結果，所以沒有被列出。

表1 不同網絡社團性下F-HOC與EAGLE算法的運行時間比較Table 1 Comparison of time of F-HOC and EAGLE with respect to different network connections s

從表 1可以看出：不管網絡社團性是否明顯，F-HOC的運行效率都比 EAGLE的高很多。因為F-HOC算法是利用社團連通性進行判斷，只需計算局部變量，計算復雜度較低，所以，不論網絡社團性如何，F-HOC的速度都比EAGLE的速度快。如圖2所示，不管網絡規模如何，F-HOC比EAGLE的速度快很多，且隨著網絡規模的增加，EAGLE的運行時間提升幅度比F-HOC的時間提升幅度快很多，而F-HOC時間變化幅度不大。網絡的規模越大，F-HOC的優勢越明顯。而在實際網絡中，網絡節點一般都在 1 000以上，且隨著大規模網絡數據的不斷增加，F-HOC更適用于大規模的復雜網絡。

圖2 不同網絡規模下F-HOC與EAGEL的運行時間比較Fig.2 Comparison of time of F-HOC and EAGLE with respect to different sizes of networks

2.3 交疊點的識別度

因為算法可以用于識別交疊的模塊，在生成已知社團結構的隨機網絡時，加入了1個重疊參數，即在生成隨機網絡時保證社團之間有重疊點。為了驗證算法識別社團的交疊性能力，檢查了設定的重疊點是否出現在多個輸出社團內，若都找到，則令Ol=1；若有1個沒有找到，則令Ol=0，得出對已知交疊點的識別度Ov：

其中：n表示隨機網絡的個數。表2所示為pin取0.9～0.5時，F-HOC和EAGLE對已知交疊點的識別度。從表2可以看出：在網絡社團性很強的情況下即pin為0.9和0.8時，F-HOC和EAGLE都能準確地識別出已知的重疊點，也就是說算法確實找到了這些重疊的點，并且這些點都存在于多個社團內。但隨著網絡社團性的減弱，識別重疊點的能力也明顯降低，這與識別社團的能力呈正比。

表2 不同網絡社團性下F-HOC與EAGLE算法對已知交疊點的識別度OvTable 2 Comparison of Ov of F-HOC and EAGLE with respect to different network connections

表3 F-HOC與EAGLE算法應用于足球網絡的匹配度對照結果Table 3 Comparison of overlapping scores which applying F-HOC and EAGLE in football network

3 應用

將F-HOC算法應用于社團性較強的足球網絡[2]，并與EAGLE的結果進行比較，結果如表3所示。表3中列出了所有OS(Cp, Ck)≥0.2的社團對和其社團匹配值，足球網絡有12個社團。從表3可以看出：F-HOC找到了 10個社團，其中與已知社團完全匹配的有 6個，占已知社團的50%；匹配值高于0.500 000的有7個，占已知社團的58%。EAGLE找到了8個社團，其中與已知社團完全匹配的只有2個，僅占已知社團的17%；匹配值高于0.500 000的有6個，占已知社團的 50%。這也說明在社團性明顯的實際網絡中，F-HOC的精度比EAGLE的精度高。

F-HOC算法的運行時間為3.547 s，EAGLE算法的運行時間為9 490 s，可見，F-HOC的運行速度明顯增大。

4 結論

(1) 設計了一種發現交疊社團的快速層次化算法F-HOC。以提出的度量社團間連通性的指標為依據，采用凝聚法對k-團進行弱社團檢測，對符合條件的社團進行合并，遞歸合并以達到網絡可交疊層次化快速聚類的目的。

(2) F-HOC以極大團為初始社團，在此基礎上進行合并，所以，社團都存在交疊性。

(3) F-HOC利用社團連通性這一指標進行判斷，計算復雜度比EAGLE采用的社團相似度這一全局變量低，所以，不論網絡社團性如何，速度都比EAGLE的運行速度快，有明顯的優勢；且隨著網絡規模的增大，F-HOC運行時間的增幅比EAGLE運行時間的增幅小很多。

(4) 在網絡社團性強的情況下，F-HOC能準確識別出已知的社團結構和重疊點，精度與EAGLE的精度相當；但是，在社團性較弱的情況下，雖然速度比EAGLE的快，但是，識別能力比EAGLE的弱。由于EAGLE是利用Q函數來劃分社團性的，對于明顯不好的網絡簇結構，EAGLE也有可能得出較高的Q，所以，F-HOC在社團性不是很強的情況下，識別能力比EAGLE的弱并不能說明F-HOC的識別能力差。

(5) 總體來說，對于大規模的社團結構明顯的復雜網絡，用F-HOC算法發現可交疊的層次化社團結構具有很高的精度和運行效率。

[1] 楊博, 劉大有, LIU Ji-ming, 等. 復雜網絡聚類方法[J]. 軟件學報, 2009, 20(1): 54-66.YANG Bo, LIU Da-you, LIU Ji-ming, et al. Complex network clustering algorithms[J]. Journal of Software, 2009, 20(1):54-66.

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

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

[4] Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structures of complex networks in nature and society[J]. Nature, 2005, 435(6): 814-818.

[5] Wilkinson D M, Huberman B A. A method for finding communities of related genes[J]. Proc of the National Academy of Science, 2004, 101(Suppl 1): 5241-5248.

[6] Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks[J]. Proc of the National Academy of Science, 2004, 101(9): 2658-2663.

[7] Sales-Pardo M, Guimerà R, Moreira A A, et al. Extracting the hierarchical organization of complex systems[J]. Proc of the National Academy of Science, 2007, 104(39): 15224-15229.

[8] Ravasz E, Somera A L, Mongru D A, et al. Hierarchical organization of modularity in metabolic networks[J]. Science,2002, 297(8): 1551-1555.

[9] Pons P. Post-processing hierarchical community structures:Quality improvements and multi-scale view[EB/OL].[2006-08-09]. http://arxiv.org/ps_cache/cs/pdf/0608/0608050 v1.pdf.

[10] Newman M E J. Fast algorithm for detecting community structure in networks[J]. The European Physical Journal B, 2004,38(6): 321-330.

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

[12] Wang Z, Zhang J. In serach of the biological significance of modular structures in protein networks[J]. PLOS Computational Biology, 2007, 3(6): 1011-1021.

[13] Newman M E J. Modularity and communities structure in networks[J]. Proc of the National Academy of Science, 2006,103(23): 8577-8582.

[14] Pujol J M, Béjar J, Delgado J. Clustering algorithm for determining community structure in large networks[J]. Physical Review E, 2006, 74(1): 016107-1-016107-9.

[15] Duch J, Arenas A. Community detection in complex networks using extreme optimization[J]. Physical Review E, 2005, 72(2):027104-1-027104-4.

[16] Guimera R, Sales M, Amaral L A N. Modularity from fluctuations in random graphs and complex networks[J].Physical Review E, 2004, 70(2): 025101-1-025101-8.

[17] Fortunato S, Barthelemy M. Resolution limit in community detection[J]. Proc of the National Academy of Science, 2007,104(1): 36-41.

[18] Flake G W, Lawrence S, Giles C L, et al. Self-Organization and identification of Web communities[J]. IEEE Computer, 2002,35(3): 66-71.

[19] Tyler J R, Wilkinson D M, Huberman B A. Email as spectroscopy: Automated discovery of community structure within organizations[J]. The Information Society, 2005, 21(2):143-153.

[20] Wu F, Huberman B A. Finding communities in linear time: A physics approach[J]. European Physical Journal B, 2004, 38(2):331-338.

[21] Saito K, Yamada T, Kazama K. Extracting communities from complex networks by the k-dense method[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2008, E91-A(11): 3304-3311.

[22] Lancichinetti A, Fortunato S, Kertesz J. Detecting the overlapping and hierarchical community structure of complex networks[EB/OL]. [2009-05-11]. http://arxiv.org/ps_cache/arxiv/pdf/0802/0802.1218 v2.pdf.

[23] SHEN Hua, CHENG Xue, CAI Kai, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A,2009, 388: 1706-1712

[24] Bron C, Kerbosch J. Finding all cliques in an undirected graph[J].Communications of the ACM, 1973, 16(9): 575-577.

[25] Bader G D, Hogue C W. An automated method for finding molecular complexes in large protein interaction networks[J].BMC Bioinformatics, 2003, 4(2): 1-27.

[26] King A D, Przulj N, Jurisica I. Protein complex prediction via cost-based clustering[J]. Bioinformatics, 2004, 20(17):3013-3020.