一種改進(jìn)的種子擴(kuò)展的重疊社區(qū)檢測(cè)算法

段瑞瑋 張公敬

摘要：針對(duì)基于種子擴(kuò)展的重疊社區(qū)檢測(cè)算法存在因種子選取質(zhì)量不高而導(dǎo)致重疊社區(qū)檢測(cè)結(jié)果準(zhǔn)確度較低的問(wèn)題，提出一種利用圖嵌入、聚類(lèi)和K-shell相結(jié)合的新的種子選取策略來(lái)進(jìn)行種子擴(kuò)展的重疊社區(qū)檢測(cè)算法。算法利用提出的新的種子選取策略得到種子集，根據(jù)社區(qū)度量函數(shù)即電導(dǎo)性最優(yōu)的原則不斷進(jìn)行種子擴(kuò)展完成社區(qū)劃分。研究結(jié)果表明，改進(jìn)的種子擴(kuò)展的重疊社區(qū)檢測(cè)算法提高了檢測(cè)結(jié)果的準(zhǔn)確度。

關(guān)鍵詞：重疊社區(qū);圖嵌入;聚類(lèi);K-shell;種子擴(kuò)展;社區(qū)檢測(cè)

中圖分類(lèi)號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1006-1037（2021）01-0064-06

基金項(xiàng)目：國(guó)家自然科學(xué)基金（批準(zhǔn)號(hào)：61872205）資助。

通信作者：張公敬，男，副教授，主要研究方向?yàn)閿?shù)據(jù)挖掘、智能信息處理、信息安全等。E-mail：zhang8887327@163.com

復(fù)雜網(wǎng)絡(luò)是具有大量節(jié)點(diǎn)和連接的網(wǎng)絡(luò)，社區(qū)是節(jié)點(diǎn)內(nèi)部連接緊密而外部連接相對(duì)稀疏的一組節(jié)點(diǎn)集群，社區(qū)檢測(cè)可以發(fā)現(xiàn)由相似屬性節(jié)點(diǎn)組成的密集集群。在非重疊社區(qū)結(jié)構(gòu)[1]中，網(wǎng)絡(luò)里的每個(gè)節(jié)點(diǎn)只能屬于一個(gè)社區(qū)，隨著對(duì)復(fù)雜網(wǎng)絡(luò)的深入研究，人們逐漸發(fā)現(xiàn)重疊社區(qū)更加符合個(gè)體在現(xiàn)實(shí)網(wǎng)絡(luò)中存在的規(guī)律，其中同時(shí)參與多個(gè)社區(qū)的節(jié)點(diǎn)被稱(chēng)為重疊節(jié)點(diǎn)，因此，對(duì)重疊社區(qū)發(fā)現(xiàn)研究的關(guān)注度越來(lái)越高。當(dāng)前被最廣泛應(yīng)用的重疊社區(qū)檢測(cè)算法主要分為三類(lèi)：基于標(biāo)簽傳播的重疊社區(qū)檢測(cè)算法[2-3]，這類(lèi)算法根據(jù)節(jié)點(diǎn)的大多數(shù)鄰居節(jié)點(diǎn)的標(biāo)簽為其添加標(biāo)簽以代表所屬的社區(qū)，但是檢測(cè)結(jié)果不穩(wěn)定;基于節(jié)點(diǎn)相似度的重疊社區(qū)檢測(cè)算法[4-5]，基本思想是網(wǎng)絡(luò)中越相似的節(jié)點(diǎn)越容易聚集成群，相對(duì)于基于標(biāo)簽傳播的重疊社區(qū)檢測(cè)算法，穩(wěn)定性有了提高，但是時(shí)間復(fù)雜度較高;基于種子擴(kuò)展的重疊社區(qū)檢測(cè)算法[6-7]，核心思想是找到好的種子，然后基于社區(qū)度量函數(shù)貪婪地?cái)U(kuò)展種子，直至完成社區(qū)檢測(cè)。相對(duì)于前兩類(lèi)重疊社區(qū)檢測(cè)算法，在穩(wěn)定性和時(shí)間復(fù)雜度上有了明顯提高，也適用于大型網(wǎng)絡(luò)?；诜N子擴(kuò)展的重疊社區(qū)檢測(cè)算法又可分為兩類(lèi)：基于種子擴(kuò)展的局部重疊社區(qū)檢測(cè)算法，例如，Hollocou等[8]提出的通過(guò)擴(kuò)展初始給定種子集來(lái)檢測(cè)多個(gè)可能重疊的局部社區(qū)的Mutilcom算法，但僅可識(shí)別出與給定種子集相關(guān)的局部社區(qū)，不能全面了解網(wǎng)絡(luò)的信息從而提供實(shí)際應(yīng)用價(jià)值;基于種子擴(kuò)展的全局重疊社區(qū)檢測(cè)算法，例如，Whang等[9]提出的NISE算法，首先對(duì)節(jié)點(diǎn)進(jìn)行過(guò)濾，然后通過(guò)新的播種策略找到好的種子，最后進(jìn)行種子擴(kuò)展完成社區(qū)檢測(cè)。這類(lèi)算法可全面了解網(wǎng)絡(luò)的信息，準(zhǔn)確識(shí)別網(wǎng)絡(luò)中所有社區(qū)的組織和功能，從而提供更加完善的實(shí)際應(yīng)用價(jià)值。但是其普遍存在的問(wèn)題是對(duì)選取的種子節(jié)點(diǎn)敏感，種子的質(zhì)量對(duì)最終社區(qū)檢測(cè)效果影響較大?；诜N子擴(kuò)展的全局重疊社區(qū)檢測(cè)算法出現(xiàn)的問(wèn)題，本文對(duì)如何在網(wǎng)絡(luò)中找到高質(zhì)量的種子進(jìn)行重疊社區(qū)檢測(cè)的方法做了改進(jìn)，提出一種改進(jìn)的種子擴(kuò)展的重疊社區(qū)檢測(cè)算法（Graph-embedding clustering seed expansion， GCSE）。

