利用堆數據結構實現鄰域重疊社團結構挖掘

任成磊, 韓定定, 蒲　鵬, 張嘉誠

(華東師范大學信息科學技術學院, 上海 200241)

?

利用堆數據結構實現鄰域重疊社團結構挖掘

任成磊, 韓定定, 蒲鵬, 張嘉誠

(華東師范大學信息科學技術學院, 上海 200241)

摘要:基于當前復雜網絡中社團劃分算法普遍存在算法復雜度過高以及重疊節點挖掘不準確的局限性，提出了一種高效、快速、準確的社團劃分算法。基于貪婪算法，建立最大模塊度矩陣，并采用堆數據結構，劃分非鄰域重疊社團。通過分析局部網絡的連邊情況，計算鄰域社團的劃分密度，以準確挖掘社團間的重疊節點。新算法經過仿真分析和實證研究表明，算法復雜度降到近線性。

關鍵詞：社團挖掘；鄰域重疊；模塊度；劃分密度；時間復雜度

0引言

隨著對網絡性質的物理意義和數學特性的深入研究，人們發現在社會網、神經網、蛋白質網、萬維網、通信網等網絡中，普遍存在著一種特性——社團結構[1-4]。網絡是由若干個團簇構成的，每個團簇內部的節點之間的連接非常緊密，但是各個團簇之間的連接卻相對比較稀疏。這些子團簇就被稱為社團，社團結構可以直觀形象地揭示一個網絡內部是如何自組織的，以及各個團簇之間的關系。因此，復雜網絡社團結構的探測研究，對于網絡的拓撲結構分析、功能的理解和網絡行為動力學預測等有著重要的意義[5-6]。

近幾年，復雜網絡中社團結構的挖掘得到了各個領域科學家的廣泛研究。Kernighan等[7]基于貪婪算法的基本原理，通過優化兩個社團之間的連邊，準確地將網絡劃分為兩個已知大小的社團。Giran等[8]基于各個節點間的連接強度，提出了一種分裂方法，通過不斷地從網絡中移除介數最大的邊，把網絡自然地劃分為不同的社團結構。Newman等[9]基于模塊度，提出了一種快速凝聚算法，算法具有較低的復雜度，可以實現大規模網絡社團結構的快速劃分。Clauset等[10]在Newman快速算法的基礎上，通過更新網絡的模塊度，提出了一種新的貪婪算法，該算法的復雜度只有O(nlog2n)，已接近線性，是目前在事先不知道社團數目的情況下，最快的社團劃分算法。以上諸多算法可以將網絡劃分為若干個互相分離的社團，而現實中很多網絡并不存在絕對的彼此獨立的社團結構；相反，他們是由許多彼此重疊的社團構成。比如，我們每個人根據不同的分類方法都會屬于多個不同的社團(如學校、家庭、不同的興趣小組等)，因此以上的社團劃分算法并不適合重疊社團結構的劃分[11]。近幾年，重疊社團結構的豐富性引起了眾多學者的廣泛研究，很多重疊社團結構挖掘算法被提出。Palla等[12]提出了一種派系過濾算法，通過挖掘網絡中的全耦合子圖，實現重疊社團結構劃分。楊歡等[13]基于完全子圖的社團探測算法，通過計算每一對完全子圖的重疊節點個數，設置合并完全子圖的閾值，快速地實現網絡中重疊社團結構挖掘。Ahn等[14]通過對網絡中的邊進行社團劃分，而不是傳統方法中的節點，以劃分密度D為重疊社團的檢測標準，有效地實現了網絡中重疊節點的挖掘。張忠元等[15]提出一種二元對稱矩陣分解方法，首先利用非負對稱矩陣算法對網絡的社團成員矩陣初始化，然后對初始成員矩陣進行優化，最后統計各個社團中的連邊數以及節點數并計算整個網絡的劃分密度，從而準確地挖掘出社團間的重疊部分。鄰域重疊社團劃分算法雖然可以準確地挖掘網絡中的重疊節點，但是在網絡社團結構的劃分上卻存在模糊性，社團劃分不夠準確，此外算法復雜度較高，難以實現大規模網絡重疊節點挖掘。針對上述問題，本文將二者的優勢揉合到一起，利用堆的數據結構，快速地實現非鄰域社團結構劃分，并通過分析局部網絡的連邊情況，利用劃分密度準確地挖掘出網絡中的重疊節點。

