圖重構下大規模網絡的社團檢測算法

摘 要：對大型復雜網絡進行高質量的社團檢測通常依賴圖的拓撲結構來劃分節點集，然而現實世界的網絡通常帶有嘈雜且與集群無關的連接，這些鏈接可能會導致模型將來自不同集群的節點劃分在一起。為此，提出了基于圖重構的社團檢測算法（graph reconstruction based community detection，GRCD），該方法能夠處理大規模復雜網絡的社團檢測。首先，刪除社團之間的相互連接的邊來重新構建原始圖的社團結構；然后，將網絡視為一個社交系統，旨在以更直觀的方式揭示社團；提出了一種高效的社團檢測策略，即基于話語權的社團組織生成策略；最后，在不同規模數據集上進行實驗。實驗結果表明，GRCD算法不僅能夠處理大規模網絡，而且在保持較高穩定性的同時，其社團劃分的質量對比現有的幾種基準算法都有很強的競爭力。

關鍵詞：大規模；復雜網絡；圖重構；社團檢測

中圖分類號：TP301.6 文獻標志碼：A 文章編號：1001-3695（2023）02-026-0470-06

doi： 10.19734/j.issn.1001-3695.2022.07.0331

Community detection algorithm for large-scale networks by graph reconstruction

Chen Yanbinga，b， Zhang Yinglongb

（a. School of Computer， b. College of Physics amp; Information Engineering， Minnan Normal University， Zhangzhou Fujian 363000， China）

Abstract：High-quality community detection for large-scale complex networks usually depends on the topology of the graph， which used to divide the node set. However， real-world networks usually have noisy and cluster-independent links， which may cause the model to divide the nodes from different clusters together. This paper proposed a algorithm called graph reconstruction based community detection（GRCD）. This method could handle community detection in large-scale complex networks. GRCD firstly deleted the connected edges between communities to reconstruct the community structure of the original graph. Subsequently， GRCD regarded the network as a social system， aiming to reveal the community in a more intuitive way. This paper proposed an efficient community detection strategy： a community organization generation strategy based on discourse power. Extensive experiments were performed on datasets of different sizes. The results show that GRCD can not only deal with large-scale networks， but also has strong competitiveness in the quality of its community division compared with several existing benchmark algorithms while maintaining high stability.

Key words：large-scale; complex network; graph reconstruction; community detection

0 引言

隨著通信技術和移動終端的快速發展，人們對彼此互動的方式發生了巨大的改變，這導致了復雜網絡的規模也在呈指數增長。社團結構作為復雜網絡最重要的屬性之一［1］，它通常代表著一個具有相似興趣愛好、價值觀、生活習慣或是關系密切的用戶群體。由此，揭示復雜網絡的底層社團結構來劃分不同的群體是一項重要且極具價值的任務。

近年來，學術界和工業界的研究者在復雜網絡的分析上作出了重大貢獻。然而，隨著數據的積累，復雜網絡的規模逐漸擴大且變得嘈雜［2］，這就導致了依賴于拓撲結構的傳統社團檢測算法在處理大規模復雜網絡時所面臨的時間復雜度以及準確度的問題。也就是說，大多數現有算法無法擴展應用到當今復雜網絡的龐大規模。因此，如何過濾現實世界中嘈雜的網絡結構以及提高社團檢測的效率是一個關鍵問題。

為了揭示網絡結構，文獻［3］提出了一種稱為模塊化（modularity）函數的定量標準，用于描述社團結構的質量。該函數對社團結構進行了清晰的定義，并在實際應用中取得了巨大成功，因此逐漸被業界所接受。同時，采用模塊化函數作為優化函數的方法已成為社團檢測的主流之一，例如fast-greedy［4］、Louvain［5］、combo［6］以及光譜分析方法［7，8］。然而，這些基于模塊化函數的方法可能無法識別小于一定大小的社團結構，這被稱為分辨率限制問題［9］。為了應對這一問題，文獻［10］對模塊化函數做了一些修改。此外，標簽傳播算法（label propagation algorithm，LPA）［11］也逐漸成為一種競爭方法，引起了許多學者的關注。標簽傳播的啟發式規則是指社團結構網絡中的任何節點都應該與其大多數鄰居處于同一個社團中。LPA最大的優點是線性的計算復雜度，但其不確定性和隨機性比較突出，在不同的實驗中可能會產生不同的社團結構。最近，文獻［12～14］提出了拓展LPA算法來優化性能。然而，這些擴展算法并不能完全解決隨機性問題，甚至大大提高了算法的復雜度。近年來，有學者通過尋找社團核心位置來發現社團結構［15］，核心節點擴展算法（core expand algorithm，CE）［16］是其中之一。然而，由于其完全依賴原始拓撲結構來擴展社團，可能會導致正確率較低。作為無監督學習中的一種有效方法，非負矩陣分解（nonnegative matrix factorization，NMF）［17］也逐漸被應用于分析社團結構（A-NMF）［18］。雖然基于NMF的算法具有良好的可解釋性，但通常需要網絡中社團數量作為先驗知識，然而社團數量一般是未知的。在過去的幾年里，圖神經網絡［19］在處理復雜網絡中的節點分類和連接預測等一系列表示學習相關任務方面表現出了驚人的能力，但由于其參數量過大，在面對大規模的網絡需要大量的計算資源，到今天仍然是一個無法解決的難題。