1 方案

1.1 問(wèn)題定義，相關(guān)知識(shí)和社區(qū)質(zhì)量評(píng)價(jià)標(biāo)準(zhǔn)

社區(qū)是一組連接緊密的節(jié)點(diǎn)集群，這些節(jié)點(diǎn)內(nèi)部的相互連接密度高于與外部節(jié)點(diǎn)的連接密度。給定無(wú)向無(wú)權(quán)圖G=（V，E），圖中節(jié)點(diǎn)集用V表示，邊集用E表示。將此無(wú)向圖表示為鄰接矩陣M，M矩陣是對(duì)稱(chēng)的，Mij=0時(shí)，表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間無(wú)邊相連，Mij=1時(shí)，表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間有邊相連。重疊社區(qū)檢測(cè)問(wèn)題的目標(biāo)是將圖劃分為k個(gè)簇，這k個(gè)簇之間存在重疊現(xiàn)象，這些簇內(nèi)節(jié)點(diǎn)集合滿足T1∪T2∪…∪TkV關(guān)系。

判斷網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性程度有很多種方法，如度中心性、介數(shù)中心性、接近中心性， K-shell[10]分解算法等。其中度中心性忽略了節(jié)點(diǎn)的鄰居對(duì)節(jié)點(diǎn)影響力起到的間接作用，介數(shù)中心性和接近中心性未將節(jié)點(diǎn)的拓?fù)湮恢每紤]進(jìn)去來(lái)綜合評(píng)判節(jié)點(diǎn)的重要性，而K-shell分解算法考慮節(jié)點(diǎn)的拓?fù)湮恢?，可以根?jù)節(jié)點(diǎn)的影響力得到較粗粒度的排序結(jié)果，為此，本文借助該算法得到網(wǎng)絡(luò)拓?fù)浜诵墓?jié)點(diǎn)集，通過(guò)提出的節(jié)點(diǎn)影響力評(píng)判標(biāo)準(zhǔn)得到核心節(jié)點(diǎn)集中影響力最大的節(jié)點(diǎn)。

本文用社區(qū)質(zhì)量評(píng)價(jià)標(biāo)準(zhǔn)NMI[11]來(lái)衡量算法社區(qū)檢測(cè)的效果

