多點(diǎn)種子預(yù)劃分的二階段社區(qū)發(fā)現(xiàn)算法

佟帥 陳德運(yùn) 楊海陸

摘 要：社區(qū)發(fā)現(xiàn)是在線社交網(wǎng)絡(luò)研究領(lǐng)域中的重要內(nèi)容，基于種子擴(kuò)張的社區(qū)發(fā)現(xiàn)算法具有時(shí)間復(fù)雜度低、識(shí)別精度高以及不受社區(qū)形態(tài)限制等特點(diǎn)，近年來(lái)在網(wǎng)絡(luò)局部社區(qū)發(fā)現(xiàn)任務(wù)中得到了廣泛的應(yīng)用。然而，該方法在種子選取時(shí)沒(méi)有考慮種子之間的關(guān)聯(lián)性，因此識(shí)別出的社區(qū)結(jié)構(gòu)個(gè)數(shù)較多、結(jié)構(gòu)松散。針對(duì)這一問(wèn)題，提出一種基于多點(diǎn)種子預(yù)劃分的二階段社區(qū)發(fā)現(xiàn)算法。首先識(shí)別網(wǎng)絡(luò)中的高影響力節(jié)點(diǎn)，利用K-means算法將高影響力節(jié)點(diǎn)加以聚合，得到高影響力社區(qū)簇。然后提出一種吸引力度量函數(shù)，選擇性的將網(wǎng)絡(luò)中的剩余節(jié)點(diǎn)合并到社區(qū)簇以完成社區(qū)識(shí)別任務(wù)。實(shí)驗(yàn)結(jié)果表明，二階段社區(qū)發(fā)現(xiàn)方法能夠發(fā)現(xiàn)尺寸較大，個(gè)數(shù)較少的社區(qū)結(jié)構(gòu)，進(jìn)而在中觀層面捕捉群組之間的關(guān)聯(lián)性。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò);局部社區(qū)發(fā)現(xiàn);種子擴(kuò)張;節(jié)點(diǎn)影響力;K-means算法

DOI：10.15938/j.jhust.2021.04.011

中圖分類號(hào)：TP391.4

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

文章編號(hào)：1007-2683（2021）04-0078-09

Abstract：Community detection is an important content in the field of online social networks research. The community detection algorithm based on seed expansion has the characteristics of low time complexity， high recognition accuracy， and is not restricted by the shape of the community. In recent years， it has been widely used in local community discovery of complex networks. However， this method does not consider the correlation between seeds when selecting seeds， so the number of identified community structures is large and the structure is loose. Aiming at this problem， a two-stage community discovery algorithm for multi-point seed prepartition was proposed. First， high-impact nodes in the network are identified， and high-impact nodes are aggregated using the k-means algorithm to obtain high-impact community clusters. Next， an attractiveness measurement function is proposed to selectively merge the remaining nodes in the network into the community cluster to complete the community identification task. The experimental results show that the two-stage community discovery method can find community structures with larger sizes and fewer numbers， and then capture the association between groups at the meso level.

Keywords：complex network; local community detection; seed expansion; node influence; K-means algorithm

0 引 言

現(xiàn)實(shí)世界的復(fù)雜網(wǎng)絡(luò)通?？梢猿橄鬄閳D模型，圖中節(jié)點(diǎn)代表現(xiàn)實(shí)世界的實(shí)體，兩個(gè)節(jié)點(diǎn)之間的鏈接代表實(shí)體之間的關(guān)系。社區(qū)[1]是復(fù)雜網(wǎng)絡(luò)中的稠密子圖，保證了社區(qū)內(nèi)部節(jié)點(diǎn)之間的鏈接較為緊密，社區(qū)之間節(jié)點(diǎn)的鏈接較為稀疏[2-5]。探索社區(qū)結(jié)構(gòu)有助于人們理解復(fù)雜網(wǎng)絡(luò)的自組織以及群聚特性，是復(fù)雜網(wǎng)絡(luò)中觀層次最重要的屬性之一。

從社區(qū)的層次化角度來(lái)看，已有的社區(qū)識(shí)別算法可分為全局優(yōu)化算法和局部?jī)?yōu)化算法兩種。前者在宏觀角度尋找社區(qū)結(jié)構(gòu)，描述了宏觀層面網(wǎng)絡(luò)節(jié)點(diǎn)的自組織特性，適合以數(shù)理統(tǒng)計(jì)為目的的網(wǎng)絡(luò)特征分析[1-2]。后者從微觀層面刻畫節(jié)點(diǎn)的局部?jī)A向性，更適合發(fā)現(xiàn)社區(qū)的演化規(guī)律及形成過(guò)程?；诜N子節(jié)點(diǎn)擴(kuò)張的社區(qū)發(fā)現(xiàn)算法[6]，就是局部?jī)?yōu)化算法的典型代表。

2009年，Lancichinetti等[7]提出重疊社區(qū)發(fā)現(xiàn)算法LFM，根據(jù)定義的自適應(yīng)函數(shù)Fitness進(jìn)行基于種子擴(kuò)張的社區(qū)識(shí)別。Coscia等[8]提出的DEMON算法以整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)為起始種子，利用標(biāo)簽傳播算法識(shí)別網(wǎng)絡(luò)中的局部社區(qū)結(jié)構(gòu)。Baumes等[9]提出一種鏈接聚合方法。先按照遞增或遞減原則對(duì)節(jié)點(diǎn)進(jìn)行排序，作為初始社區(qū)，如果節(jié)點(diǎn)的添加不能提高任何社區(qū)的密度，則該節(jié)點(diǎn)將作為新的種子節(jié)點(diǎn)，并生成新社區(qū)。李婕等[10]采用基于派系過(guò)濾的算法選擇種子節(jié)點(diǎn)進(jìn)行社區(qū)識(shí)別。Su等[11]基于隨機(jī)游走算法，使用緊密連接子圖作為社區(qū)識(shí)別的初始種子社區(qū)。