1模塊度Q和劃分密度D

為了衡量網絡社團劃分結果的合理性，科學家提出了一系列衡量標準。其中，在非鄰域社團結構劃分方面，Newman等[8]引進了一個衡量網絡劃分質量的標準——模塊度Q。Q值表征了網絡社團劃分的質量，Q值越大，表明社團內部的連邊越多，而社團之間的連邊越少，此時社團劃分質量也越高。模塊度值Q的公式為

(1)

其中，m為網絡中的邊數，vw為節點，Avw為網絡的連接矩陣中的元素，若節點v和節點w之間有邊相連接則值為1，否則為0，kv表示節點v的度值，kw表示節點w的度值，若節點v和節點w屬于一個社團，則δ(cv，cw)函數值為1，否則為0。式(1)的物理意義是：網絡中連接兩個同種類型的節點的邊(即社團內部邊)的比例，減去在同樣的社團結構下任意連接這兩個節點的邊的比例的期望值。如果社團內部邊的比例不大于任意連接時的期望值，則有Q=0。Q的上限值是1，Q越接近這個值，就說明社團結構越明顯。實際網絡中，該值通常位于0.3～0.7之間。在以往的非鄰域重疊社團劃分研究工作中，模塊度Q被作為一個重要的衡量標準，用以衡量社團劃分結果的準確性。

隨著復雜網絡社團挖掘研究的深入，人們發現復雜網絡中很多社團之間都存在著鄰域重疊結構。因為傳統的社團劃分算法難以實現鄰域重疊結構劃分，所以許多針對網絡鄰域重疊社團結構的挖掘算法被提出。傳統的模塊度Q已經難以準確衡量鄰域重疊社團劃分算法的準確性，Ahn等[14]基于局部網絡的連邊情況，提出了一個衡量網絡鄰域社團劃分質量的標準——劃分密度D。在一個有M條邊，N個節點的網絡中，社團c的劃分密度為

(2)

其中，Dc為社團c的劃分密度，mc為社團c中的邊數，nc為社團c中的節點數。整個網絡的劃分密度是所有子社團密度值之和的平均值，對應的公式為

(3)

2基于堆數據結構的社團挖掘

堆數據結構是一種數組對象，可以被認為是一棵完全二叉樹。根據完全二叉樹中節點的優先級可以將堆分為最大堆和最小堆兩種類型。最大堆中父節點的值大于兩個子節點的值，而最小堆中父節點的值小于兩個子節點的值。圖1是最大堆與最小堆的一個例子。

圖1　最大堆與最小堆示例圖

由于堆具有獨特的數據結構，常被用于實現數據排序，算法簡單，復雜度低。在本文中，首先采用最大堆數據排序法來計算和更新網絡的模塊度，快速地實現網絡的非鄰域社團結構劃分，并以此作為初始的社團成員矩陣；然后，再對網絡中的邊進行分析，若一條邊中的兩個節點在兩個不同的社團中，那么這兩個節點中有一個節點應該是鄰域社團的重疊節點，結合當前合理的鄰域重疊社團衡量標準——劃分密度D，分析該對節點中哪一個節點算作重疊節點更加合理。

在本文中，鄰域重疊社團結構挖掘算法一共用到了3種數據結構：

1)模塊度增量矩陣ΔQij：它與網絡的鄰接矩陣A一樣，是一個稀疏矩陣，初始化公式如下所示：

(4)

其中，m為網絡中的總邊數，ki為節點i的度，kj為節點j的度。

2)最大堆H。最大堆H中存儲的是模塊度增量矩陣ΔQij每一行的最大元素，以及最大元素對應的兩個社團的編號i和j。

3)輔助向量α1：輔助向量初始化公式為

(5)

其中，m為網絡中的總邊數，ki為節點i的度。