值得注意的是，上述算法在面對大規模網絡時，其效率無法得到保證。為了應對這一挑戰，文獻［20～23］進行了大量的研究，這些方法可以分為并行社團檢測算法和局部社團發現算法。第一類方法通過構造不同的分區并從隨機選擇的節點貪婪地擴展社團結構。然而，在隨機地通過原始圖結構來傳播節點的過程中，并不是所有的邊都能夠對社團檢測起到積極作用。因此有必要提出一種在不降低甚至能提高社團檢測精確度的前提下，通過重構圖結構來縮減網絡規模的一種新的社團檢測方法?；谏鲜瞿康?，本文針對無屬性無向圖提出了一種基于圖重構的大規模復雜網絡社團檢測（GRCD）算法。首先，定義一個相似度指標來衡量原始圖中所有節點對的相似度，通過刪除社團之間存在且相似度低的邊來縮減網絡規模；然后，本文提出了一種基于話語權的社團檢測方法來表征網絡社團結構；在衡量個人的話語權和影響力的同時，啟發式的擴展社團。本文工作的主要貢獻如下：

a）提出了一種簡單、高效、無損的復雜網絡重構方法。

b）基于話語權的社團組織生成策略，提出了一種可以自動檢測社團數量和尋找初始社團高話語權節點的社團檢測算法。

c）在三種不同規模的LFR基準網絡數據集和六個真實數據集上的實驗表明，GRCD相比多個基準模型，在運行時間和模型精確度上都有很強的競爭力。

1 相關研究

同一社團中的節點之間的連接比其他社團中的更緊密，這是復雜網絡的一個重要特性，即社團結構。最近，學者提出了許多算法來檢測潛在的網絡社團結構，如基于模塊度最大化的方法、基于標簽傳播的方法、基于非負矩陣分解的方法、基于圖神經網絡的方法等。

1.1 模塊度最大化

社團檢測的開創性工作是文獻［24］提出的GN算法，該算法根據圖的邊介數中心性，通過不斷迭代并消除邊介數最高的邊。許多受GN啟發的相關工作被提出，特別是文獻［3］提出了一種稱為模塊性函數的定量標準，用于描述社團結構的質量，該函數給出了社團結構的清晰定義，并在實際應用中取得了巨大成功，因此已逐漸被接受。fast-greedy［4］是一種具有代表性的聚合算法，它以模塊化指數作為算法劃分的目標函數，選擇最優模塊化值對應的結構作為最終的社團劃分結果。文獻［25］將最大化模塊化函數的NP難問題轉換為非凸優化問題，然后通過凸函數差分規劃進行求解。

1.2 標簽傳播

標簽傳播算法（LPA）由Raghavan 等人［11］提出，其采用簡單的標簽傳播來識別社團結構。標簽傳播方法的啟發式規則是一個社團結構網絡中的節點應該與他們的大多數鄰居處在同一個社團中。這種啟發式算法只使用網絡結構作為輸入，沒有設置自由參數。標簽傳播算法為每個節點分配唯一標簽，并且根據其鄰居不斷更新每個節點的標簽，直到沒有標簽被更改。其最大的優點是線性計算復雜度，但它的不確定性和隨機性突出。LPAMNI［26］為了解決這種不確定性問題，在節點傳播標簽的同時考慮了最大化模塊度的策略。

1.3 非負矩陣分解

非負矩陣分解（NMF）［17］也逐漸應用于分析社團結構，該方法將非負矩陣M近似為兩個非負矩陣W和H的低秩積。A-NMF［18］提出了一種簡單的方法來顯著加速矩陣分解過程，基于對每次迭代所需計算成本的仔細分析，同時保持它們的收斂特性。Bigclam［27］使用社團隸屬關系圖模型來學習表示節點社團成員資格的潛在向量。