提高基于種子擴(kuò)張的社區(qū)識(shí)別性能的關(guān)鍵在于種子節(jié)點(diǎn)的選取，近年來(lái)有研究者提出借助影響力分析方法，增加初始種子節(jié)點(diǎn)位于社區(qū)內(nèi)核的概率。Clauset等[12]依次探索網(wǎng)絡(luò)節(jié)點(diǎn)，推斷給定節(jié)點(diǎn)所在社區(qū)。Luo等[13]將度的概念從單節(jié)點(diǎn)擴(kuò)展到子圖，在此基礎(chǔ)上給出了網(wǎng)絡(luò)模塊化的定義，以此進(jìn)行社區(qū)識(shí)別。Chen等[14]提出一種新的局部社區(qū)測(cè)度，先提取所有可能的候選社區(qū)，然后對(duì)社區(qū)層次進(jìn)行優(yōu)化。吳英俊等[15]提出LS算法，通過(guò)分析社區(qū)與節(jié)點(diǎn)之間的鏈接相似性來(lái)尋找局部社區(qū)結(jié)構(gòu)。Fanrong等[16]提出一種基于最大團(tuán)擴(kuò)展的局部社區(qū)檢測(cè)算法LCDMC，首先找到包含源節(jié)點(diǎn)的最大派系集合，然后利用貪婪優(yōu)化方法擴(kuò)展社區(qū)。Yao等[17]分析了高影響節(jié)點(diǎn)在社區(qū)檢測(cè)中的作用。齊金山等[18]提出了一種結(jié)合Jaccard系數(shù)的節(jié)點(diǎn)影響力計(jì)算公式，提高了算法對(duì)星形社區(qū)的匹配性。

上述社區(qū)識(shí)別方法雖然在特定領(lǐng)域具有一定的性能優(yōu)勢(shì)，但普遍存在以下兩方面問(wèn)題。首先，上述方法在種子選取時(shí)沒(méi)有考慮種子之間的關(guān)聯(lián)性，導(dǎo)致識(shí)別出社區(qū)結(jié)構(gòu)個(gè)數(shù)較多、穩(wěn)定性較差，不利于在中觀層面上挖掘群組之間的關(guān)聯(lián)性。其次，由于社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)的多樣性，上述方法在影響力識(shí)別時(shí)忽略了網(wǎng)絡(luò)的結(jié)構(gòu)特性，導(dǎo)致網(wǎng)絡(luò)中的高影響力節(jié)點(diǎn)呈現(xiàn)出較低的影響力評(píng)分的假象，這使得識(shí)別出的社區(qū)結(jié)構(gòu)較為松散，內(nèi)聚性較差。

為了解決上述問(wèn)題，提出一種多點(diǎn)種子預(yù)劃分的二階段社區(qū)發(fā)現(xiàn)算法（two-stage community detection algorithm，TSCDA），其創(chuàng)新之處主要體現(xiàn)在以下三方面。首先，在節(jié)點(diǎn)的影響力計(jì)算時(shí)融入邊介數(shù)屬性，增強(qiáng)節(jié)點(diǎn)影響力的結(jié)構(gòu)因素;其次，通過(guò)預(yù)劃分高影響力節(jié)點(diǎn)生成骨干網(wǎng)絡(luò)，增強(qiáng)種子的結(jié)構(gòu)密度;最后，以稠密子圖代替節(jié)點(diǎn)作為種子進(jìn)行擴(kuò)張，增加了社區(qū)結(jié)構(gòu)的穩(wěn)定性。仿真結(jié)果表明，TSCDA能夠挖掘出數(shù)量較少、規(guī)模較大的社區(qū)結(jié)構(gòu)，并在模塊度以及F-Score等指標(biāo)上表現(xiàn)出一定的性能優(yōu)勢(shì)。

1 基于節(jié)點(diǎn)影響力識(shí)別的種子節(jié)點(diǎn)選取方法

用無(wú)向圖G=（V，E）表示社交網(wǎng)絡(luò)，其中V代表網(wǎng)絡(luò)中個(gè)數(shù)為n的節(jié)點(diǎn)集合，E代表網(wǎng)絡(luò)中個(gè)數(shù)為m的鏈接關(guān)系集合。圖1給出了一種具有強(qiáng)聚合特性的社交網(wǎng)絡(luò)結(jié)構(gòu)（社區(qū)網(wǎng)絡(luò)）。

社會(huì)網(wǎng)絡(luò)中，節(jié)點(diǎn)u的鄰居集合定義為：

這里u和v代表網(wǎng)絡(luò)節(jié)點(diǎn)，V代表網(wǎng)絡(luò)中的節(jié)點(diǎn)集，如果u和v之間存在邊（u，v），則（u，v）屬于邊集E。節(jié)點(diǎn)u的節(jié)點(diǎn)度D（u）定義為與u直接相連的邊的個(gè)數(shù)（或鄰居元素的個(gè)數(shù)），滿足D（u）=|N（u）|。

為了在影響力計(jì)算中引入結(jié)構(gòu)的相似屬性，提出從節(jié)點(diǎn)相似性以及鏈接相似性雙重角度構(gòu)造影響力評(píng)價(jià)函數(shù)。