其中，N表示節(jié)點(diǎn)數(shù)量，A表示已知社區(qū)分布，B表示檢測(cè)到的社區(qū)分布，C是一個(gè)混淆矩陣，矩陣中的元素Cij表示既屬于A中i社區(qū)也屬于B中j社區(qū)的節(jié)點(diǎn)的數(shù)量，CA是已知的社區(qū)數(shù)量，CB是檢測(cè)到的社區(qū)數(shù)量，Ci（Cj）為社區(qū)C第i行（第j列）的節(jié)點(diǎn)數(shù)量之和。

用電導(dǎo)性[9]（conductance）作為衡量單個(gè)社區(qū)質(zhì)量的評(píng)價(jià)標(biāo)準(zhǔn)

1.2 重疊社區(qū)檢測(cè)算法GCSE

本節(jié)提出一種改進(jìn)的種子擴(kuò)展的重疊社區(qū)檢測(cè)算法GCSE。

1.2.1 圖中節(jié)點(diǎn)表示為向量 本文應(yīng)用了圖嵌入算法DeepWalk[12]，是一種將隨機(jī)游走（random walk）和word2vec兩種算法相結(jié)合的圖結(jié)構(gòu)數(shù)據(jù)挖掘算法。該算法能夠?qū)W習(xí)網(wǎng)絡(luò)的隱藏信息，將圖中的節(jié)點(diǎn)表示為一個(gè)包含潛在信息的向量，該算法主要分為隨機(jī)游走和生成表示向量?jī)蓚€(gè)部分。通過(guò)該算法將圖中節(jié)點(diǎn)表示為向量后，根據(jù)節(jié)點(diǎn)在嵌入空間中的相互距離進(jìn)行聚類(lèi)。

1.2.2 基于可變密度的聚類(lèi)算法對(duì)節(jié)點(diǎn)進(jìn)行聚類(lèi) 將上一節(jié)得到的向量利用聚類(lèi)算法得到簇。已有的聚類(lèi)算法DBSCAN[13]首先將數(shù)據(jù)點(diǎn)集中的每個(gè)節(jié)點(diǎn)標(biāo)記為未處理對(duì)象，人工輸入半徑參數(shù)Eps和密度閾值MinPts，然后計(jì)算每個(gè)節(jié)點(diǎn)Eps半徑內(nèi)節(jié)點(diǎn)的個(gè)數(shù)，若Eps半徑內(nèi)節(jié)點(diǎn)的個(gè)數(shù)多于密度閾值MinPts，則標(biāo)記這個(gè)節(jié)點(diǎn)為核心點(diǎn)，在核心點(diǎn)鄰域內(nèi)剩余的點(diǎn)則被標(biāo)記為邊界點(diǎn)，否則將被標(biāo)記為噪聲點(diǎn)。如果該算法的半徑參數(shù)Eps和密度閾值MinPts選擇不合理將會(huì)使得聚類(lèi)準(zhǔn)確率降低。為此，本文提出基于可變密度的聚類(lèi)算法（Variable density-Based Spatial Clustering of Applications with Noise， VDBSCAN），根據(jù)節(jié)點(diǎn)在嵌入空間中的相互距離利用VDBSCAN進(jìn)行聚類(lèi)得到簇D1，D2，…，Dk，以提高聚類(lèi)準(zhǔn)確率。

首先給定參數(shù)Eps，按照每個(gè)節(jié)點(diǎn)Eps半徑內(nèi)的節(jié)點(diǎn)個(gè)數(shù)對(duì)節(jié)點(diǎn)從大到小排序，對(duì)于Eps半徑內(nèi)節(jié)點(diǎn)個(gè)數(shù)相同的節(jié)點(diǎn)，利用高斯核相似度更細(xì)化的區(qū)分節(jié)點(diǎn)之間的局部密度。高斯核相似度定義