1.4 圖神經網絡

圖神經網絡在表示學習中具有優異的表現能力，近年來被許多工作用來劃分社團。GEMESC［28］是一種通過節點序列采樣的模型，它在學習節點嵌入的同時劃分社團。Zhang等人［29］提出了 SEAL 算法來使用生成對抗網絡檢測社團。剪影社區檢測（silhouette community detection，SCD）［30］是一種嵌入式聚類方法，它通過優化等值線測量來揭示社團結構，從其鄰域中提取節點的真實值表示。

2 圖重構

圖結構是傳統圖分析方法的重要信息來源，因此圖結構的好壞可以直接影響社團檢測任務。然而現實中的圖或多或少都含有一些嘈雜的邊（社團間的邊），這些邊有可能會誤導社團檢測模型，將來自不同社團之間的節點劃分在一起。本章將針對上述問題提出一種新穎的圖重構方法。首先，通過理論依據來證明圖重構的可行性；然后，針對圖拓撲結構的特性，預測社團之間的邊并將其從原始圖中刪除，以達到重建圖結構的目的。

2.1 理論依據

傳統的社團檢測算法通常利用拓撲特性來識別社團結構，但是現實世界的網絡通常含有嘈雜的邊。文獻［31］在進行大量的實驗后，證明了在有真實標簽的情況下通過刪除社團間的邊對傳統社團檢測算法的性能和效率有明顯的提升。由此，可以對一個原始的無向圖G=（V，E）通過刪除社團間的邊后重新構建成另一個圖G′，在壓縮網絡規模的同時能更清楚地揭示社團結構，那么就可以在重構圖G′下進行社團檢測來提高效率和準確率。

2.2 圖重構的設計

2.2.1 預測社團之間的邊

在進行圖重構時，應該能夠從原始結構中識別出社團間的邊，如果真實社團標簽可用，則可以很容易識別出社團間的邊，但是這在社團檢測時并不可取。那么該如何在完全沒有真實標簽的網絡中去預測社團間的邊？一個很好的經驗是通過計算節點對之間的結構相似度。社團內部的節點之間相互連接密集，但是社團邊界的節點之間相互連接稀疏，因此社團間的節點對之間存在相互連接的邊，它們的相似度也應該較低。根據節點之間的相似度可以很好地反映社團之間的邊，由此本文采用文獻［32］的相似度衡量方法來捕捉節點之間的相似度sim。

其中：sim（u，v）為節點u和v的相似度；Ng（u）為節點u的鄰居節點集；p為節點i和j直接或間接相連的路徑之一；|p|為p的長度，從1增長到α。參數α用于控制測量sim的最大路徑長度，在sim的準確性和時間復雜度之間存在權衡，α越大表示考慮更多的拓撲信息來衡量節點之間的相似性，伴隨準確率的提高也會帶來更高的復雜度。文獻［32］提出將α的值設置為3可以更精確地衡量相似度的同時也能保持較低的時間復雜度。圖1是一個簡單圖的圖重構過程，每一對節點都根據式（1）（2）呈現了它們之間的相似度，可以注意到節點對（1，8）和（3，9）都表現出了低于社團內部的所有相互連接的邊，而它們也正是社團之間的邊。

2.2.2 決定刪除邊的數量

相似度作為一種衡量指標能夠有效預測出社團間的邊，接下來，本文提出一個算子δ，該算子決定了在原始圖G中刪除的邊的數量。具體來說，選擇低相似度且存在邊的節點對作為社團間邊。在計算相似度矩陣后，根據升序排序成對相似度序列，于是有

然后，通過設置一個算子δ（0lt;δlt;1）來判定節點對的類型是否為社團間的邊，節點對（i， j）在相似度序列sQ中的排名用rij表示，因此預測節點對（i， j）的類型為社團間邊的準則如下：

其中：|sQ|表示sQ的長度，通過對原始圖G刪除社團間的邊來獲得重構圖G′。節點對之間的相似度越低，則該邊作為社團間邊的概率就越高。然而，在沒有真實標簽的情況下，δ的值要設置為多少才能在不破壞原始圖結構的情況下提高社團檢測的準確率，需要進行試驗。因此，對δ的分析會在4.2節進行詳細闡述。

3 基于話語權的社團組織生成策略

