多點種子預劃分的二階段社區發現算法

佟帥 陳德運 楊海陸

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

關鍵詞：復雜網絡;局部社區發現;種子擴張;節點影響力;K-means算法

DOI：10.15938/j.jhust.2021.04.011

中圖分類號：TP391.4

文獻標志碼：A

文章編號：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 引 言

現實世界的復雜網絡通常可以抽象為圖模型，圖中節點代表現實世界的實體，兩個節點之間的鏈接代表實體之間的關系。社區[1]是復雜網絡中的稠密子圖，保證了社區內部節點之間的鏈接較為緊密，社區之間節點的鏈接較為稀疏[2-5]。探索社區結構有助于人們理解復雜網絡的自組織以及群聚特性，是復雜網絡中觀層次最重要的屬性之一。

從社區的層次化角度來看，已有的社區識別算法可分為全局優化算法和局部優化算法兩種。前者在宏觀角度尋找社區結構，描述了宏觀層面網絡節點的自組織特性，適合以數理統計為目的的網絡特征分析[1-2]。后者從微觀層面刻畫節點的局部傾向性，更適合發現社區的演化規律及形成過程。基于種子節點擴張的社區發現算法[6]，就是局部優化算法的典型代表。

2009年，Lancichinetti等[7]提出重疊社區發現算法LFM，根據定義的自適應函數Fitness進行基于種子擴張的社區識別。Coscia等[8]提出的DEMON算法以整個網絡節點為起始種子，利用標簽傳播算法識別網絡中的局部社區結構。Baumes等[9]提出一種鏈接聚合方法。先按照遞增或遞減原則對節點進行排序，作為初始社區，如果節點的添加不能提高任何社區的密度，則該節點將作為新的種子節點，并生成新社區。李婕等[10]采用基于派系過濾的算法選擇種子節點進行社區識別。Su等[11]基于隨機游走算法，使用緊密連接子圖作為社區識別的初始種子社區。

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

上述社區識別方法雖然在特定領域具有一定的性能優勢，但普遍存在以下兩方面問題。首先，上述方法在種子選取時沒有考慮種子之間的關聯性，導致識別出社區結構個數較多、穩定性較差，不利于在中觀層面上挖掘群組之間的關聯性。其次，由于社會網絡結構的多樣性，上述方法在影響力識別時忽略了網絡的結構特性，導致網絡中的高影響力節點呈現出較低的影響力評分的假象，這使得識別出的社區結構較為松散，內聚性較差。

為了解決上述問題，提出一種多點種子預劃分的二階段社區發現算法（two-stage community detection algorithm，TSCDA），其創新之處主要體現在以下三方面。首先，在節點的影響力計算時融入邊介數屬性，增強節點影響力的結構因素;其次，通過預劃分高影響力節點生成骨干網絡，增強種子的結構密度;最后，以稠密子圖代替節點作為種子進行擴張，增加了社區結構的穩定性。仿真結果表明，TSCDA能夠挖掘出數量較少、規模較大的社區結構，并在模塊度以及F-Score等指標上表現出一定的性能優勢。

1 基于節點影響力識別的種子節點選取方法

用無向圖G=（V，E）表示社交網絡，其中V代表網絡中個數為n的節點集合，E代表網絡中個數為m的鏈接關系集合。圖1給出了一種具有強聚合特性的社交網絡結構（社區網絡）。

社會網絡中，節點u的鄰居集合定義為：

這里u和v代表網絡節點，V代表網絡中的節點集，如果u和v之間存在邊（u，v），則（u，v）屬于邊集E。節點u的節點度D（u）定義為與u直接相連的邊的個數（或鄰居元素的個數），滿足D（u）=|N（u）|。

為了在影響力計算中引入結構的相似屬性，提出從節點相似性以及鏈接相似性雙重角度構造影響力評價函數。

Jaccard系數Juv用于比較社會網絡中節點之間的結構相似性。其定義為：

N（u）和N（v）分別代表節點u和節點v的鄰居節點。JuvJuv取值范圍為[0，1]，其值越大，節點u和節點v的共有鄰居節點就越多，鄰域結構也就相對越稠密。

邊介數用來度量社會網絡中所有節點間的最短路徑中經過該邊的路徑的數目占最短路徑總數的比例。邊介數值越大，該邊越有可能成為連接社區內部節點的重要途徑。其定義為：