Jaccard系數(shù)Juv用于比較社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)之間的結(jié)構(gòu)相似性。其定義為：

N（u）和N（v）分別代表節(jié)點(diǎn)u和節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)。JuvJuv取值范圍為[0，1]，其值越大，節(jié)點(diǎn)u和節(jié)點(diǎn)v的共有鄰居節(jié)點(diǎn)就越多，鄰域結(jié)構(gòu)也就相對(duì)越稠密。

邊介數(shù)用來(lái)度量社會(huì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)間的最短路徑中經(jīng)過(guò)該邊的路徑的數(shù)目占最短路徑總數(shù)的比例。邊介數(shù)值越大，該邊越有可能成為連接社區(qū)內(nèi)部節(jié)點(diǎn)的重要途徑。其定義為：

其中g(shù)uvst表示網(wǎng)絡(luò)中任意節(jié)點(diǎn)s與任意節(jié)點(diǎn)t之間的最短路徑同時(shí)經(jīng)過(guò)節(jié)點(diǎn)u和v（即邊euv）的條數(shù)。根據(jù)式（3），可以計(jì)算出圖1各邊的邊介數(shù)指數(shù)，例如節(jié)點(diǎn)8和節(jié)點(diǎn)10，即（e8，10）之間邊強(qiáng)度為EBET（e8，9）=11;節(jié)點(diǎn)9和節(jié)點(diǎn)10，即（e9，10）之間邊強(qiáng)度為EBET（e9，10）=11。邊介數(shù)反映了社區(qū)內(nèi)部鏈接的稠密程度，是增加社區(qū)穩(wěn)定性的關(guān)鍵參數(shù)。

受牛頓萬(wàn)有引力定律的啟發(fā)，提出一種基于Jaccard系數(shù)以及邊介數(shù)的影響力計(jì)算方法。社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)u對(duì)節(jié)點(diǎn)v的影響力評(píng)分定義為：

這里D（u）和D（v）分別表示節(jié)點(diǎn)u和節(jié)點(diǎn)v的度。由于節(jié)點(diǎn)度在局部環(huán)境反映了節(jié)點(diǎn)鏈接能力，因此在本文中被用來(lái)衡量社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)的質(zhì)量。節(jié)點(diǎn)之間的距離d（u，v）用節(jié)點(diǎn)間的相異程度加以衡量，滿足d（u，v）=1-Juv。其中Juv代表節(jié)點(diǎn)u和節(jié)點(diǎn)v的Jaccard相似度。G是影響力常量，在實(shí)驗(yàn)中通常取值為1。

節(jié)點(diǎn)在局部社區(qū)的影響力評(píng)分Iscore（u）定義為該節(jié)點(diǎn)對(duì)其所有鄰居的節(jié)點(diǎn)影響力評(píng)分之和。進(jìn)而有：

式（5）中，v∈N（u）表明節(jié)點(diǎn)v是節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)。Iscore（u）的值越大，說(shuō)明節(jié)點(diǎn)u在局部環(huán)境的影響強(qiáng)度越大，表明越有可能成為種子節(jié)點(diǎn)。根據(jù)式（5），可以計(jì)算出圖1各節(jié)點(diǎn)的影響力分?jǐn)?shù)。例如節(jié)點(diǎn)10的影響力分?jǐn)?shù)：

因此節(jié)點(diǎn)10在網(wǎng)絡(luò)中影響力分?jǐn)?shù)Iscore（u10）=275。

下面給出基于節(jié)點(diǎn)影響力識(shí)別的種子節(jié)點(diǎn)選取過(guò)程。算法通過(guò)式（5）計(jì)算社會(huì)網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)的影響力評(píng)分。其偽代碼如下：

算法1 具有高影響力的初始種子選取算法

輸入：社會(huì)網(wǎng)絡(luò)G=（V，E）

輸出：高質(zhì)量節(jié)點(diǎn)集合S

1）初始化集合S為空集;

2）遍歷社會(huì)網(wǎng)絡(luò)的所有節(jié)點(diǎn)，根據(jù)公式（5）計(jì)算社會(huì)網(wǎng)絡(luò)所有節(jié)點(diǎn)的節(jié)點(diǎn)影響力評(píng)分;

3）對(duì)于任意節(jié)點(diǎn)，如果它的影響力評(píng)分大于其任一鄰居的影響力評(píng)分，則為高影響力種子節(jié)點(diǎn)，將其存儲(chǔ)到集合S;

4）輸出集合S。

根據(jù)算法1，計(jì)算圖1中節(jié)點(diǎn)1到節(jié)點(diǎn)10的影響力評(píng)分，具體如表1所示。在本文中，如果一個(gè)節(jié)點(diǎn)的影響力分?jǐn)?shù)大于其任一鄰居的影響力評(píng)分，則為高影響種子節(jié)點(diǎn)。例如，節(jié)點(diǎn)8的鄰居節(jié)點(diǎn)為6，7，9，10。通過(guò)表1可知，節(jié)點(diǎn)8的影響力評(píng)分大于節(jié)點(diǎn)6，7，9，10的影響力評(píng)分，因此節(jié)點(diǎn)8為高影響力節(jié)點(diǎn)。

2 多點(diǎn)種子預(yù)劃分的二階段社區(qū)發(fā)現(xiàn)算法