獲得重構圖G′的目的是在G′上進行社團檢測。本文提出的社團檢測算法是基于真實社會中群落的生成規律。在真實世界中，一般是最有話語權的人（在圖中表示為度數高的節點）建立組織然后號召大家加入自己的組織，此時周圍的人（在圖中表示為鄰居節點）就會受其影響，紛紛加入該組織；同時，又有一個話語權較大的人想加入組織，但是看到這些已經建立的組織不適合自己（在圖中表示為節點與社團的距離較遠），于是就自己建立一個組織，然后號召周圍的人加入自己的組織；最后，有一個人想加入組織且周圍的有兩個甚至更多的組織適合自己，于是這個人就在周圍選一個對自己影響力最大的人并加入這個人所屬的組織（影響力傳播效應）。在本文中一個人的話語權表示為p（u），一個人v對于另一個人u的影響力表示為NNIv（u）。

3.1 高話語權節點的選擇

高話語權的節點擁有優先建立社團或加入社團的權力，這是因為在現實生活中高話語權的人的行為往往會影響周圍其他話語權比他低的人的行為。在圖中節點度數高的節點往往很大概率就是高話語權節點。本文用節點的度數作為衡量指標，節點的度數越高，其作為高話語權節點的概率也隨之提高。節點的話語權表示如下：

其中：du為節點u的度數。在現實生活中，當一個人周圍有多個人關注他的時候，就表明這個人的話語權高，那么這個人就要首先作出表率（創建社團或加入某個社團）來影響周圍的人所做的決定。于是，根據節點話語權對所有節點進行排序：

高話語權節點擁有創建社團并且擴展社團的權力，在本文中規定了節點度數越高的節點其成為高話語權節點的概率就越大，但并不是所有的度數高的節點都能成為高話語權節點，還必須滿足一個條件，就是該節點周圍沒有加入社團的節點。由于本文是按照節點話語權降序遍歷節點，所以并不存在當一個節點想加入社團時其鄰居存在話語權比該節點高且沒有加入社團的節點。

3.2 社團組織的建立及其傳播

本文對所有節點規定三種行為：a）節點周圍無隸屬社團時，以自身創建社團；b）節點的直接鄰居有且只隸屬一個社團時，加入該社團；c）節點的直接鄰居隸屬不同社團時，根據其鄰居節點對其的影響力加入影響力最高的鄰居節點所屬的社團。

在現實生活中，每個人都有自己的利益和特點，這就導致在擁有相關利益的人之間相互影響進入同一個社團。例如，A和B都喜歡運動，B和C都喜歡音樂。與運動相比，B更喜歡音樂。很明顯，A和B之間的相似性不如B和C之間的相似性大，因此B和C會用音樂而不是運動來吸引對方。由于個體之間的影響力不僅與相似性有關，還與個體自身的話語權有關，所以將個體之間的影響力定義為個體的話語權與個體之間的相似性的乘積。于是，節點v對u的影響力（neighbor node influence）定義如下：

遍歷vQ的所有節點，若節點i的鄰居都不隸屬于某個社團時，則該節點i便以自身的id建立社團ci并歸屬于ci；若節點i的鄰居有且只有一個節點隸屬于社團，則將節點i加入到其所屬的社團；若節點i的鄰居已經隸屬于社團且不止一個，則根據其鄰居節點對其的影響力加入影響力最高的鄰居節點所屬的社團。這種方式避免了節點話語權較高的兩個成對節點劃分到不同的社團。

本文的社團檢測算法與傳統基于核心節點擴展的算法［16］不同總結如下：傳統的基于核心節點擴展的算法首先選擇一組初始社團節點，然后通過節點擴展將社團結果擴展至整個社團結構，本文的高話語權節點是在遍歷vQ時確定的，并不是在一開始就確定下來；傳統基于標簽傳播的算法［11，25］通過每次迭代更新所有節點對鄰居節點的隸屬度的方式傳播社團結果。本文的影響力只考慮鄰居節點中節點話語權比該節點高的節點，且只需遍歷一次就可確定社團結果。

