0 引言

    現(xiàn)實世界網(wǎng)絡(luò)具有復(fù)雜性,、高維性和多面性，其基本屬性是網(wǎng)絡(luò)的“社區(qū)結(jié)構(gòu)”,，通常假定為社交網(wǎng)絡(luò)中的組織單元^[1],、引文網(wǎng)絡(luò)中的科研社區(qū)^[2]等。雖然社區(qū)檢測(CD)的研究較早,，但其依然是個具有挑戰(zhàn)性的復(fù)雜問題,，主要體現(xiàn)在：(1)CD問題沒有明確的定義，針對同一個網(wǎng)絡(luò)可以得到多個解,，且每個解都有其自身的重要意義,；(2)現(xiàn)實世界網(wǎng)絡(luò)的頂點常屬于多個社區(qū)^[3-4]，導(dǎo)致重疊的社區(qū)結(jié)構(gòu),。

    傳統(tǒng)的CD算法大多假定社區(qū)是非重疊的,，如基于頂點相似性的算法^[5]、基于顯著性的算法^[6],、基于模塊優(yōu)化的算法^[7]等,。在現(xiàn)實世界中，一個頂點屬于多個社區(qū),，從而產(chǎn)生重疊社區(qū)結(jié)構(gòu),。因此也有一些重疊CD算法，如文獻[8]提出了基于擴展激活的標(biāo)簽傳播算法(LPAEA),，用于動態(tài)社交網(wǎng)絡(luò)中的重疊社區(qū)檢測,；文獻[9]加強了節(jié)點自身的內(nèi)容特性，提出了增廣網(wǎng)絡(luò)的CD算法,。

    此外,，在數(shù)據(jù)挖掘中，也經(jīng)常利用集成方法進行數(shù)據(jù)點聚類,。如文獻[10]將CD問題建模為一個單目標(biāo)優(yōu)化問題,，提出了一個新的Memetic算法，通過優(yōu)化模糊度評價指標(biāo)檢測復(fù)雜網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu),，并使用“一致續(xù)存”度量來修改給定的非重疊社區(qū)結(jié)構(gòu),；文獻[11]提出的集成算法MEDOC使用了元社區(qū)的概念，利用基礎(chǔ)非重疊社區(qū)結(jié)構(gòu)來創(chuàng)建多分體網(wǎng)絡(luò),，通過隸屬函數(shù)來確定頂點對社區(qū)的隸屬性,。

    由于非重疊CD算法會從一個網(wǎng)絡(luò)中生成大量(且顯著不同的)社區(qū)結(jié)構(gòu)，本文利用該信息來提取與每個頂點相關(guān)聯(lián)的隱性特征信息,，提出了一種集成重疊社區(qū)檢測方法(IOCD),，充分利用了非重疊CD的生成解。實驗結(jié)果表明,，所提IOCD的性能優(yōu)秀,，框架具有良好的通用性。因此,，在網(wǎng)絡(luò)拓?fù)洳煌暾?、本質(zhì)上具有稀疏性且頂點屬性可用的情況下，可利用所提框架將特征合并到模型中以進行重疊社區(qū)檢測,。

1 提出的算法概況

    本文設(shè)計IOCD算法,，以最大化社區(qū)內(nèi)每個節(jié)點的隸屬可能性。IOCD首先在網(wǎng)絡(luò)上以不同的頂點順序運行所有的基礎(chǔ)非重疊CD算法,，得到不同的基礎(chǔ)社區(qū)結(jié)構(gòu),。除此之外，利用基礎(chǔ)社區(qū)信息為每個頂點生成特征向量,，由此將網(wǎng)絡(luò)中的頂點轉(zhuǎn)換為特征空間,。每次迭代中，算法通過從指定社區(qū)中隨機移除頂點并將其分配至一些未指定社區(qū),，以調(diào)整社區(qū)結(jié)構(gòu)^[12],，由此避免違反相似性條件。在每次迭代后,，對每個社區(qū)相關(guān)的相似性閾值進行更新,。持續(xù)進行迭代，直至目標(biāo)函數(shù)的數(shù)值開始下降,。

2 算法實現(xiàn)細(xì)節(jié)

2.1 生成頂點的特征向量

2.2 目標(biāo)函數(shù)

    首先,，定義目標(biāo)函數(shù)需要明確幾個度量。

    其中,，每個社區(qū)均關(guān)聯(lián)到一個最小相似度閾值,，每個頂點必須滿足該閾值才能成為相應(yīng)社區(qū)的一部分。

    (3)每個社區(qū)的相似度閾值：在提出的模型中,，每個社區(qū)OC_j均被分配一個相似度閾值τ_j,，若頂點v∈V在OC_j中，則其應(yīng)該滿足SIM′(OCj,，v)≥τ_j,。給定OC={OC₁,，OC₂，…},，一個重疊社區(qū)結(jié)構(gòu)和閾值集合ζ={τ₁,，τ₂，…},，根據(jù)兩個頂點在不同的重疊社區(qū)中的隸屬性,，定義這兩個頂點之間的隸屬相似度。

    (4)逐對頂點的隸屬相似度：根據(jù)頂點u和v在不同社區(qū)中的隸屬性來定義兩個頂點之間的隸屬相似度：

    算法將式(8)中的目標(biāo)函數(shù)最大化(算法1第31行),，以得到最終重疊社區(qū)結(jié)構(gòu)OC,。