其中，de的值為半徑參數(shù)Eps，dij為半徑Eps范圍內(nèi)的點(diǎn)i到點(diǎn)j的距離，Ir表示節(jié)點(diǎn)i半徑Eps范圍內(nèi)的所有節(jié)點(diǎn)。按照局部密度的大小對(duì)每個(gè)節(jié)點(diǎn)從大到小排序，選取局部密度最大的節(jié)點(diǎn)做核心點(diǎn)，按照該點(diǎn)成為核心點(diǎn)的密度閾值MinPts并結(jié)合之前給定的半徑參數(shù)Eps繼續(xù)擴(kuò)展聚類(lèi)。之后，在未被處理的節(jié)點(diǎn)中選取密度最大的點(diǎn)做核心點(diǎn)，重復(fù)上一步，直到剩余的節(jié)點(diǎn)無(wú)法作為核心點(diǎn)停止（即剩余未處理的節(jié)點(diǎn)在其半徑Eps范圍內(nèi)節(jié)點(diǎn)的個(gè)數(shù)小于4）。最后，形成簇D1，D2，…，Dk，對(duì)于節(jié)點(diǎn)個(gè)數(shù)不足3個(gè)的簇，將其合并到與它距離最近的簇中，聚類(lèi)結(jié)束。

1.2.3 選取種子 將上一節(jié)形成的簇D1，D2，…，Dk分別利用K-shell劃分層次，找到每個(gè)簇的核心節(jié)點(diǎn)集，如果核心節(jié)點(diǎn)集中只有一個(gè)節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)作為新的種子加入種子集S。如果核心節(jié)點(diǎn)集中包含多個(gè)節(jié)點(diǎn)，則需要詳細(xì)區(qū)分具有同一K-shell值的節(jié)點(diǎn)的影響力。本文使用下列公式對(duì)節(jié)點(diǎn)的重要性程度進(jìn)行排序，選出重要性程度最高的節(jié)點(diǎn)作為新的種子加入種子集S

將加權(quán)網(wǎng)絡(luò)中的邊權(quán)概念引入無(wú)向無(wú)權(quán)網(wǎng)絡(luò)中，邊權(quán)Wij值定義為一條邊的兩端節(jié)點(diǎn)的度數(shù)之和，其中di為節(jié)點(diǎn)i的度數(shù)，dj為節(jié)點(diǎn)j的度數(shù)。

節(jié)點(diǎn)的點(diǎn)權(quán)又稱(chēng)為點(diǎn)強(qiáng)度（Vertex Strength），定義為與節(jié)點(diǎn)相連的邊權(quán)之和，Ni為節(jié)點(diǎn)i的直接相連節(jié)點(diǎn)的集合。

其中，Ti表示節(jié)點(diǎn)i的鄰域聚類(lèi)緊密程度，反映了節(jié)點(diǎn)i的直接鄰居之間的連接緊密程度，Ei為節(jié)點(diǎn)i的Ki個(gè)直接鄰居之間的連邊個(gè)數(shù)。

其中，F(xiàn)i是點(diǎn)i及其直接鄰居對(duì)鄰域的影響力。

其中，MNi表示節(jié)點(diǎn)i的影響力大小，節(jié)點(diǎn)i的MNi值越大則說(shuō)明節(jié)點(diǎn)i在其鄰域中影響力越大。經(jīng)過(guò)上述步驟可以得到各個(gè)簇D1，D2，…，Dk的核心節(jié)點(diǎn)集中影響力最大的節(jié)點(diǎn)，將這個(gè)節(jié)點(diǎn)作為新的種子節(jié)點(diǎn)添加到種子集S中。

1.2.4 種子擴(kuò)展 利用Personalized PageRank [8]評(píng)分函數(shù)對(duì)種子集S中的每個(gè)新種子節(jié)點(diǎn)s的鄰域節(jié)點(diǎn)進(jìn)行打分，得到每個(gè)節(jié)點(diǎn)的得分向量fs。按照f(shuō)s分值從高到低的順序，根據(jù)電導(dǎo)性依次判斷節(jié)點(diǎn)是否要加入當(dāng)前種子所在的局部社區(qū)，當(dāng)節(jié)點(diǎn)加入社區(qū)使得當(dāng)前社區(qū)電導(dǎo)性更優(yōu)時(shí)，將該節(jié)點(diǎn)劃分到這個(gè)社區(qū)，再按順序依次檢查其他節(jié)點(diǎn)的加入會(huì)不會(huì)引起社區(qū)電導(dǎo)性的變化，最后返回達(dá)到電導(dǎo)性最優(yōu)的集群。