基于以上3種數據結構，鄰域重疊社團挖掘算法流程為

1)初始化。利用公式(4)、(5)計算網絡初始化模塊度增量矩陣ΔQij和輔助向量i，得到了初始化的模塊度增量矩陣以后，利用最大堆排序法，讀取增量矩陣中的每一行最大元素ΔQij構成最大堆H。

2)從最大堆H中選擇最大的ΔQij，合并相應的社團i和社團j，標記合并后的社團序號為j；并更新模塊度增量矩陣ΔQij、最大堆H和輔助向量αi，以及合并之后的模塊度值Q+ΔQij。

(1)ΔQij的更新：刪除第i行和第i列的元素，更新第j行和第j列的元素：

(6)

(2)H的更新：每次更新ΔQij后，更新最大堆中相應行的最大元素。

(3)αi的更新：

(7)

3)重復步驟2)，直到最大堆H中的元素全部變成負值，此時得到的就是網絡最佳的非鄰域重疊社團結構。

4)讀取網絡連邊Lsd，若當前邊對應的兩個節點從屬于不同的社團，分別將源節點(s)和目標節點(d)作為重疊節點，重新統計各個社團中的連邊數和節點數，利用劃分密度公式計算得到源節點的劃分密度DS和目標節點的劃分密度Dd。若DS大于Dd，則源節點是兩個社團間的重疊節點，反之目標節點是兩個社團間的重疊節點，記錄重疊節點。

5)重復步驟4)，直到網絡中的所有邊都被檢測完畢，將非鄰域重疊社團成員矩陣和重疊節點結合，實現網絡的鄰域重疊社團結構挖掘。

3算法復雜度近線性

本文提出的鄰域重疊社團結構挖掘算法主要是由兩部分組成：非鄰域重疊社團結構劃分和社團間重疊節點挖掘。本文基于堆數據結構快速實現社團成員矩陣的初始化，對于一個有n個節點，m條邊的網絡，算法復雜度為O(mdlogn)(d表示網絡的深度)[9]。而現實中很多網絡都是稀疏網絡，則有m≈n、d≈logn，在這種情況下，非鄰域重疊社團劃分算法的復雜度近似為O(nlog2n)。此時算法復雜度近似為線性，運行速度快。此外，算法本身基于模塊度值，通過更新模塊度增量矩陣得到整個網絡的最大模塊度值，所以最終的社團劃分結果也是最佳結果。在最優的非鄰域社團結構基礎上，遍歷網絡中的m條邊，分析網絡中的連邊信息。若當前邊上的一對節點從屬于不同的社團，則需要把其中的源節點和目標節點分別作為重疊節點，統計對應的社團中新出現的邊，并計算網絡的劃分密度D，其中較大值對應的節點即為重疊節點。將網絡信息以鄰接表的形式存儲，當社團中增加一個節點，判斷該節點的鄰居節點是否也在當前社團中，此時整個過程的算法復雜度為O(k)(其中k為網絡的平均度)。假設在最壞的情況下，每條邊對應的節點對都從屬于不同的社團，則社團重疊結構挖掘過程的算法復雜度為O(mk)，在稀疏網絡中m≈n，此時算法的復雜度近似為O(nk)。綜上所述，本文提出的鄰域重疊社團結構挖掘算法的復雜度近似為O(n(log2n+k))，近似為線性，因此可以將它應用到大規模網絡鄰域重疊社團結構挖掘。

圖2　模擬網絡驗證鄰域重疊社團結構挖掘算法的有效性

4實驗結果與分析

4.1利用模擬網絡驗證算法

本文利用一個模擬網絡來驗證算法的準確性，在圖2中，一個模擬網絡中有兩個社團，其中節點5和節點6是兩個社團所共有的重疊節點。首先，我們對網絡進行初始化，計算得到模塊度增量矩陣ΔQij和輔助向量αi以及最大堆H；然后利用堆的數據結構計算和更新網絡的模塊度，快速地實現非鄰域社團結構劃分；最后遍歷網絡中的所有邊，基于劃分密度D挖掘出社團之間的重疊節點，并將重疊節點與非鄰域社團結構相結合，得到鄰域重疊社團結構。從圖2中可以看到，鄰域重疊社團挖掘算法準確地將網絡劃分成兩個重疊的社團，其中1表示該節點屬于社團，0表示不屬于社團。

