文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.190704
中文引用格式： 陳吉成，陳鴻昶，李邵梅. 利用非重疊CD生成解的集成重疊社區檢測[J].電子技術應用，2019，45(12)：96-100，105.
英文引用格式： Chen Jicheng，Chen Hongchang，Li Shaomei. Integrated overlapping CD method using existing solutions of non-over-lapping CD[J]. Application of Electronic Technique，2019，45(12)：96-100，105.
0 引言
現實世界網絡具有復雜性、高維性和多面性，其基本屬性是網絡的“社區結構”，通常假定為社交網絡中的組織單元[1]、引文網絡中的科研社區[2]等。雖然社區檢測(CD)的研究較早，但其依然是個具有挑戰性的復雜問題，主要體現在：(1)CD問題沒有明確的定義，針對同一個網絡可以得到多個解，且每個解都有其自身的重要意義；(2)現實世界網絡的頂點常屬于多個社區[3-4]，導致重疊的社區結構。
傳統的CD算法大多假定社區是非重疊的，如基于頂點相似性的算法[5]、基于顯著性的算法[6]、基于模塊優化的算法[7]等。在現實世界中，一個頂點屬于多個社區，從而產生重疊社區結構。因此也有一些重疊CD算法，如文獻[8]提出了基于擴展激活的標簽傳播算法(LPAEA)，用于動態社交網絡中的重疊社區檢測；文獻[9]加強了節點自身的內容特性，提出了增廣網絡的CD算法。
此外，在數據挖掘中，也經常利用集成方法進行數據點聚類。如文獻[10]將CD問題建模為一個單目標優化問題，提出了一個新的Memetic算法，通過優化模糊度評價指標檢測復雜網絡中的重疊社區結構，并使用“一致續存”度量來修改給定的非重疊社區結構；文獻[11]提出的集成算法MEDOC使用了元社區的概念，利用基礎非重疊社區結構來創建多分體網絡，通過隸屬函數來確定頂點對社區的隸屬性。
由于非重疊CD算法會從一個網絡中生成大量(且顯著不同的)社區結構，本文利用該信息來提取與每個頂點相關聯的隱性特征信息，提出了一種集成重疊社區檢測方法(IOCD)，充分利用了非重疊CD的生成解。實驗結果表明，所提IOCD的性能優秀，框架具有良好的通用性。因此，在網絡拓撲不完整、本質上具有稀疏性且頂點屬性可用的情況下，可利用所提框架將特征合并到模型中以進行重疊社區檢測。
1 提出的算法概況
本文設計IOCD算法，以最大化社區內每個節點的隸屬可能性。IOCD首先在網絡上以不同的頂點順序運行所有的基礎非重疊CD算法，得到不同的基礎社區結構。除此之外，利用基礎社區信息為每個頂點生成特征向量，由此將網絡中的頂點轉換為特征空間。每次迭代中，算法通過從指定社區中隨機移除頂點并將其分配至一些未指定社區，以調整社區結構[12]，由此避免違反相似性條件。在每次迭代后，對每個社區相關的相似性閾值進行更新。持續進行迭代，直至目標函數的數值開始下降。
2 算法實現細節
2.1 生成頂點的特征向量
2.2 目標函數
首先，定義目標函數需要明確幾個度量。
其中，每個社區均關聯到一個最小相似度閾值，每個頂點必須滿足該閾值才能成為相應社區的一部分。
(3)每個社區的相似度閾值：在提出的模型中，每個社區OCj均被分配一個相似度閾值τj，若頂點v∈V在OCj中，則其應該滿足SIM′(OCj，v)≥τj。給定OC={OC1，OC2，…}，一個重疊社區結構和閾值集合ζ={τ1，τ2，…}，根據兩個頂點在不同的重疊社區中的隸屬性，定義這兩個頂點之間的隸屬相似度。
(4)逐對頂點的隸屬相似度：根據頂點u和v在不同社區中的隸屬性來定義兩個頂點之間的隸屬相似度：
算法將式(8)中的目標函數最大化(算法1第31行)，以得到最終重疊社區結構OC。
2.3 更新閾值并計算目標函數
2.4 復雜度分析
當目標函數達到最大值且不發生進一步變化時，IOCD終止。最差情況下，在任意一次迭代后，重疊社區的最大數量為|V|，每個社區內頂點最大數量也為|V|。由此，每次迭代后的運行時間為O(|V|+|OC|)。需注意的是，只有在對數似然值增加的情況下，才可以對當前社區結構進行調整。因此，IOCD通常會在有限次數的迭代后收斂。實踐中，本文假定如果對數似然值在|V|次迭代后不發生變化，則達到局部最大值。此外，IOCD是一個集成算法，需要運行所有基礎算法，其優化途徑之一是基礎算法的并行化。
3 實驗結果與分析
3.1 數據集
本文使用了兩類網絡數據集：
(1)合成網絡：利用LFR基準模型[10]來生成合成網絡及社區。參數配置如下：頂點數量N=10 000；平均度
=50；最大度kmax=150；最大社區規模cmax=150；最小社區規模cmin=50；重疊頂點百分比On=15%；一個頂點所屬的社區數量Om=20；混合參數μ=0.3(表示社區間和社區內的邊的比率；?滋數值越低，表示社區質量越高)。針對每個配置創建100個LFR網絡，并報告平均結果。
(2)現實世界的社區網絡：使用2個不同規模的現實網絡，且為先驗可用，如表2所示。
3.2 度量
為比較檢測到的重疊社區結構，本文使用了3個標準度量：(1)重疊歸一化互信息(ONMI)[14]；(2)Ω指標[7]；(3)F測度[7]。
3.3 評價分析
本文在LFR網絡和2個真實世界網絡上運行IOCD與其他3個重疊CD算法，這3個算法分別是：文獻[8]提出的基于擴展激活的標簽傳播算法(LPAEA)；文獻[10]提出的Memetic算法，將CD問題建模為一個單目標優化問題；文獻[11]提出的集成算法MEDOC，使用了元社區的概念。實驗通過3個評價指標對輸出進行比較。表3～表5分別給出了在ONMI、Ω指標和F值方面的性能。整體上，IOCD表現出最優性能，其次為MEDOC[11]。IOCD在所有網絡上的絕對平均值ONMI為0.82。IOCD的Ω指標和F值的絕對平均值分別為0.82和0.83。
所提IOCD的性能明顯優于LPAEA[8]、Memetic[10]和MEDOC[11]的可能原因列舉如下。Memetic和MEDOC的最終性能取決于單個CD算法的性能。Memetic在找到單個非重疊社區結構后，通過后處理步驟發現重疊屬性，因此重疊社區結構的質量取決于最初找到的非重疊社區結構。LPAEA利用未標簽的數據來捕捉整個數據的潛在分布，相似的數據必須要有相同的標簽，對CD算法有一定依賴性。MEDOC利用CD算法，對利用基礎非重疊社區結構所創建的多分體網絡進行劃分，因此最終重疊社區結構的質量取決于在多分體網絡上使用的CD算法的性能。另一方面，IOCD通過多個非重疊CD算法給出的非重疊社區結構來取得頂點特征，并以優化后的設置來使用這些特征。因此，IOCD的性能不取決于任何一個CD算法，能夠從多個非重疊社區結構中進行有效學習。
3.4 參數選擇分析
本文通過將混合參數μ從0.1～0.8之間變化(以0.1遞增)，在LFR網絡上進行實驗，涉及的主要參數問題如下。
(1)涉入度函數（INV）：以下兩個函數用于量化頂點在社區中的涉入程度：
涉入度函數如圖1所示，混合參數μ從0.1～0.8之間變化（以0.1遞增）。可以看出，所提IOCD在使用一致存續性度量時始終取得了較好性能。
(2)兩個頂點之間的相似度(SIM)：本文在2.2節提到了利用余弦相似性來測量兩個頂點的特征向量之間的相似度，但本文還使用了Pearson相關系數測量了兩個特征向量之間的相似度。結果表明，余弦相似性度量的性能優于Pearson相關系數，如圖2所示。
(3)迭代次數(K)：根據網絡中頂點的數量N來設定K。圖3的分析表明，對于大部分網絡，特別是具有獨特社區結構的網絡(例如混合參數μ=0.1的LFR網絡)，IOCD的性能會在K=0.2|V|處收斂，因此，將K=0.2|V|作為默認值。
4 結論
本文充分利用了非重疊CD的生成解，將解的信息與每個頂點相關聯的隱性特征信息，利用多個非重疊CD算法的輸出進行重疊社區檢測，所提IOCD幾乎不受基礎CD算法的影響。多個數據集上的實驗結果表明，所提IOCD優于一些同類CD算法。未來可能通過相關性研究或基于機器學習的方法來提升CD算法的求解效率。
參考文獻
[1] 劉天華，殷守林，李航.一種新的在線社交網絡的隱私保護方案[J].電子技術應用，2015，41(4)：122-124.
[2] 羅雙玲，張文琪，夏昊翔.基于半積累引文網絡社區發現的學科領域主題演化分析——以“合作演化”領域為例[J].情報學報，2017，36(1)：100-110.
[3] YANG J，LESKOVEC J.Overlapping community detection at scale：A nonnegative matrix factorization approach[C].Proceedings of the Sixth ACM International Conference on Web Search and Data Mining.ACM，2013：587-596.
[4] 崔俊明，李勇，李躍新.基于非加權圖的大型社會網絡檢測算法研究[J].電子技術應用，2018，44(2)：86-89，93.
[5] 陳曉，郭景峰，張春英.社會網絡頂點間相似性度量及其應用[J].計算機科學與探索，2017，11(10)：1629-1641.
[6] ANDREA L，FILIPPO R，RAMASCO JOSE J，et al.Finding statistically significant communities in networks[J].PLOS ONE，2011，6(4)：61-71.
[7] 闕建華.社交網絡中基于近似因子的自適應社區檢測算法[J].計算機工程，2016，42(5)：134-138.
[8] HUANG M，ZOU G，ZHANG B，et al.Overlapping community detection in heterogeneous social networks via the user model[J].Information Sciences，2018，38(4)：164-184.
[9] 蔣盛益，楊博泓，姚娟娜，等.一種基于增廣網絡的快速微博社區檢測算法[J].中文信息學報，2016，30(5)：65-72.
[10] 郭楊志.復雜網絡社區結構的重疊社區發現和魯棒性分析[D].西安：西安電子科技大學，2018.
[11] CHAKRABORTY T，PARK N，SUBRAHMANIAN V S.Ensemble-based algorithms to detect disjoint and overlapping communities in networks[J].ASONAM，2016，45(12)：73-80.
[12] 龍浩，汪浩.復雜社會網絡的兩階段社區發現算法[J].小型微型計算機系統，2016，37(4)：694-698.
[13] KANAWATI R.YASCA：an ensemble-based approach for community detection in complex networks[M].Computing and Combinatorics. Springer International Publishing，2014.
[14] HAJIABADI M，ZARE H，BOBARSHAD H.IEDC：an integrated approach for overlapping and non-overlapping community detection[J].Knowledge-Based Systems，2017，43(3)：188-199.
[15] 陳曉，郭景峰，張春英.社會網絡頂點間相似性度量及其應用[J].計算機科學與探索，2017，11(10)：1629-1641.
作者信息:
陳吉成，陳鴻昶，李邵梅
(國家數字交換系統工程技術研究中心，河南 鄭州450002)