為了更好地理解本文的社團檢測算法以及如何使用式（7）來計算節點之間的影響力，本文用一個實例網絡來說明。如圖2所示，這個網絡由14個節點組成，這些節點分為兩個社團。其中，填充顏色的節點表示高話語權節點，其余節點是等待加入組織的節點。所有節點話語權按降序排序為（10，2，3，4，5，8，11，1，12，9，13，6，7，14），首先按照該順序遍歷節點，由于v10的節點話語權最大，于是v10便屬于一個新的社團c10。接下來由于v2和v10之間不存在邊，所以v2也屬于新的社團c2。然后是v3，由于v3和v2存在邊，于是將v3歸屬于v2所屬的社團，依此類推直至傳播到整個社團結構。最后考慮一個節點的鄰居存在多個社團隸屬的情況，由于在圖重構下，社團間的節點已被刪除無須考慮，但是在真實網絡中難免會出現這種情況，所以現在假設節點對（1，8）間存在邊，然后通過節點影響力考慮v1的隸屬社團。由式（7）可計算出v1的直接鄰居節點對v1的影響力，即，NNI8（1）=0.81，NNI3（1）=0.94，NNI2（1）=0.88。對比其影響力的大小可知NNI3（1）gt;NNI2（1）gt;NNI8（1），于是便可將v1歸屬于v3所在的社團。

3.3 復雜度分析

假設復雜網絡中有n個節點、m條邊且節點的平均度數為k。GRCD算法的時間復雜度主要分為初始化、重構圖結構和節點擴展部分三個部分。GRCD算法在初始化部分計算節點p（u）值時根據的是節點度，復雜度為O（n）；計算相似度時參考節點對的鄰居，復雜度為O（kα－1×m）；計算節點影響力時，復雜度為O（m）。在圖重構部分，根據相似度低的邊來重構圖，復雜度為O（δ×m）。最后根據節點p（u）值和節點影響力來選擇高話語權節點和傳播社團，復雜度為O（nd）。因此，GRCD的時間復雜度為O（n+kα－1×m+m+δ×m+nd）。GRCD

4 實驗

數值實驗在具備Intel i7處理器、8 GB內存和 Windows 10操作系統的電腦上運行，在Python 3.6環境下編程計算。

4.1 實驗數據和評價方法

為了充分評估GRCD算法的性能，使用了兩種數據集。一種是真實世界的復雜網絡數據集，然而對于許多真實的網絡，其社團結構通常是未知的，這導致無法評估GRCD算法的真實效果。因此，本文還在仿真網絡上對算法進行實驗，這些仿真網絡由LFR基準網絡程序生成［33］，它們的真實社團結構是已知的。

4.1.1 仿真網絡數據和評價方法

LFR在生成仿真網絡的同時也產生了社團劃分結果，以方便算法使用其生成的仿真網絡數據集進行社團劃分的結果與已知社團進行對比。仿真網絡數據集的詳細信息如表1所示，必要的參數描述見表2。衡量網絡中檢測到社團的質量是一項挑戰，因為不同的衡量標準可能導致不同質量的社團。根據特定網絡的基本真相社團是否已知，所使用的質量度量是不同的。本文將NMI ［34］用做對仿真網絡這種已知社團的數據集進行檢測社團質量的評估度量。相對于其他的評價指標，它的魯棒性更強。NMI具體信息詳見式（8）。

NMI=∑ki=1 ∑k′j=1ni， jlogn×ni， jnci×npj∑ki=1nci×logncin×∑k′j=1npj×lognpjn（8）

其中：C={C1，C2，…，Ck}和P={P1，P2，…，Pk′}分別為由社團檢測算法社團集合和真實標簽所分配的社團集合；k和k′分別為社團C和P的數量；ni， j為社團Ci和真實社團Pj的公共節點數；nci為社團Ci的節點數；npj為社團Pj中的節點數。NMI的取值為0～1，NMI的值越高表示劃分的社團質量越好。

4.1.2 真實網絡數據和評價方法

本文也在社團結構未知的六個真實網絡（karte［35］、dolphin［36］、football［24］、DeezerEurope（Deezer）［37］、DBLP［38］、Com-YouTube（YouTube）［38］）中做了測試。它們的社團規模和拓撲結構都不同，應該可以很好地衡量算法的優劣性。真實網絡數據集相關統計如表3所示。由于很多時候并不知道真實網絡的社團劃分，所以很難有基于真實信息的評價標準。而Newman等人［3］提出的用于評價社團檢測算法在真實數據集的社團檢測質量的函數（模塊度）得到廣泛認可，詳見式（9）。

其中：m為網絡中邊的總數；A為鄰接矩陣，如果節點i和j存在邊，則Aij=1，反之，Aij=0；Ci為節點i所屬的社團，如果節點i和j所屬的社團一樣，則δ（Ci，Cj）=1，否則，δ（Ci，Cj）=0；di為節點i的度數；Q的取值為0～1，Q的值越高表示劃分的社團質量越好。

4.2 參數選擇