本節(jié)給出多點(diǎn)種子預(yù)劃分的二階段社區(qū)發(fā)現(xiàn)算法。首先，根據(jù)算法1選取網(wǎng)絡(luò)中的高影響力種子節(jié)點(diǎn)，對(duì)這些節(jié)點(diǎn)利用K-means聚類算法進(jìn)行初始劃分，識(shí)別出由高質(zhì)量節(jié)點(diǎn)組成的種子社區(qū)即骨干社區(qū);然后提出一種基于吸引力度量的社區(qū)識(shí)別算法將社會(huì)網(wǎng)絡(luò)中其余節(jié)點(diǎn)按特定規(guī)則有選擇性的加入骨干社區(qū)中，從而完成社區(qū)劃分。該方法的優(yōu)勢(shì)在于充分考慮了種子節(jié)點(diǎn)之間稠密性以及關(guān)聯(lián)性，有助于提高社區(qū)的穩(wěn)定程度。

2.1 基于K-means聚類的骨干社區(qū)識(shí)別

本文采用K-means算法作為骨干社區(qū)的初始化算法，其距離度量公式在式（7）給出。

式中：minDis（A，B）為在社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)A，B間最短路徑長(zhǎng)度;comNeighbor（A，B）為節(jié)點(diǎn)A，B間共同鄰居數(shù)量;C為迭代中心，初始值為0;Dis（A，B）為A、B兩點(diǎn)的距離，該值與A、B兩點(diǎn)的最短路徑長(zhǎng)度呈正相關(guān)，與A、B兩點(diǎn)的共同鄰居數(shù)量呈負(fù)相關(guān)。

K-means算法在迭代時(shí)依靠簇內(nèi)所有節(jié)點(diǎn)的平均坐標(biāo)設(shè)定新中心。然而社區(qū)不存在坐標(biāo)，因此需要重新定義中心選取方式。本文選取到簇內(nèi)其他節(jié)點(diǎn)的距離之和最小的節(jié)點(diǎn)作為新的中心節(jié)點(diǎn)，具體如式（8）所示。

式中：N（i）表示第i個(gè)社區(qū)內(nèi)的節(jié)點(diǎn)集合。K-means算法的最終輸出1棵骨干社區(qū)層次化樹，采用模塊度函數(shù)在層次化樹上進(jìn)行分割，獲取質(zhì)量最高的社區(qū)劃分。模塊度函數(shù)Q是Newman[19]在2004年提出的概念，用以評(píng)價(jià)社區(qū)劃分的質(zhì)量，其定義為：

式中：eii代表社區(qū)i中邊的期望;ai代表鏈接到社區(qū)i中的邊數(shù)的期望。模塊度的形式化定義是社區(qū)內(nèi)的邊數(shù)減去隨機(jī)產(chǎn)生的邊的期望，因此模塊度越高，社區(qū)內(nèi)外邊比例就越大，社區(qū)劃分結(jié)果就越好。

我們發(fā)現(xiàn)，算法在層次聚類時(shí)模塊度函數(shù)Q的取值并不是單調(diào)遞增或單調(diào)遞減的，因此每當(dāng)有社區(qū)進(jìn)行合并操作，就需要重新計(jì)算Q值，能對(duì)產(chǎn)生最大Q值的兩個(gè)社區(qū)合并。為簡(jiǎn)化計(jì)算，每次僅計(jì)

算Q的變化部分，即向Q值增大最多或者減少最小的方向進(jìn)行社區(qū)合并。Q函數(shù)的變化量計(jì)算公式如下所示。

對(duì)能產(chǎn)生最大Q值的兩社區(qū)進(jìn)行合并，直到所有節(jié)點(diǎn)合并至同一社區(qū)。算法的偽代碼如下：

算法2 利用K-means聚類算法實(shí)現(xiàn)種子節(jié)點(diǎn)初始劃分

輸入：3個(gè)種子節(jié)點(diǎn)集合，社會(huì)網(wǎng)絡(luò)G

輸出：骨干社區(qū)集合BC={BC1，BC2，…BCn}

1）選取這3個(gè)種子節(jié)點(diǎn)進(jìn)行初始聚類;

2）根據(jù)距離度量式（7）計(jì)算任意兩節(jié)點(diǎn)之間的距離;

3）比較任意兩點(diǎn)間的距離，將節(jié)點(diǎn)劃分至距離最近的節(jié)點(diǎn)簇內(nèi);

4）對(duì)于每個(gè)簇內(nèi)，分別計(jì)算簇內(nèi)每個(gè)節(jié)點(diǎn)與簇內(nèi)的其他節(jié)點(diǎn)距離之和，取和最小的節(jié)點(diǎn)作為新的中心節(jié)點(diǎn);

5）迭代步驟4）、5），直到中心節(jié)點(diǎn)不發(fā)生改變;

6）對(duì)K-means算法產(chǎn)生的社區(qū)按照式（10）計(jì)算兩兩之間合并產(chǎn)生的ΔQ，將使ΔQ增加或減少的兩個(gè)社區(qū)進(jìn)行合并，并按照式（9）計(jì)算當(dāng)前Q值，保存Q值及當(dāng)前社區(qū)劃分;

7）對(duì)步驟7）進(jìn)行迭代，直到所有節(jié)點(diǎn)都包含在一個(gè)社區(qū)或不能進(jìn)行社區(qū)合并;

8）比較每次合并的Q值大小，取Q值最大的社區(qū)作為最終的結(jié)果。

2.2 基于吸引力度量的社區(qū)識(shí)別過(guò)程