4.2實證網絡驗證算法

在本節，我們將本文所提出的鄰域重疊社團結構劃分算法應用到已知社團結構的空手道俱樂部網和海豚網中，實現網絡中的鄰域社團結構挖掘，以驗證鄰域社團劃分算法的準確性。

20世紀70年代，Zachary[16]基于美國一所大學中的空手道俱樂部成員間的相互社會關系，構造了他們之間的關系網。在他研究過程中，該俱樂部的主管與校長之間因是否提高俱樂部收費的問題產生了爭執，導致俱樂部分裂成了兩個分別以主管和校長為核心的小俱樂部。因此空手道俱樂部網成為復雜網絡社團劃分方面的一個經典網絡，被廣泛用于檢驗社團劃分算法的準確度。圖3為利用本文所提出的鄰域重疊社團結構劃分算法對經典的空手道俱樂部網絡進行鄰域社團劃分所得結果。

其中，橙色節點和淡粉色節點分別屬于不同的社團，中間的紫色節點是兩個社團之間的重疊節點。基于模塊度Q，利用堆數據結構合理地將空手道網絡劃分為彼此不重疊的兩部分，其社團結構與現實中的空手道俱樂部網絡幾乎一致。通過分析網絡中的連邊情況，利用劃分密度D，準確地挖掘出網絡中的重疊節點，其中節點1,3,9,34不但與左邊社團中多個節點相連，而且還與右邊多個節點之間有聯系，因此應該是兩個社團之間的共有部分。而節點31雖然只與左邊社團中的一個節點相連，但是起到了橋梁作用，兩個社團可以通過節點31進行交流，所以節點31也應該是兩個社團之間的重疊節點。

圖3　空手道俱樂部重疊社團劃分結果

圖4　海豚網重疊社團劃分結果

Lusseau等[17]對生活在新西蘭神奇海灣中的一群海豚做了跟蹤調查，發現它們之間同樣存在著社團結構。圖4是利用本文所提出的鄰域重疊社團結構劃分算法對海豚網絡進行鄰域社團劃分所得結果。紅色節點和綠色節點分別屬于不同的社團，中間的藍色節點是兩個社團之間的重疊節點。節點2,29,31不但與左邊社團中多個節點相連，而且還與右邊多個節點之間存在關系，因此也應該是兩個社團之間的共有部分。節點8,58雖然只與右邊社團中的一個節點相連，但是這兩個節點同樣也起到了橋梁作用，使得左右兩個社團可以通過節點8,58進行交流，所以節點8,58也應該是兩個社團之間的重疊節點。

在空手道俱樂部網和海豚網中，利用本文提出的鄰域重疊社團結構劃分算法，得到的社團結構與實際情況相一致，進一步證實了算法的準確性。此外，本文還將鄰域重疊社團結構劃分算法運用到科學家合作網中[8]。圖5是對科學家合作網進行鄰域社團劃分所得結果。

圖5　科學家合作網重疊社團劃分結果

數據集名稱節點數邊數運行時間/sSBMF9220.004Karateclub34780.006Dolphins621590.010Sciencenet158927420.388

在圖5中，科學家合作網中的最大連通網被劃分成8個社團，不同顏色的團簇代表了一個社團結構，社團之間的紅色的節點表示的是重疊節點。從圖5可以看出，社團內部的節點之間聯系非常緊密，而社團之間的連接卻相對比較稀疏。社團間的重疊節點大多是度值比較大的節點或者是與度值較大的重疊節點關系緊密的小度值節點。圖5中的網絡拓撲結構合理地反映了科學家之間的合作模式：相同研究方向的科學家之間的合作非常緊密，具有明顯的聚簇現象；同時不同研究方向的科學家之間也存在著學術交流，但這往往發生在學科代表的身上以及他的研究團隊中。比如，在復雜網絡領域，Mark Newman是一名偉大的物理學教授，其團隊主要從事網絡拓撲結構和網絡功能的研究。由于Newman團隊取得的成績非常突出，導致很多領域的科學家都會與他的團隊進行合作，此時他的團隊就成為不同研究領域的社團之間的重疊節點。在圖5中，Newman及其團隊對應的是藍色社團中的度值較大的紅色節點以及度值較小的紅色節點。