GRCD算法通過設置δ（0lt;δlt;1）的大小來確定要刪除原始圖G中邊的數量，本文在生成網絡s1、s2兩種數據集的不同mu值上對其進行測試GRCD算法的表現。圖3（a）（c）（e）描述了不同δ下NMI值的變化，圖3（b）（d）（f）描述了不同δ下運行時間的變化趨勢?？梢钥闯觯诖蟛糠智闆r下δ=0.2時，社團檢測的NMI值相對較高，這是由于社團內邊的數量往往要遠大于社團間的邊。若δ過小則社團結構不清晰，若δ過大則會裁剪掉社團內的邊從而導致正確率下降。GRCD算法的運行時間隨著δ的增大呈現下降趨勢，雖然δ越大，越能提高GRCD算法的運行效率，但是為了平衡算法的準確率，本文的后續實驗將δ設置為0.2。

4.3 對比算法

為了評估GRCD算法的性能，本實驗將GRCD算法與七種具有代表性的社團檢測算法進行了比較。本節將簡要描述這些算法以及對應的參數設置。

LPA［11］利用樣本之間的關系建立完整的圖模型。其基本思想是利用標記節點的標記信息來預測未標記節點的標記信息。該算法實現簡單，執行時間成本較低，但每次運行的結果不穩定。

Louvain［5］是一種著名的多級模塊化優化社團檢測算法，支持分層社團檢測，與Newman提出的算法［3］相比，該算法的時間復雜度較低。

combo［6］是一種基于模塊化函數的通用社團檢測的優化技術，但是由于內存限制，其當前的適用性限制在大約3萬個節點。

CE［16］是為了克服模塊化優化技術的一些局限性，特別是大密集群的分裂和過擬合，而提出的一種基于核心節點擴展的社團檢測算法，并且保持模塊化得分盡可能接近最大值。

A-NMF［18］在NMF［17］的基礎上更好地利用了算法中最昂貴的部分，通過重復（受保護的）固定次數的迭代中較便宜的部分，并保留了原始算法的收斂特性。

LPAMNI［26］ 通過將模塊度函數和節點重要性與原始 LPA［11］相結合，解決了LPA的隨機性問題。

SCD［30］是一種嵌入式聚類方法，它通過優化輪廓測量來揭示社團結構，特別是從其鄰域中提取節點的真實值表示。

本文將LPA、LPAMNI算法的最大迭代次數設置為100。combo、CE、Louvain都能夠自動選擇社團的數量。此外，對于不能夠自動選擇社團數量的A-NMF和SCD來說，將該參數設置為真實社團數量。

4.4 實驗分析

4.4.1 仿真網絡數據集上的實驗

在五種不同mu值的仿真網絡（表1）上進行實驗，用來評估GRCD算法（以下簡稱GRCD）的性能。圖4描述了不同mu值下的三種仿真網絡中不同算法的NMI。如圖4所示，GRCD在大多數網絡中得到了最高的NMI，尤其是在圖4（c）中，在節點數量為5 000的情況下，GRCD都取得了最優的分數。圖4（d）的是幾個算法在節點數量不同的情況下所消耗的時間， 可以看到，GRCD在時間成本上也低于參與對比的其他算法。LPAMNI相對與LPA算法展示了更高的穩定性，這是由于LPAMNI在標簽傳播過程中以模塊度更高的方向傳播。SCD根據節點對提取節點的嵌入表示，由于每次迭代都要更新參數所以需要大量的計算成本。

4.4.2 真實網絡數據集上的實驗

對于那些沒有真實社團劃分的復雜網絡，本文使用模塊度Q來衡量社團檢測結果的質量。比較模塊度Q的結果如表4所示。在該表中，如果算法的運行時間大于8 h，將其終止并將結果設置為“NA”。在模塊度指標方面，得到以下觀察結果：與其他算法相比，GRCD性能更好，并在四個網絡上獲得了最優結果。此外，combo在其他兩個網絡上獲得了最好的結果。這主要是因為combo的每次迭代是通過計算模塊度來劃分網絡的，因為本文算法不是專門為優化模塊化值而設計的，同時由于每次迭代都需要計算模塊度，所以時間成本大大提高，導致在大型網絡的耗時太長。GRCD獲得的模塊度幾乎總是優于其他算法，在表5中，GRCD運行所占用的時間在每個數據集都是最小的。因此，可以得出結論，GRCD是一種識別社團結構的有效且具有競爭力的方法。

5 結束語