算法2結(jié)束后，會(huì)對(duì)社會(huì)網(wǎng)絡(luò)中影響力較高的前3個(gè)節(jié)點(diǎn)進(jìn)行預(yù)劃分，識(shí)別出由高影響力節(jié)點(diǎn)組成的種子社區(qū)即為骨干社區(qū)。而網(wǎng)絡(luò)中影響力較低的n-3個(gè)零散節(jié)點(diǎn)可能處于孤立狀態(tài)，因此需要將其合并到骨干社區(qū)之中。提出一種基于影響力分析的吸引力度量函數(shù)，將網(wǎng)絡(luò)中零散節(jié)點(diǎn)添加到對(duì)其吸引力較高的骨干社區(qū)。對(duì)于任意骨干社區(qū)BC和節(jié)點(diǎn)u，BC對(duì)u的吸引力度量函數(shù)attract（BC，u）的定義為：

式中：∑v∈BC∧v∈N（u）NG（u，v）表示節(jié)點(diǎn)u對(duì)當(dāng)前所在骨干社區(qū)的所有鄰居節(jié)點(diǎn)的影響力評(píng)分?jǐn)?shù)之和;Iscore（u）表示節(jié)點(diǎn)u的影響力評(píng)分。attract（BC，u）的值越大，節(jié)點(diǎn)u受骨干社區(qū)BC吸引而加入社區(qū)BC的可能性就越大，反之節(jié)點(diǎn)u成為骨干社區(qū)BC內(nèi)部節(jié)點(diǎn)的概率較低。

設(shè)定了吸引力閾值β，對(duì)于節(jié)點(diǎn)u以及任意社區(qū)BC，若attract（BC，u）>β，則節(jié)點(diǎn)u屬于骨干社區(qū)BC。節(jié)點(diǎn)u可能同時(shí)加入多個(gè)社區(qū)結(jié)構(gòu)，因此社區(qū)具有重疊性。在圖1中，假設(shè)骨干社區(qū)BC1包含的節(jié)點(diǎn)集合為{1，2，3，4，5}，骨干社區(qū)BC1對(duì)節(jié)點(diǎn)6的吸引力函數(shù)為：

假設(shè)BC2的骨干社區(qū)包含節(jié)點(diǎn)集合為{7，8，9，10}，骨干社區(qū)BC2對(duì)節(jié)點(diǎn)6的吸引力為：

若β=0.4，則節(jié)點(diǎn)6不屬于骨干社區(qū)BC1，屬于骨干社區(qū)BC2。

下面給出基于種子擴(kuò)張的社區(qū)發(fā)現(xiàn)算法，算法的偽代碼如下：

算法3 基于種子擴(kuò)張的社區(qū)發(fā)現(xiàn)算法

輸入：高影響力節(jié)點(diǎn)構(gòu)成的社區(qū)集合BC，社區(qū)網(wǎng)絡(luò)G

輸出：社區(qū)劃分結(jié)構(gòu)

1）將網(wǎng)絡(luò)中高影響力節(jié)點(diǎn)標(biāo)記為true，其余n-3個(gè)節(jié)點(diǎn)標(biāo)記為false;

2）將網(wǎng)絡(luò)中標(biāo)記為false的節(jié)點(diǎn)按照式（11）依次對(duì)骨干社區(qū)集合BC={BC1，BC2…BCn}進(jìn)行計(jì)算;

3）對(duì)每個(gè)標(biāo)記為false的節(jié)點(diǎn)按照不同的骨干社區(qū)的計(jì)算，選取attract（BC，u）最大的值并將該節(jié)點(diǎn)加入到對(duì)應(yīng)的骨干網(wǎng)絡(luò);

4）將加入骨干社區(qū)網(wǎng)絡(luò)的節(jié)點(diǎn)標(biāo)記為true;

5）重復(fù)執(zhí)行步驟2），步驟3）和步驟4），直到社區(qū)網(wǎng)絡(luò)中所有節(jié)點(diǎn)都標(biāo)記為true;

6）輸出社區(qū)劃分結(jié)構(gòu)。

為了挖掘網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，首先將網(wǎng)絡(luò)除3個(gè)高影響力節(jié)點(diǎn)外的節(jié)點(diǎn)都標(biāo)記為false，若節(jié)點(diǎn)劃分到一個(gè)社區(qū)中，則該節(jié)點(diǎn)標(biāo)記為ture。

在基于吸引力度量的種子擴(kuò)張過(guò)程的偽代碼中，第一步為遍歷n個(gè)高影響力評(píng)分節(jié)點(diǎn)社區(qū)集合。第二步以及第三步為計(jì)算集合BCi中對(duì)n-3吸引度量函數(shù)值attract（BCi，v）不小于給定的閾值β的節(jié)點(diǎn)。若節(jié)點(diǎn)attract（BCi，v）值大于或等于閾值，將該節(jié)點(diǎn)合并到當(dāng)前的社區(qū)中，若一個(gè)節(jié)點(diǎn)屬于多個(gè)社區(qū)，則稱該節(jié)點(diǎn)為重疊節(jié)點(diǎn)。將該節(jié)點(diǎn)加入到attract（BCi，v）值最大的骨干社區(qū)中。最后將加入骨干社區(qū)的節(jié)點(diǎn)標(biāo)記為true，得到最終的社區(qū)結(jié)構(gòu)劃分結(jié)果。社區(qū)合并本質(zhì)上是一種貪心策略，然而由于網(wǎng)絡(luò)本身存在稀疏性，在實(shí)際的種子擴(kuò)張中零散節(jié)點(diǎn)鄰接社區(qū)要遠(yuǎn)小于其鄰接的社區(qū)數(shù)，這有效的控制了算法的時(shí)間開(kāi)銷。