1.2.5 社區(qū)合并 在社交網(wǎng)絡(luò)中，一個(gè)節(jié)點(diǎn)通常同時(shí)參與多個(gè)社區(qū)，所以由GCSE算法返回的社區(qū)可能存在重疊現(xiàn)象。在GCSE算法的末尾增加了一個(gè)名為合并的處理步驟。如果兩個(gè)社區(qū)之間重疊節(jié)點(diǎn)過(guò)多，則進(jìn)行社區(qū)合并;如果仍存在重疊節(jié)點(diǎn)，根據(jù)該節(jié)點(diǎn)的加入和刪除對(duì)當(dāng)前所在社區(qū)電導(dǎo)性變化量的影響來(lái)判斷該節(jié)點(diǎn)的歸屬，哪個(gè)社區(qū)的電導(dǎo)性的變化量最大，將節(jié)點(diǎn)歸于該社區(qū);對(duì)于未被分配社區(qū)的節(jié)點(diǎn)按照電導(dǎo)性繼續(xù)為其分配社區(qū)，直到圖中所有節(jié)點(diǎn)都劃分完成。

1.2.6 GCSE算法描述 算法的輸入為一個(gè)無(wú)權(quán)無(wú)向圖，最終輸出結(jié)果為檢測(cè)到的社區(qū)。

Step 1 通過(guò)圖嵌入算法DeepWalk將節(jié)點(diǎn)表示為向量;

Step 2 用改進(jìn)的自適應(yīng)參數(shù)密度聚類(lèi)算法VDBSCAN對(duì)通過(guò)Step 1形成的數(shù)據(jù)點(diǎn)集進(jìn)行聚類(lèi)，形成簇D1，D2，…，Dk;

Step 3 在簇D1，D2，…，Dk中借助K-shell劃分出核心節(jié)點(diǎn)集，從核心節(jié)點(diǎn)集中選出影響力最大的節(jié)點(diǎn)作為種子，加入種子集S;

Step 4 根據(jù)Step 3選取的種子集，利用Personalized PageRank評(píng)分函數(shù)對(duì)其余節(jié)點(diǎn)進(jìn)行評(píng)分，并對(duì)其降序排序，按照排序結(jié)果利用電導(dǎo)性來(lái)獲取各個(gè)種子對(duì)應(yīng)的局部社區(qū);

Step 5 如果兩個(gè)局部社區(qū)之間重疊節(jié)點(diǎn)過(guò)多則對(duì)其進(jìn)行社區(qū)合并。若圖中仍存在重疊節(jié)點(diǎn)和未被分配的節(jié)點(diǎn)，則根據(jù)電導(dǎo)性為其分配社區(qū)，直到社區(qū)中所有節(jié)點(diǎn)劃分完成，并返回最終的社區(qū)檢測(cè)結(jié)果。

karate網(wǎng)絡(luò)[14]是網(wǎng)絡(luò)分析領(lǐng)域的經(jīng)典數(shù)據(jù)集，由34個(gè)節(jié)點(diǎn)組成，實(shí)際上劃分為2個(gè)社區(qū)。本文在karate網(wǎng)絡(luò)上應(yīng)用算法GCSE進(jìn)行社區(qū)檢測(cè)過(guò)程如圖1所示。

2 實(shí)驗(yàn)

2.1 實(shí)驗(yàn)環(huán)境描述和參數(shù)設(shè)置

實(shí)驗(yàn)在Intel （R） 3.6GHZ Xeon（R） W-2133CPU和32G RAM的電腦上運(yùn)行，軟件平臺(tái)為Windows下的Python 3.6。GCSE算法中使用了2個(gè)參數(shù)：d和MinPts。圖嵌入DeepWalk算法將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)通過(guò)Word2vec表示為一個(gè)維度為d的向量，本文將維度d設(shè)置為2。VDBSCAN聚類(lèi)算法中密度參數(shù)MinPts用于控制檢測(cè)的初始化社區(qū)數(shù)量，通過(guò)參數(shù)調(diào)整得知將其設(shè)置為0.46時(shí)較為合適。

