0 引言

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

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

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

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

1 提出的算法概況

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

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

2.1 生成頂點(diǎn)的特征向量

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

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

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

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

    (4)逐對(duì)頂點(diǎn)的隸屬相似度：根據(jù)頂點(diǎn)u和v在不同社區(qū)中的隸屬性來(lái)定義兩個(gè)頂點(diǎn)之間的隸屬相似度：

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

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

2.4 復(fù)雜度分析

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

3.2 度量

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

3.3 評(píng)價(jià)分析

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

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

3.4 參數(shù)選擇分析

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

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

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

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

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

4 結(jié)論

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

參考文獻(xiàn)

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

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

[5] 陳曉，郭景峰，張春英.社會(huì)網(wǎng)絡(luò)頂點(diǎn)間相似性度量及其應(yīng)用[J].計(jì)算機(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ū)檢測(cè)算法[J].計(jì)算機(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ū)檢測(cè)算法[J].中文信息學(xué)報(bào)，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ù)雜社會(huì)網(wǎng)絡(luò)的兩階段社區(qū)發(fā)現(xiàn)算法[J].小型微型計(jì)算機(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] 陳曉，郭景峰，張春英.社會(huì)網(wǎng)絡(luò)頂點(diǎn)間相似性度量及其應(yīng)用[J].計(jì)算機(jī)科學(xué)與探索，2017，11(10)：1629-1641.

作者信息:

陳吉成，陳鴻昶，李邵梅

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