2.3 更新閾值并計算目標(biāo)函數(shù)

2.4 復(fù)雜度分析

    當(dāng)目標(biāo)函數(shù)達(dá)到最大值且不發(fā)生進一步變化時，IOCD終止,。最差情況下,，在任意一次迭代后，重疊社區(qū)的最大數(shù)量為|V|,，每個社區(qū)內(nèi)頂點最大數(shù)量也為|V|,。由此，每次迭代后的運行時間為O(|V|+|OC|),。需注意的是,，只有在對數(shù)似然值增加的情況下，才可以對當(dāng)前社區(qū)結(jié)構(gòu)進行調(diào)整,。因此,，IOCD通常會在有限次數(shù)的迭代后收斂。實踐中,，本文假定如果對數(shù)似然值在|V|次迭代后不發(fā)生變化,，則達(dá)到局部最大值。此外,，IOCD是一個集成算法,，需要運行所有基礎(chǔ)算法，其優(yōu)化途徑之一是基礎(chǔ)算法的并行化,。

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集

    本文使用了兩類網(wǎng)絡(luò)數(shù)據(jù)集：

    (1)合成網(wǎng)絡(luò)：利用LFR基準(zhǔn)模型^[10]來生成合成網(wǎng)絡(luò)及社區(qū),。參數(shù)配置如下：頂點數(shù)量N=10 000；平均度=50,；最大度k_max=150,；最大社區(qū)規(guī)模c_max=150；最小社區(qū)規(guī)模c_min=50,；重疊頂點百分比O_n=15%,；一個頂點所屬的社區(qū)數(shù)量O_m=20；混合參數(shù)μ=0.3(表示社區(qū)間和社區(qū)內(nèi)的邊的比率,；?滋數(shù)值越低,，表示社區(qū)質(zhì)量越高),。針對每個配置創(chuàng)建100個LFR網(wǎng)絡(luò)，并報告平均結(jié)果,。

    (2)現(xiàn)實世界的社區(qū)網(wǎng)絡(luò)：使用2個不同規(guī)模的現(xiàn)實網(wǎng)絡(luò),，且為先驗可用，如表2所示,。

3.2 度量

    為比較檢測到的重疊社區(qū)結(jié)構(gòu)，本文使用了3個標(biāo)準(zhǔn)度量：(1)重疊歸一化互信息(ONMI)^[14],；(2)Ω指標(biāo)^[7],；(3)F測度^[7]。

3.3 評價分析

    本文在LFR網(wǎng)絡(luò)和2個真實世界網(wǎng)絡(luò)上運行IOCD與其他3個重疊CD算法,，這3個算法分別是：文獻[8]提出的基于擴展激活的標(biāo)簽傳播算法(LPAEA),；文獻[10]提出的Memetic算法，將CD問題建模為一個單目標(biāo)優(yōu)化問題,；文獻[11]提出的集成算法MEDOC,，使用了元社區(qū)的概念。實驗通過3個評價指標(biāo)對輸出進行比較,。表3～表5分別給出了在ONMI,、Ω指標(biāo)和F值方面的性能。整體上,，IOCD表現(xiàn)出最優(yōu)性能,，其次為MEDOC^[11]。IOCD在所有網(wǎng)絡(luò)上的絕對平均值ONMI為0.82,。IOCD的Ω指標(biāo)和F值的絕對平均值分別為0.82和0.83,。

    所提IOCD的性能明顯優(yōu)于LPAEA^[8]、Memetic^[10]和MEDOC^[11]的可能原因列舉如下,。Memetic和MEDOC的最終性能取決于單個CD算法的性能,。Memetic在找到單個非重疊社區(qū)結(jié)構(gòu)后，通過后處理步驟發(fā)現(xiàn)重疊屬性,，因此重疊社區(qū)結(jié)構(gòu)的質(zhì)量取決于最初找到的非重疊社區(qū)結(jié)構(gòu),。LPAEA利用未標(biāo)簽的數(shù)據(jù)來捕捉整個數(shù)據(jù)的潛在分布，相似的數(shù)據(jù)必須要有相同的標(biāo)簽,，對CD算法有一定依賴性,。MEDOC利用CD算法，對利用基礎(chǔ)非重疊社區(qū)結(jié)構(gòu)所創(chuàng)建的多分體網(wǎng)絡(luò)進行劃分,，因此最終重疊社區(qū)結(jié)構(gòu)的質(zhì)量取決于在多分體網(wǎng)絡(luò)上使用的CD算法的性能,。另一方面，IOCD通過多個非重疊CD算法給出的非重疊社區(qū)結(jié)構(gòu)來取得頂點特征,，并以優(yōu)化后的設(shè)置來使用這些特征,。因此,，IOCD的性能不取決于任何一個CD算法，能夠從多個非重疊社區(qū)結(jié)構(gòu)中進行有效學(xué)習(xí),。