2.2 實(shí)驗(yàn)結(jié)果和分析

2.2.1 真實(shí)網(wǎng)絡(luò) 如圖2所示，在Karate網(wǎng)絡(luò)上通過(guò)度中心性查找到的種子為0、5、33，而GCSE通過(guò)綜合考慮節(jié)點(diǎn)的拓?fù)湮恢煤陀绊懥Σ檎业降姆N子為0、16、32，在實(shí)驗(yàn)中也證明了通過(guò)這種方法查找到的種子的質(zhì)量比較高，提高了社區(qū)檢測(cè)的準(zhǔn)確性。實(shí)驗(yàn)中，將GCSE算法與算法CPM[15]，COPRA，BASH[16]，IEDC[17]分別在真實(shí)網(wǎng)絡(luò)karate，dolphins，polbooks和football上進(jìn)行了比較。

圖3顯示了在真實(shí)網(wǎng)絡(luò)上不同算法的NMI值，GCSE算法在四個(gè)真實(shí)網(wǎng)絡(luò)上可以得到良好的社區(qū)檢測(cè)效果。GCSE算法在karate網(wǎng)絡(luò)表現(xiàn)最好，其次是在football網(wǎng)絡(luò)上的表現(xiàn)也優(yōu)于其他算法，得到的社區(qū)檢測(cè)結(jié)果非常接近真實(shí)情況。

2.2.2 仿真網(wǎng)絡(luò) 除了真實(shí)網(wǎng)絡(luò)，使用了LFR （Lancichinetti-Fortunato-Radicchi）基準(zhǔn)網(wǎng)絡(luò)測(cè)試了GCSE算法的性能。其中，仿真網(wǎng)絡(luò)節(jié)點(diǎn)的最大度數(shù)設(shè)置為50，社區(qū)節(jié)點(diǎn)個(gè)數(shù)最小值設(shè)置為20，社區(qū)節(jié)點(diǎn)個(gè)數(shù)最大值設(shè)置為50，節(jié)點(diǎn)平均度設(shè)置為10。本文研究了不同算法取不同μ值和不同On值時(shí)的性能，對(duì)應(yīng)的2組仿真網(wǎng)絡(luò)參數(shù)設(shè)置如下： AD1： N=6 000， Om=3， On=50， μ=0.0～0.4; AD2： N=6 000， Om=3， On =50～400， μ=0.2。

圖4為各算法在AD1仿真網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果，顯示了μ在由0增加到0.4時(shí)，不同算法的NMI值。μ表示社區(qū)結(jié)構(gòu)的重疊度，當(dāng)μ=0時(shí)，所有算法的性能都很好，NMI值接近于1。隨著混合參數(shù)μ的增加，所有算法的性能下降，但是GCSE算法仍然表現(xiàn)出良好的魯棒性，IEDC算法也表現(xiàn)出了較好的性能。

圖5為各算法在AD2仿真網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果。顯示了On從50增加到400時(shí)，不同算法的NMI值。On表示社區(qū)中重疊節(jié)點(diǎn)的數(shù)量，實(shí)驗(yàn)結(jié)果表明，隨著On值的增加，即隨著網(wǎng)絡(luò)中重疊節(jié)點(diǎn)數(shù)量的增加，所有算法的效率和精度均降低，但GCSE算法仍優(yōu)于其他算法，最糟糕的是COPRA算法。

3 結(jié)論