2.3 算法的時(shí)間復(fù)雜度分析

假設(shè)社會(huì)網(wǎng)絡(luò)G包含有n個(gè)節(jié)點(diǎn)和m條邊，算法1在求解節(jié)點(diǎn)的影響力強(qiáng)度時(shí)，時(shí)間復(fù)雜度為O（n）。在算法2中基于K-means聚類算法將O（l）個(gè)節(jié)點(diǎn)進(jìn)行合并得出骨干網(wǎng)絡(luò)，其時(shí)間復(fù)雜度為O（kl），最壞的情況下將O（n）個(gè)節(jié)點(diǎn)進(jìn)行合并，故算法2的時(shí)間復(fù)雜度為O（kn）。在算法3中，在社區(qū)擴(kuò)展階段將O（n）個(gè)節(jié)點(diǎn)加入到O（k）個(gè)骨干社區(qū)中，該過(guò)程重復(fù)執(zhí)行O（n）次，所以找到所有的最終社區(qū)的時(shí)間復(fù)雜度為O（kn2），若k<

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

本節(jié)給出算法在人工合成網(wǎng)絡(luò)以及真實(shí)數(shù)據(jù)集上的運(yùn)行結(jié)果。實(shí)驗(yàn)的運(yùn)行環(huán)境為Intel Core i5-7300HQ 2.5GHz處理器，8GB內(nèi)存，Windows 10操作系統(tǒng)，算法采用Python與Matlab R2016a混合編程。

3.1 NMI指數(shù)

Danon等[20]提出歸一化互信息（normalized mutual information，NMI），度量社區(qū)集合之間的相似性。NMI基于混淆矩陣N，其中行表示真實(shí)的社區(qū)結(jié)構(gòu)，列表示算法生成的社區(qū)。Ni表示矩陣N第i行所有元素的總和，Nj表示矩陣N第j列所有元素的總和。Nij是矩陣N的元素，表示同時(shí)屬于真實(shí)社區(qū)i和算法生成社區(qū)j的節(jié)點(diǎn)數(shù)量。NMI公式定義為：

式中：CA代表網(wǎng)絡(luò)中真實(shí)社區(qū)的數(shù)量;CB代表由算法生成社區(qū)的數(shù)量。如果探測(cè)出的社區(qū)結(jié)構(gòu)和真實(shí)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)相同則NMI=1;反之，如果所探測(cè)的社區(qū)結(jié)構(gòu)和真實(shí)網(wǎng)絡(luò)完全不同，則NMI=0。傳統(tǒng)意義上的歸一化互信息被用來(lái)量化兩個(gè)分布之間的差異性，為了使之適用于社區(qū)差異性量化，實(shí)驗(yàn)中采用的了NMI的簡(jiǎn)化版本[21]。

3.2 F-SCORE

F-Score也是常用的社區(qū)發(fā)現(xiàn)算法度量指標(biāo)。首先定義算法生成社區(qū)在全部社區(qū)中的比例。

式中，CR代表高質(zhì)量節(jié)點(diǎn)所在的真實(shí)社區(qū)，CF代表高質(zhì)量節(jié)點(diǎn)所在的探測(cè)社區(qū)。

Precision是正確劃分節(jié)點(diǎn)的數(shù)量除以節(jié)點(diǎn)在CF中的數(shù)量，其定義為：

結(jié)合式（15）以及式（16），F(xiàn)-Score定義為：

3.3 人工合成網(wǎng)絡(luò)社區(qū)識(shí)別結(jié)果

利用LFR-Benchmark提供的MATLAB數(shù)據(jù)生成器生成網(wǎng)絡(luò)，網(wǎng)絡(luò)中的部分重要參數(shù)設(shè)置如下。首先，生成網(wǎng)絡(luò)規(guī)模為N=1 000的復(fù)雜網(wǎng)絡(luò)，其中最小社區(qū)尺寸為10、最大社區(qū)尺寸為100。接下來(lái)設(shè)置網(wǎng)絡(luò)的平均度為5、最大節(jié)點(diǎn)度為25、混合參數(shù)u的取值范圍為0.1～0.8。在LFR Benchmark中，混合參數(shù)是一個(gè)獨(dú)立參數(shù)，其值越大社區(qū)越難以發(fā)現(xiàn)，因此通常用來(lái)刻畫算法的魯棒性。

首先驗(yàn)證了不同混合參數(shù)下K-means聚類算法中的k取值不同時(shí)NMI指標(biāo)變化情況，實(shí)驗(yàn)結(jié)果如圖2所示?？梢钥闯觯跏紩r(shí)社區(qū)質(zhì)量會(huì)隨種子社區(qū)的不斷增多而不斷上升，但達(dá)到某一極值時(shí)，社區(qū)質(zhì)量開(kāi)始下降。這是因?yàn)槌跏挤N子過(guò)多會(huì)導(dǎo)致社區(qū)個(gè)數(shù)增加，進(jìn)而降低社區(qū)內(nèi)部的緊密程度。另一個(gè)發(fā)現(xiàn)是，社區(qū)結(jié)構(gòu)較為模糊的網(wǎng)絡(luò)中（u=0.8），需要更多的種子社區(qū)才能達(dá)到較好的發(fā)現(xiàn)效果。