社團檢測是一個具有挑戰性的問題，尤其是在網絡規模較大的復雜網絡分析中。本文提出的算法旨在通過縮減網絡規模來提高復雜網絡內的社團檢測效率和準確率。該算法包括圖重構、高話語權節點的選擇和社團組織的建立及其傳播三個步驟。首先，刪除社團之間相互連接的邊來重新構建原始圖的社團結構。隨后，提出了一種基于話語權的社團組織生成策略，該策略的核心思想是將網絡視為一個社會系統，網絡中的個體因其強大的話語權建立社團，社團里的成員又會因自身的影響力而吸引其他個體形成大群體。隨著時間的推移，所有個體最終會被吸引到不同的社團中，形成一個穩定的社團結構。實驗結果表明，該算法在提取社團結構、效率和有效性方面均取得了很好的效果。不過所提出的基于圖重構的算法僅適用于無屬性網絡，如何將圖重構策略拓展到屬性圖上的社團檢測是未來的研究重點。

參考文獻：

［1］蔣忠元，陳賢宇，馬建峰. 社交網絡中的社團隱私研究綜述［J］. 網絡與信息安全學報，2021，7（2）： 10-21. （Jiang Zhongyuan，Chen Xianyu，Ma Jianfeng. Survey of community privacy in social network［J］. Chinese Journal of Network and Information Secu-rity，2021，7（2）： 10-21.）

［2］李忠，靳小龍，莊傳志，等. 面向圖的異常檢測研究綜述［J］. 軟件學報，2021，32（1）： 167-193. （Li Zhong，Jin Xiaolong，Zhuang Chuanzhi，et al. Overview on graph based anomaly detection［J］. Journal of Software，2021，32（1）： 167-193.）

［3］Newman M，Girvan M. Finding and evaluating community structure in networks［J］. Physical Review E，2004，2004（2）： article ID 026113.

［4］Clauset A，Newman M，Moore C. Finding community structure in very large networks［J］. Physical Review E，2004，2004（6）： article ID 066111.

［5］Blondel V D，Guillaume J L，Lambiotte R. Fast unfolding of communities in large networks［J］. Journal of Statistical Mechanics： Theory and Experiment，2008，2008（10）： P10008.

［6］Sobolevsky S，Campari R，Belyi A，et al. General optimization technique for high-quality community detection in complex networks［J］. Physical Review E，2014，90（1）： 1103-1111.

［7］Gui Chun，Zhang Ruisheng，Hu Rongjing，et al. Overlapping communities detection based on spectral analysis of line graphs［J］. Physica A：Statistical Mechanics and Its Applications，2018，498（1）：50-65.

［8］Zhang Xiao，Newman M E J. Multiway spectral community detection in networks［J］. Physical Review E，2015，92（5）： article ID 052808.

［9］Fortunato S，Barthelemy M. Resolution limit in community detection［J］. Proceedings of the National Academy of Sciences，2007，104（1）： 36-41.

［10］Chen Mingming，Kuzmin K，Szymanski B K. Community detection via maximization of modularity and its variants［J］. IEEE Trans on Computational Social Systems，2014，1（1）： 46-65.

［11］Raghavan U N，Albert R，Kumara S. Near linear time algorithm to detect community structures in large-scale networks［J］. Physical Review E，2007，2007（76）： 036106.

［12］Gui Qiong，Deng Rui，Xue Pengfei，et al. A community discovery algorithm based on boundary nodes and label propagation［J］. Pattern Recognition Letters，2018，109（1）： 103-109.

［13］Ma Tianren，Xia Zhengyou. An improved label propagation algorithm based on node importance and random walk for community detection［J］. Modern Physics Letters B，2017，31（14）：article ID 1750162.

［14］Xing Yan，Meng Fanrong，Zhou Yong，et al. A node influence based label propagation algorithm for community detection in networks［J］. The Scientific World Journal，2014，2014（1）： article ID 627581.

［15］張應龍，夏學文，徐星，等. 面向標簽傳播算法的社團檢測研究現狀及展望［J］. 小型微型計算機系統，2021，42（5）： 1093-1102. （Zhang Yinglong，Xia Xuewen，Xu Xing，et al. Review on label propa-gation algorithms for community detection［J］. Journal of Chinese Computer Systems，2021，42（5）： 1093-1102.）

［16］Choumane A，Awada A，Harkous A. Core expansion： a new community detection algorithm based on neighborhood overlap［J］. Social Network Analysis and Mining，2020，10（1）： article No. 30.

［17］Lee D D，Seung H S. Learning the parts of objects by non-negative matrix factorization［J］. Nature，1999，401（6755）： 788-791.