本文提出了一種改進(jìn)的種子擴(kuò)展的重疊社區(qū)檢測(cè)算法GCSE。首先提出一種新的種子選取策略，該策略為利用圖嵌入將節(jié)點(diǎn)表示為向量，接著利用提出的可變密度的聚類(lèi)算法VDBSCAN對(duì)節(jié)點(diǎn)進(jìn)行聚類(lèi)，改進(jìn)后的聚類(lèi)算法對(duì)不同密度節(jié)點(diǎn)集群的適應(yīng)性更強(qiáng)，考慮節(jié)點(diǎn)的拓?fù)湮恢靡约肮?jié)點(diǎn)鄰居對(duì)節(jié)點(diǎn)影響力起到的間接作用來(lái)綜合評(píng)判節(jié)點(diǎn)影響力。按照提出的新的種子選取策略從每個(gè)簇中選取種子，利用Personalized PageRank評(píng)分函數(shù)對(duì)節(jié)點(diǎn)進(jìn)行評(píng)分，最后根據(jù)評(píng)分結(jié)果利用電導(dǎo)性擴(kuò)展種子完成社區(qū)檢測(cè)。實(shí)驗(yàn)結(jié)果表明，該算法提高了選取的種子的質(zhì)量和社區(qū)檢測(cè)的準(zhǔn)確性。

參考文獻(xiàn)

[1]LIU Z， MA Y. A divide and agglomerate algorithm for community detection in social networks[J]. Information Sciences， 2019（482）： 321-333.

[2]GREGORY S. Finding overlapping communities in networks by label propagation[J]. New J. Phys.， 2009（12）： 2011-2024.

[3]朱帥， 許國(guó)艷， 李敏佳，等. 基于LeaderRank的重疊社區(qū)發(fā)現(xiàn)算法[J]. 計(jì)算機(jī)與現(xiàn)代化， 2019， 283（3）：94-98.

[4]SUNGSU L， SEUNGWOO R， et al. LinkSCAN*： Overlapping community detection using the link-space transformation[C]// 2014 IEEE 30th International Conference on Data Engineering. Chicago， 2014： 292-303.

[5]BAI L， CHENG X， LIANG J， et al. Fast graph clustering with a new description model for community detection[J]. Information Sciences， 2017（388）： 37-47.

[6]李艷， 賀靜， 武優(yōu)西. 種子節(jié)點(diǎn)貪婪擴(kuò)張的重疊社區(qū)發(fā)現(xiàn)方法[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2019， 40（5）：205-209.

[7]於志勇， 陳基杰， 郭昆， 等. 基于影響力與種子擴(kuò)展的重疊社區(qū)發(fā)現(xiàn)[J]. 電子學(xué)報(bào)， 2019， 47（1）：153-160.

[8]HOLLOCOU A， BONALD T， LELARGE M. Multiple local community detection[J]. ACM Sigmetrics Performance Evaluation Review， 2018， 45（3）： 76-83.

[9]WHANG J， GLEICH F D， DHILLON I. Overlapping community detection using neighborhood-inflated seed expansion[J]. IEEE Transactions on Knowledge and Data Engineering， 2016， 28（5）： 1272-1284.

[10] BONACICH P. Factoring and weighting approaches to status scores and clique identification[J]. Journal of Mathematical Sociology， 1972， 2（1）： 113-120.

[11] ZHANG P. Evaluating accuracy of community detection using the relative normalized mutual information[J]. Computer Science， 2015（11）： 11006.

[12] PEROZZI B， Al-RFOU R， SKIENA S. Deepwalk： Online learning of social representations KDD[C]//20th ACM SIGDD International Conference on Knowledge Discovery and Data Mining. New York， 2014： 701-710.

[13] 歐陽(yáng)佩佩， 趙志剛， 劉桂峰. 一種改進(jìn)的稀疏子空間聚類(lèi)算法[J]. 青島大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2014， 27（3）：44-48.

[14] ZACHARY W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research， 1977，33（4）： 452-473.

[15] PALLA G， DERENYI I， FARKAS I， et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature， 2005， 435（7043）： 814-818.

[16] CUI Y， WANG X， EUSTACE J. Detecting community structure via the maximal sub-graphs and belonging degrees in complex networks[J]. Physica A： Statistical Mechanics and its Applications， 2014（416）： 198-207.

[17] HAJIABADI M， ZARE H， BOBARSHAD H. IEDC： An integrated approach for overlapping and non-overlapping community detection[J]. Knowledge-Based Systems， 2017（123）： 188-199.