接下來(lái)，驗(yàn)證TSCDA算法的性能。與Clauset[12]、LWP[13]、Chen[14]、LS[15]、LCDMC[16]以及VI[17]6種社區(qū)識(shí)別算法在人工合成網(wǎng)絡(luò)社區(qū)進(jìn)行比較，為了保證算法結(jié)果的客觀性，將相關(guān)參數(shù)按原有文獻(xiàn)加以設(shè)定，算法的NMI指標(biāo)以及F-Score在圖3以及圖4給出。

如圖2及圖3所示，當(dāng)混合參數(shù)u等于0.1時(shí)，TSCDA在NMI以及F-Score的性能指標(biāo)明顯優(yōu)于其它算法，具有一定的性能優(yōu)勢(shì)。隨著混合參數(shù)u的不斷增加，TSCDA算法和其他6種算法的NMI指標(biāo)以及F-Score均呈現(xiàn)明顯的下降趨勢(shì)，當(dāng)混合參數(shù)u等于0.5以及0.6時(shí)，TSCDA算法略優(yōu)于VI算法和LCDMC算法，優(yōu)于LWP以及LS算法;當(dāng)混合參數(shù)u等于0.7以及0.8時(shí)，各算法性能較為接近，但總體來(lái)看，TSCDA算法仍然要優(yōu)于其他6種社區(qū)識(shí)別方法，這表明TSCDA算法在結(jié)構(gòu)指標(biāo)上更貼近于內(nèi)嵌社區(qū)。

3.4 真實(shí)網(wǎng)絡(luò)社區(qū)識(shí)別結(jié)果

為了驗(yàn)證TSCDA算法在真實(shí)網(wǎng)絡(luò)社區(qū)識(shí)別的性能，本節(jié)選取了在5種真實(shí)網(wǎng)絡(luò)上，對(duì)比TSCDA算法與前文6種社區(qū)識(shí)別算法的性能差異。表2列出了所選擇的真實(shí)網(wǎng)絡(luò)的網(wǎng)絡(luò)特征，其中Node代表節(jié)點(diǎn)個(gè)數(shù)、Link代表鏈接條數(shù)、d—表示網(wǎng)絡(luò)的平均度、|C—|表示真實(shí)社區(qū)的平均大小、Community表示社區(qū)個(gè)數(shù)。我們從Amazon社區(qū)中移除了前5 000個(gè)子社區(qū)，保留了它的不同的社區(qū)。

還在DBLP計(jì)算機(jī)學(xué)科文獻(xiàn)數(shù)據(jù)網(wǎng)絡(luò)上測(cè)試了TSCDA算法與Clauset算法、LWP算法、Chen算法、LS算法、LCDMC算法以及VI算法的NMI指標(biāo)以及F-Score指標(biāo)。DBLP文獻(xiàn)網(wǎng)絡(luò)的特性如表3所示。|C|代表社區(qū)規(guī)模的范圍，例如，（0，10]代表樣本網(wǎng)絡(luò)包含的社區(qū)大小大于0，小于等于10。我們同樣移除了DBLP網(wǎng)絡(luò)前5 000個(gè)社區(qū)中的子社區(qū)，并保留了它們不同的社區(qū)結(jié)構(gòu)。

表4給出了各算法在真實(shí)網(wǎng)絡(luò)上的NMI指標(biāo)以及F-Score指標(biāo)。相比其它6種方法，TSCDA具有一定的性能優(yōu)勢(shì)。一方面，TSCDA基于節(jié)點(diǎn)影響力擴(kuò)展社區(qū)，因此在識(shí)別社區(qū)成員時(shí)準(zhǔn)確度更高。另一方面，本文在節(jié)點(diǎn)影響力計(jì)算中加入了邊介數(shù)屬性，不僅考慮了節(jié)點(diǎn)自身的重要程度，還考慮了鏈接在局部區(qū)域中的重要程度。LWP和LS算法在個(gè)別網(wǎng)絡(luò)中顯示出比TSCDA更好的性能，例如在Football網(wǎng)絡(luò)中LWP算法的NMI指標(biāo)高于TSCDA約0.09、在Amazon網(wǎng)絡(luò)中LS算法的F-Score高于TSCDA約0.02。一個(gè)可能的原因是Football網(wǎng)絡(luò)的平均節(jié)點(diǎn)度較高，使得各算法在社區(qū)識(shí)別時(shí)更容易發(fā)現(xiàn)結(jié)構(gòu)較為緊湊的局部結(jié)構(gòu)。TSCDA算法在Dolpins網(wǎng)的準(zhǔn)確性有所下降，這是由于Dolpins網(wǎng)絡(luò)中的鏈接關(guān)系依靠于節(jié)點(diǎn)之間的接觸歷史，因此影響力識(shí)別時(shí)準(zhǔn)確度一般。但是相比其它6種算法TSCDA算法仍然表現(xiàn)出一定的穩(wěn)定性，進(jìn)一步說(shuō)明了TSCDA算法具有較高的魯棒性。

圖5和圖6給出了各算法在DBLP引文網(wǎng)絡(luò)上的性能指標(biāo)。實(shí)驗(yàn)結(jié)果顯示，當(dāng)社區(qū)規(guī)模在0到10時(shí)（Label 0），TSCDA在社區(qū)識(shí)別性能上略低于其他6種算法表現(xiàn)的差。然而當(dāng)社區(qū)規(guī)模大于10時(shí)（Label 1～10），TSCDA的表現(xiàn)性能明顯優(yōu)于Clauset、LWP、Chen、LS、LCDMC和VI算法，這表明TSCDA善于挖掘個(gè)數(shù)較多的社區(qū)結(jié)果，社區(qū)粒度更加細(xì)致。