其中guvst表示網絡中任意節點s與任意節點t之間的最短路徑同時經過節點u和v（即邊euv）的條數。根據式（3），可以計算出圖1各邊的邊介數指數，例如節點8和節點10，即（e8，10）之間邊強度為EBET（e8，9）=11;節點9和節點10，即（e9，10）之間邊強度為EBET（e9，10）=11。邊介數反映了社區內部鏈接的稠密程度，是增加社區穩定性的關鍵參數。

受牛頓萬有引力定律的啟發，提出一種基于Jaccard系數以及邊介數的影響力計算方法。社會網絡節點u對節點v的影響力評分定義為：

這里D（u）和D（v）分別表示節點u和節點v的度。由于節點度在局部環境反映了節點鏈接能力，因此在本文中被用來衡量社會網絡節點的質量。節點之間的距離d（u，v）用節點間的相異程度加以衡量，滿足d（u，v）=1-Juv。其中Juv代表節點u和節點v的Jaccard相似度。G是影響力常量，在實驗中通常取值為1。

節點在局部社區的影響力評分Iscore（u）定義為該節點對其所有鄰居的節點影響力評分之和。進而有：

式（5）中，v∈N（u）表明節點v是節點u的鄰居節點。Iscore（u）的值越大，說明節點u在局部環境的影響強度越大，表明越有可能成為種子節點。根據式（5），可以計算出圖1各節點的影響力分數。例如節點10的影響力分數：

因此節點10在網絡中影響力分數Iscore（u10）=275。

下面給出基于節點影響力識別的種子節點選取過程。算法通過式（5）計算社會網絡每個節點的影響力評分。其偽代碼如下：

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

輸入：社會網絡G=（V，E）

輸出：高質量節點集合S

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

2）遍歷社會網絡的所有節點，根據公式（5）計算社會網絡所有節點的節點影響力評分;

3）對于任意節點，如果它的影響力評分大于其任一鄰居的影響力評分，則為高影響力種子節點，將其存儲到集合S;

4）輸出集合S。

根據算法1，計算圖1中節點1到節點10的影響力評分，具體如表1所示。在本文中，如果一個節點的影響力分數大于其任一鄰居的影響力評分，則為高影響種子節點。例如，節點8的鄰居節點為6，7，9，10。通過表1可知，節點8的影響力評分大于節點6，7，9，10的影響力評分，因此節點8為高影響力節點。

2 多點種子預劃分的二階段社區發現算法

本節給出多點種子預劃分的二階段社區發現算法。首先，根據算法1選取網絡中的高影響力種子節點，對這些節點利用K-means聚類算法進行初始劃分，識別出由高質量節點組成的種子社區即骨干社區;然后提出一種基于吸引力度量的社區識別算法將社會網絡中其余節點按特定規則有選擇性的加入骨干社區中，從而完成社區劃分。該方法的優勢在于充分考慮了種子節點之間稠密性以及關聯性，有助于提高社區的穩定程度。

2.1 基于K-means聚類的骨干社區識別

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

式中：minDis（A，B）為在社會網絡中節點A，B間最短路徑長度;comNeighbor（A，B）為節點A，B間共同鄰居數量;C為迭代中心，初始值為0;Dis（A，B）為A、B兩點的距離，該值與A、B兩點的最短路徑長度呈正相關，與A、B兩點的共同鄰居數量呈負相關。

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

式中：N（i）表示第i個社區內的節點集合。K-means算法的最終輸出1棵骨干社區層次化樹，采用模塊度函數在層次化樹上進行分割，獲取質量最高的社區劃分。模塊度函數Q是Newman[19]在2004年提出的概念，用以評價社區劃分的質量，其定義為：

式中：eii代表社區i中邊的期望;ai代表鏈接到社區i中的邊數的期望。模塊度的形式化定義是社區內的邊數減去隨機產生的邊的期望，因此模塊度越高，社區內外邊比例就越大，社區劃分結果就越好。

我們發現，算法在層次聚類時模塊度函數Q的取值并不是單調遞增或單調遞減的，因此每當有社區進行合并操作，就需要重新計算Q值，能對產生最大Q值的兩個社區合并。為簡化計算，每次僅計

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

對能產生最大Q值的兩社區進行合并，直到所有節點合并至同一社區。算法的偽代碼如下：

算法2 利用K-means聚類算法實現種子節點初始劃分

輸入：3個種子節點集合，社會網絡G

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