3.4 參數(shù)選擇分析

    本文通過將混合參數(shù)μ從0.1～0.8之間變化(以0.1遞增),，在LFR網(wǎng)絡(luò)上進行實驗，涉及的主要參數(shù)問題如下,。

    (1)涉入度函數(shù)（INV）：以下兩個函數(shù)用于量化頂點在社區(qū)中的涉入程度：

    涉入度函數(shù)如圖1所示,，混合參數(shù)μ從0.1～0.8之間變化（以0.1遞增）?？梢钥闯?，所提IOCD在使用一致存續(xù)性度量時始終取得了較好性能。

    (2)兩個頂點之間的相似度(SIM)：本文在2.2節(jié)提到了利用余弦相似性來測量兩個頂點的特征向量之間的相似度,，但本文還使用了Pearson相關(guān)系數(shù)測量了兩個特征向量之間的相似度,。結(jié)果表明，余弦相似性度量的性能優(yōu)于Pearson相關(guān)系數(shù),，如圖2所示,。

    (3)迭代次數(shù)(K)：根據(jù)網(wǎng)絡(luò)中頂點的數(shù)量N來設(shè)定K。圖3的分析表明,，對于大部分網(wǎng)絡(luò),，特別是具有獨特社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)(例如混合參數(shù)μ=0.1的LFR網(wǎng)絡(luò))，IOCD的性能會在K=0.2|V|處收斂,，因此,，將K=0.2|V|作為默認(rèn)值。

4 結(jié)論

    本文充分利用了非重疊CD的生成解,，將解的信息與每個頂點相關(guān)聯(lián)的隱性特征信息,，利用多個非重疊CD算法的輸出進行重疊社區(qū)檢測，所提IOCD幾乎不受基礎(chǔ)CD算法的影響,。多個數(shù)據(jù)集上的實驗結(jié)果表明,，所提IOCD優(yōu)于一些同類CD算法。未來可能通過相關(guān)性研究或基于機器學(xué)習(xí)的方法來提升CD算法的求解效率,。

參考文獻

[1] 劉天華,，殷守林，李航.一種新的在線社交網(wǎng)絡(luò)的隱私保護方案[J].電子技術(shù)應(yīng)用,，2015,，41(4)：122-124.

[2] 羅雙玲，張文琪,，夏昊翔.基于半積累引文網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的學(xué)科領(lǐng)域主題演化分析——以“合作演化”領(lǐng)域為例[J].情報學(xué)報,，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] 崔俊明,，李勇，李躍新.基于非加權(quán)圖的大型社會網(wǎng)絡(luò)檢測算法研究[J].電子技術(shù)應(yīng)用,，2018,，44(2)：86-89，93.

[5] 陳曉,，郭景峰,，張春英.社會網(wǎng)絡(luò)頂點間相似性度量及其應(yīng)用[J].計算機科學(xué)與探索，2017,，11(10)：1629-1641.

[6] ANDREA L,，F(xiàn)ILIPPO R，RAMASCO JOSE J,，et al.Finding statistically significant communities in networks[J].PLOS ONE,，2011,，6(4)：61-71.

[7] 闕建華.社交網(wǎng)絡(luò)中基于近似因子的自適應(yīng)社區(qū)檢測算法[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] 蔣盛益，楊博泓,，姚娟娜,，等.一種基于增廣網(wǎng)絡(luò)的快速微博社區(qū)檢測算法[J].中文信息學(xué)報，2016,，30(5)：65-72.

[10] 郭楊志.復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的重疊社區(qū)發(fā)現(xiàn)和魯棒性分析[D].西安：西安電子科技大學(xué),，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] 龍浩,，汪浩.復(fù)雜社會網(wǎng)絡(luò)的兩階段社區(qū)發(fā)現(xiàn)算法[J].小型微型計算機系統(tǒng),，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] 陳曉,，郭景峰，張春英.社會網(wǎng)絡(luò)頂點間相似性度量及其應(yīng)用[J].計算機科學(xué)與探索,，2017,，11(10)：1629-1641.

作者信息:

陳吉成，陳鴻昶,，李邵梅

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,，河南 鄭州450002)