4 結(jié) 論

為了解決傳統(tǒng)社區(qū)識(shí)別方法社區(qū)穩(wěn)定性較差這一問(wèn)題，從節(jié)點(diǎn)相似性以及鏈接相似性兩個(gè)角度入手，提出一種多點(diǎn)種子預(yù)劃分的社區(qū)發(fā)現(xiàn)算法TSCDA。首先，在種子擴(kuò)張算法的基礎(chǔ)上，提出利用高質(zhì)量節(jié)點(diǎn)構(gòu)建骨干社區(qū)進(jìn)行社區(qū)識(shí)別，提高社區(qū)結(jié)構(gòu)的致密性;其次，將邊介數(shù)屬性加入到節(jié)點(diǎn)影響力的計(jì)算中，提高影響力計(jì)算中的結(jié)構(gòu)相關(guān)性。人工合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的仿真結(jié)果驗(yàn)證了TSCDA算法的效率和識(shí)別性能。

參 考 文 獻(xiàn)：

[1] SANTO Fortunato. Community Detection in Graphs[J]. Physics Reports，2009，486（3）：26.

[2] JAVED M A， YOUNIS M S， LATIF S， et al. Community Detection in Networks：A Multidisciplinary Review[J]. Journal of Network and Computer Applications，2018， 108：87.

[3] AMOR B， VUIK S， CALLAHAN R， et al. Community Detection and Role Identification in Directed Networks： Understanding the Twitter Network of the Caredata Debate[J]. Dynamic Networks and Cyber-security， 2015， 25（2）：19.

[4] BAZZI M， PORTER M A， WILLIAMS S， et al. Community Detection in Temporal Multilayer Networks， with an Application to Correlation Networks[J]. Multiscale Modeling & Simulation， 2016， 14（1）：1.

[5] SHARMA S， SINGH A. An Efficient Method for Link Prediction in Complex Multiplex Networks[C]// 2015 11th International Conference on Signal-Image Technology & Internet-Based Systems（SITIS）. IEEE， 2015：452.

[6] DING X， ZHANG J， YANG J. A Robust Two-stage Algorithm for Local Community Detection[J]. Knowledge Based Systems， 2018， 14（7）：62.

[7] LANCICHINETTI A， FORTUNATO S， KERTSZ， JNOS. Detecting the Overlapping and Hierarchical Community Structure in Complex Networks[J]. New Journal of Physics， 2009， 11（3）：15.

[8] COSCIA M， ROSSETTI G， GIANNOTTI F， et al. DEMON：a Local-First Discovery Method for Overlapping Communities[C]// Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2012：19.

[9] BAUMES J， GOLDBERG M， MAGDON-ISMAIL M. Efficient Identification of Overlapping Communities[C]// International Conference on Intelligence and Security Informatics， 2005：11.

[10]李婕， 王興偉， 郭靜， 等. 面向移動(dòng)通信網(wǎng)絡(luò)的局部擴(kuò)張群組構(gòu)造方法[J]. 東北大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，38（12）：1691.

LI Jie， WANG Xingwei， GUO Jing， et al. Clique Percolation Based Local Fitness Method for User Clustering in Telecommunication Network[J]. Journal of Northeastern University Natural（Science）， 2017，38（12）：1691.

[11]SU Y， WANG B， CHENG F， et al. An Algorithm Based on Positive and Negative Links for Community Detection in Signed Networks[J]. Scientific Reports， 2017， 7（1）：10874.

[12]CLAUSET， ARON. Finding Local Community Structure in Networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics， 2005， 72（2）：26.

[13]LUO F ， WANG J Z ， PROMISLOW E. Exploring Local Community Structures in Large Networks[J]. Web Intelligence & Agent Systems， 2008， 6（4）：387.

[14]JIYANG Chen， OSMAR Zaane， RANDY Goebel. Local Community Identification in Social Networks[C]// International Conference on Advances in Social Network Analysis & Mining. IEEE Computer Society， 2009：79.

[15]YING JUN， WU， HAN， et al. Local Community Detection Using Link Similarity[J]. Journal of Computer Science & Technology， 2012， 23（3）：69.

[16]FANRONG M ， MU Z ， YONG Z ， et al. Local Community Detection in Complex Networks Based on Maximum Cliques Extension[J]. Mathematical Problems in Engineering， 2014， 36（6）：1.

[17]YAOY ， WU W ， LEI M ， et al. Community Detection Based on Variable Vertex Influence[C]// IEEE International Conference on Data Science in Cyberspace. IEEE， 2016：145.

[18]齊金山， 梁循， 王怡. 基于種子節(jié)點(diǎn)選擇的重疊社區(qū)發(fā)現(xiàn)算法[J]. 計(jì)算機(jī)應(yīng)用研究，2017（12）：20.

QI Jinshan， LIANG Xun， WANG Yi. Overlapping Community Detection Algorithm Based on Selection of Seed Nodes[J]. Application Research of Computers，2017（12）：20.

[19]NEWMANM E J. Fast Algorithm for Detecting Community Structure in Networks[J]. Physical Review E， 2004， 69（6）：133.

[20]DANON， LEON， DUCH， et al. Comparing Community Structure Identification[J]. Journal of Statistical Mechanics， 2005， 206（9）：69.

[21]BAGROW， JAMES P. Evaluating Local Community Methods in Networks[J]. Journal of Statistical Mechanics：Theory and Experiment， 2008， 8（5）：26.

（編輯：溫澤宇）