1）選取這3個種子節點進行初始聚類;

2）根據距離度量式（7）計算任意兩節點之間的距離;

3）比較任意兩點間的距離，將節點劃分至距離最近的節點簇內;

4）對于每個簇內，分別計算簇內每個節點與簇內的其他節點距離之和，取和最小的節點作為新的中心節點;

5）迭代步驟4）、5），直到中心節點不發生改變;

6）對K-means算法產生的社區按照式（10）計算兩兩之間合并產生的ΔQ，將使ΔQ增加或減少的兩個社區進行合并，并按照式（9）計算當前Q值，保存Q值及當前社區劃分;

7）對步驟7）進行迭代，直到所有節點都包含在一個社區或不能進行社區合并;

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

2.2 基于吸引力度量的社區識別過程

算法2結束后，會對社會網絡中影響力較高的前3個節點進行預劃分，識別出由高影響力節點組成的種子社區即為骨干社區。而網絡中影響力較低的n-3個零散節點可能處于孤立狀態，因此需要將其合并到骨干社區之中。提出一種基于影響力分析的吸引力度量函數，將網絡中零散節點添加到對其吸引力較高的骨干社區。對于任意骨干社區BC和節點u，BC對u的吸引力度量函數attract（BC，u）的定義為：

式中：∑v∈BC∧v∈N（u）NG（u，v）表示節點u對當前所在骨干社區的所有鄰居節點的影響力評分數之和;Iscore（u）表示節點u的影響力評分。attract（BC，u）的值越大，節點u受骨干社區BC吸引而加入社區BC的可能性就越大，反之節點u成為骨干社區BC內部節點的概率較低。

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

假設BC2的骨干社區包含節點集合為{7，8，9，10}，骨干社區BC2對節點6的吸引力為：

若β=0.4，則節點6不屬于骨干社區BC1，屬于骨干社區BC2。

下面給出基于種子擴張的社區發現算法，算法的偽代碼如下：

算法3 基于種子擴張的社區發現算法

輸入：高影響力節點構成的社區集合BC，社區網絡G

輸出：社區劃分結構

1）將網絡中高影響力節點標記為true，其余n-3個節點標記為false;

2）將網絡中標記為false的節點按照式（11）依次對骨干社區集合BC={BC1，BC2…BCn}進行計算;

3）對每個標記為false的節點按照不同的骨干社區的計算，選取attract（BC，u）最大的值并將該節點加入到對應的骨干網絡;

4）將加入骨干社區網絡的節點標記為true;

5）重復執行步驟2），步驟3）和步驟4），直到社區網絡中所有節點都標記為true;

6）輸出社區劃分結構。

為了挖掘網絡的社區結構，首先將網絡除3個高影響力節點外的節點都標記為false，若節點劃分到一個社區中，則該節點標記為ture。

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

2.3 算法的時間復雜度分析

假設社會網絡G包含有n個節點和m條邊，算法1在求解節點的影響力強度時，時間復雜度為O（n）。在算法2中基于K-means聚類算法將O（l）個節點進行合并得出骨干網絡，其時間復雜度為O（kl），最壞的情況下將O（n）個節點進行合并，故算法2的時間復雜度為O（kn）。在算法3中，在社區擴展階段將O（n）個節點加入到O（k）個骨干社區中，該過程重復執行O（n）次，所以找到所有的最終社區的時間復雜度為O（kn2），若k<

3 實驗結果與分析

本節給出算法在人工合成網絡以及真實數據集上的運行結果。實驗的運行環境為Intel Core i5-7300HQ 2.5GHz處理器，8GB內存，Windows 10操作系統，算法采用Python與Matlab R2016a混合編程。

3.1 NMI指數

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

式中：CA代表網絡中真實社區的數量;CB代表由算法生成社區的數量。如果探測出的社區結構和真實網絡的社區結構相同則NMI=1;反之，如果所探測的社區結構和真實網絡完全不同，則NMI=0。傳統意義上的歸一化互信息被用來量化兩個分布之間的差異性，為了使之適用于社區差異性量化，實驗中采用的了NMI的簡化版本[21]。

3.2 F-SCORE

F-Score也是常用的社區發現算法度量指標。首先定義算法生成社區在全部社區中的比例。

式中，CR代表高質量節點所在的真實社區，CF代表高質量節點所在的探測社區。

Precision是正確劃分節點的數量除以節點在CF中的數量，其定義為：