［18］Gillis N，Glineur F. Accelerated multiplicative updates and hierarchical ALS algorithms for nonnegative matrix factorization［J］. Neural Computation，2012，24（4）： 1085-1105.

［19］Hamilton W L，Ying R，Leskovec J. Inductive representation learning on large graphs［C］// Proc of the 31st International Conference on Neural Information Processing Systems. New York： ACM Press，2017： 1025-1035.

［20］Bai Liang，Cheng Xueqi，Liang Jiye，et al. Fast graph clustering with a new description model for community detection［J］. Information Sciences，2017，388（2）： 37-47.

［21］Moon S，Lee J G，Kang M，et al. Parallel community detection on large graphs with MapReduce and GraphChi［J］. Data amp; Knowledge Engineering，2016，104（1）： 17-31.

［22］Sharma R，Oliveira S. Community detection algorithm for big social networks using hybrid architecture［J］. Big Data Research，2017，10（1）： 44-52.

［23］Staudt C L，Meyerhenke H. Engineering parallel algorithms for community detection in massive networks［J］. IEEE Trans on Parallel and Distributed Systems，2015，27（1）： 171-184.

［24］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.

［25］Yuan Quan，Liu Binghui. Community detection via an efficient nonconvex optimization approach based on modularity［J］. Computational Statistics amp; Data Analysis，2021，157： article ID 107163.

［26］Li Huan，Zhang Ruisheng，Zhao Zhili，et al. LPA-MNI： an improved label propagation algorithm based on modularity and node importance for community detection［J］. Entropy，2021，23（5）： 497.

［27］Yang J，Leskovec J. Overlapping community detection at scale： a nonnegative matrix factorization approach［C］// Proc of the 6th ACM International Conference on Web Search and Data Mining. New York： ACM Press，2013： 587-596.

［28］Rozemberczki B，Davies R，Sarkar R，et al. GEMSEC： graph embedding with self clustering［C］// Proc of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Pisca-taway，NJ：IEEE Press，2019： 65-72.

［29］Zhang Yao，Xiong Yun，Ye Yun，et al. SEAL： learning heuristics for community detection with generative adversarial networks［C］// Proc of the 26th ACM SIGKDD International Conference on Knowledge Discovery amp; Data Mining. New York： ACM Press，2020： 1103-1113.

［30］krlj B，Kralj J，Lavra N. Embedding-based Silhouette community detection［J］. Machine Learning，2020，109（11）： 2161-2193.

［31］Kang Y，Lee J S，Shin W Y，et al. CR-graph： community reinforcement for accurate community detection［C］// Proc of the 29th ACM International Conference on Information amp; Knowledge Management. New York： ACM Press，2020： 2077-2080.

［32］Lyu Meilian，Zhang Zhenlin，Qu Zhile，et al. LPANNI： overlapping community detection using label propagation in large-scale complex networks［J］. IEEE Trans on Knowledge and Data Engineering，2018，31（9）： 1736-1749.

［33］Lancichinetti A，Fortunato S，Radicchi F. Benchmark graphs for testing community detection algorithms［J］. Physical Review E，2008，78（4）： 46-51.

［34］Danon L，Diaz-Guilera A，Duch J，et al. Comparing community structure identification［J］. Journal of Statistical Mechanics： Theory and Experiment，2005，2005（9）： 98-10.

［35］Zachary W. An information flow model for conflict and fission in small groups［J］.Journal of Anthropological Research，1977，33（4）：452-473.

［36］Lusseau D，Schneider K，Boisseau O J，et al. The bottlenose dolphin community of doubtful sound features a large pro-portion of long-las-ting associations［J］. Behavioral Ecology and Sociobiology，2003，54（4）： 396-405.

［37］Rozemberczki B，Sarkar R. Characteristic functions on graphs： birds of a feather，from statistical descriptors to parametric models［C］// Proc of the 29th ACM International Conference on Information amp; Knowledge Management. New York： ACM Press，2020： 1325-1334.

［38］Yang J，Leskovec J. Defining and evaluating network com-munities based on ground-truth［J］. Knowledge and Information Systems，2015，42（1）： 181-213.

收稿日期：2022-07-05；修回日期：2022-08-23 基金項目：國家自然科學基金資助項目（61762036）

作者簡介：陳燕兵（1997-），男，福建莆田人，碩士研究生，主要研究方向為數據挖掘、機器學習；張應龍（1979-），男（通信作者），陜西綏德人，副教授，碩導，博士，主要研究方向為數據挖掘、機器學習（zhang_yinglong@126.com）.