由于本文采用了堆數據結構，從計算科學的角度優化了社團結構的劃分，極大程度上降低了算法復雜度，加快了社團結構的劃分，表1是程序在不同的數據集中的運行時間。

從表1可以看到，本文所提出的社團劃分算法可以快速地實現鄰域社團結構劃分，當網絡規模增大時，程序耗時仍然較低。因為本文所提出的社團劃分算法的算法復雜度近似線性，所以其適用于大規模復雜網絡，可以快速實現網絡的鄰域社團結構挖掘。

5結語

本文提出了一種復雜度近似線性的鄰域重疊社團結構劃分算法，可以準確、快速地實現網絡社團劃分以及重疊節點挖掘。基于模塊度Q，本文采用堆的數據結構，快速地實現了非鄰域社團劃分，利用得到的非鄰域社團構造初始社團矩陣，逐一分析網絡中的連邊，結合劃分密度D，準確地實現了社團間重疊節點的挖掘。最后，本文利用模擬網絡和經典的實證網絡進一步證實了算法的高效性、準確性。

參考文獻:

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

[2]Adamic L A, Adar E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3): 211-230.

[3]Holme P, Huss M, Jeong H. Subnetwork hierarchies of biochemical pathways[J]. Bioinformatics, 2003, 19(4): 532-538.

[4]Newman M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256.

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

[6]Flake G W, Lawrence S, Giles C L, et al. Self-organization and identification of web communities[J]. Computer, 2002, 35(3): 66-70.

[7]Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal, 1970, 49(2): 291-307.

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

[9]Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6): 066111.

[10] Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3): 036104.

[11] Zhang X S, Li Z, Wang R S, et al. A combinatorial model and algorithm for globally searching community structure in complex networks[J]. Journal of Combinatorial Optimization, 2012, 23(4): 425-442.

[12] Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.

[13] 楊歡，韓定定. 完全子圖的鄰域重疊社團結構探測[J]. 現代電子技術, 2012, 35(18):122-126.

Yang H, Han D D. Improvement of neighbourhood overlapping community detection algorithm based on complete subgraph[J]. Modern Electronics Technique, 2012, 35(18):122-126.

[14] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multiscale complexity in networks, 2010[J]. Nature, 466: 761.

[15] Zhang Z Y, Wang Y, Ahn Y Y. Overlapping community detection in complex networks using symmetric binary matrix factorization[J]. Physical Review E, 2013, 87(6): 062803.

[16] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977: 452-473.

[17] Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology, 2003, 54(4): 396-405.

(責任編輯李進)

Finding Overlapping Community in Network by Using Modularity and Partition Density

REN Chenglei, HAN Dingding, PU Peng, ZHANG Jiacheng

(School of Information Science and Technology, East China Normal University, Shanghai 200241, China)

Abstract：The algorithms of detecting community in complex networks now have lots of disadvantages such as high complexity and ignorance of accurate overlapping nodes. This paper proposes a highly efficient, rapid and accurate community detection algorithm. Based on greedy algorithm, the community is divided by establishing the modularity matrix and adopting the data structure. Considering the edges between local communities, the overlapping community structure is accurately dug by computing the partition density. We evaluate our methods using both synthetic benchmarks and real-world networks, demonstrating the effectiveness of our approach. Our method runs in essentially linear time.

Key words：community mining; overlapping community; modularity; partition density; time complexity

文章編號：16723813(2016)01010206;

DOI:10.13306/j.1672-3813.2016.01.011

收稿日期：2015-07-09

作者簡介：任成磊(1990-)，男，山東煙臺人，碩士研究生，主要研究方向為智能計算、復雜網絡。

中圖分類號：TP393.02

文獻標識碼：A