結合式（15）以及式（16），F-Score定義為：

3.3 人工合成網絡社區識別結果

利用LFR-Benchmark提供的MATLAB數據生成器生成網絡，網絡中的部分重要參數設置如下。首先，生成網絡規模為N=1 000的復雜網絡，其中最小社區尺寸為10、最大社區尺寸為100。接下來設置網絡的平均度為5、最大節點度為25、混合參數u的取值范圍為0.1～0.8。在LFR Benchmark中，混合參數是一個獨立參數，其值越大社區越難以發現，因此通常用來刻畫算法的魯棒性。

首先驗證了不同混合參數下K-means聚類算法中的k取值不同時NMI指標變化情況，實驗結果如圖2所示。可以看出，初始時社區質量會隨種子社區的不斷增多而不斷上升，但達到某一極值時，社區質量開始下降。這是因為初始種子過多會導致社區個數增加，進而降低社區內部的緊密程度。另一個發現是，社區結構較為模糊的網絡中（u=0.8），需要更多的種子社區才能達到較好的發現效果。

接下來，驗證TSCDA算法的性能。與Clauset[12]、LWP[13]、Chen[14]、LS[15]、LCDMC[16]以及VI[17]6種社區識別算法在人工合成網絡社區進行比較，為了保證算法結果的客觀性，將相關參數按原有文獻加以設定，算法的NMI指標以及F-Score在圖3以及圖4給出。

如圖2及圖3所示，當混合參數u等于0.1時，TSCDA在NMI以及F-Score的性能指標明顯優于其它算法，具有一定的性能優勢。隨著混合參數u的不斷增加，TSCDA算法和其他6種算法的NMI指標以及F-Score均呈現明顯的下降趨勢，當混合參數u等于0.5以及0.6時，TSCDA算法略優于VI算法和LCDMC算法，優于LWP以及LS算法;當混合參數u等于0.7以及0.8時，各算法性能較為接近，但總體來看，TSCDA算法仍然要優于其他6種社區識別方法，這表明TSCDA算法在結構指標上更貼近于內嵌社區。

3.4 真實網絡社區識別結果

為了驗證TSCDA算法在真實網絡社區識別的性能，本節選取了在5種真實網絡上，對比TSCDA算法與前文6種社區識別算法的性能差異。表2列出了所選擇的真實網絡的網絡特征，其中Node代表節點個數、Link代表鏈接條數、d—表示網絡的平均度、|C—|表示真實社區的平均大小、Community表示社區個數。我們從Amazon社區中移除了前5 000個子社區，保留了它的不同的社區。

還在DBLP計算機學科文獻數據網絡上測試了TSCDA算法與Clauset算法、LWP算法、Chen算法、LS算法、LCDMC算法以及VI算法的NMI指標以及F-Score指標。DBLP文獻網絡的特性如表3所示。|C|代表社區規模的范圍，例如，（0，10]代表樣本網絡包含的社區大小大于0，小于等于10。我們同樣移除了DBLP網絡前5 000個社區中的子社區，并保留了它們不同的社區結構。

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

圖5和圖6給出了各算法在DBLP引文網絡上的性能指標。實驗結果顯示，當社區規模在0到10時（Label 0），TSCDA在社區識別性能上略低于其他6種算法表現的差。然而當社區規模大于10時（Label 1～10），TSCDA的表現性能明顯優于Clauset、LWP、Chen、LS、LCDMC和VI算法，這表明TSCDA善于挖掘個數較多的社區結果，社區粒度更加細致。

4 結 論

為了解決傳統社區識別方法社區穩定性較差這一問題，從節點相似性以及鏈接相似性兩個角度入手，提出一種多點種子預劃分的社區發現算法TSCDA。首先，在種子擴張算法的基礎上，提出利用高質量節點構建骨干社區進行社區識別，提高社區結構的致密性;其次，將邊介數屬性加入到節點影響力的計算中，提高影響力計算中的結構相關性。人工合成網絡和真實網絡數據集上的仿真結果驗證了TSCDA算法的效率和識別性能。

參 考 文 獻：

[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]李婕， 王興偉， 郭靜， 等. 面向移動通信網絡的局部擴張群組構造方法[J]. 東北大學學報（自然科學版），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]齊金山， 梁循， 王怡. 基于種子節點選擇的重疊社區發現算法[J]. 計算機應用研究，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.

（編輯：溫澤宇）