利用節(jié)點(diǎn)重要度和社團(tuán)接近度發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)

馮健 史丹丹 羅香玉 葉鷗

摘?要：社團(tuán)發(fā)現(xiàn)能夠揭示復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特性。針對現(xiàn)有社團(tuán)發(fā)現(xiàn)算法社團(tuán)初始節(jié)點(diǎn)選擇隨機(jī)、相似度計算過分依賴節(jié)點(diǎn)間共享鄰居以及需要事先設(shè)定社團(tuán)個數(shù)等問題，依托層次聚類思想提出基于節(jié)點(diǎn)重要度和社團(tuán)接近度的社團(tuán)劃分算法。首先引入節(jié)點(diǎn)重要度的定義并給出重要節(jié)點(diǎn)的計算模型，根據(jù)該模型得到最重要節(jié)點(diǎn)作為社團(tuán)的初始聚類中心;然后兼顧節(jié)點(diǎn)的共享關(guān)系和直接影響定義節(jié)點(diǎn)的社團(tuán)接近度，依據(jù)社團(tuán)接近度指標(biāo)尋找與社團(tuán)最接近的節(jié)點(diǎn)，根據(jù)該節(jié)點(diǎn)的加入為社團(tuán)帶來的局部模塊度增量判斷是否將其加入到已有社團(tuán)。首個社團(tuán)劃分完畢后，重復(fù)選取初始聚類中心并構(gòu)造社團(tuán)的過程，直到?jīng)]有可歸入社團(tuán)的節(jié)點(diǎn)。在2個典型復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了測試，

并與Girvan-Newman算法和Newman快速算法從準(zhǔn)確率和模塊度進(jìn)行對比，實(shí)驗(yàn)結(jié)果表明所提算法在社團(tuán)數(shù)目未知的前提下能夠獲得更好的社團(tuán)劃分結(jié)果。關(guān)鍵詞：社團(tuán)發(fā)現(xiàn);層次聚類;節(jié)點(diǎn)重要性;社團(tuán)接近度中圖分類號：TP 399

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

文章編號：1672-9315（2020）01-0181-06

DOI：10.13800/j.cnki.xakjdxxb.2020.0124開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

Discovering community structure using node importance

and community proximity

FENG Jian?1，SHI Dan-dan?2，LUO Xiang-yu?1，YE Ou?1

（1.College of Computer Science and Engineering，Xian University of Science and Technology，Xian 710054，China;

2.Chengdu Skysoft Information Technology Co.，Ltd.，Chengdu 610041，China）

Abstract：Community discovery can reveal the topological characteristics of complex networks.For the existing community discovery algorithms，selection of the initial node for a community is random，similarity calculation is over-reliant to the shared neighbors between nodes，and the numbers of communities needs to be set in advance.To overcome these problems，based on the idea of hierarchical clustering，a community discovery algorithm based on node importance and community proximity is proposed.Firstly，the definition of node importance is introduced and the calculation model of important nodes is given.According to the model，the most important node is taken as the initial cluster center of a community.Then，the concept of node-community proximity is defined by taking the sharing relationship and direct effect of nodes into account.The node closest to the community should be found according to the node-community proximity index，andwhether to add it to the existing community is decided according to the increment of partial modularity brought by the node.After the first community is divided，the process of selecting the initial cluster center and constructing the community is repeated until there are no nodes left.Experiments are carried out on two typical complex network datasets，

with a comparison of the accuracy and modularity made between the results by Girvan-Newman algorithm and Newman fast algorithm.The experimental results show that the proposed algorithm can get better result of community division under the premise that the number of communities is unknown.Key words：community discovery;hierarchical clustering;node importance;community proximity

0?引?言

大量研究表明，結(jié)構(gòu)性是復(fù)雜網(wǎng)絡(luò)的本質(zhì)特性。結(jié)構(gòu)性體現(xiàn)為社團(tuán)，是指復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)呈現(xiàn)出以簇為特征的聚集狀態(tài)，簇內(nèi)節(jié)點(diǎn)聯(lián)系緊密，簇間節(jié)點(diǎn)聯(lián)系松散[1]。發(fā)現(xiàn)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)也稱作社團(tuán)劃分，有助于揭示網(wǎng)絡(luò)的組織原則和功能特性[2]，具有十分重要的理論和應(yīng)用價值。

社會學(xué)研究工作者Newman和Girvan等人的研究是復(fù)雜網(wǎng)絡(luò)中社團(tuán)劃分的起源性研究[3]，在此基礎(chǔ)上人們提出了很多尋找社團(tuán)結(jié)構(gòu)的算法，包括圖劃分方法，如早期提出的經(jīng)典Kernighan-Lin算法[4]和GN算法[5]，后來逐漸傾向于層次聚類法，具體又分為分裂算法[6-7]、凝聚算法[8-9]、譜平分法[10-11]等;以及隨機(jī)塊模型方法[12]、結(jié)合屬性和鏈接法[13-14]等。特別地，針對社團(tuán)的重疊特性，提出了派系過濾算法[15]、極大團(tuán)算法[16]、模糊算法[17]等。上述幾類算法根據(jù)不同的研究對象，又可以歸納為基于節(jié)點(diǎn)的和基于邊的社團(tuán)劃分方法。雖然社團(tuán)劃分算法已有大量研究，但仍存在一些問題，如圖劃分算法依據(jù)網(wǎng)絡(luò)的結(jié)構(gòu)信息進(jìn)行社團(tuán)發(fā)現(xiàn)，往往需要事先設(shè)定社團(tuán)的數(shù)目，對于社團(tuán)數(shù)目未知的網(wǎng)絡(luò)效率較低[18];大多社團(tuán)劃分算法將屬性相似或者角色相似的節(jié)點(diǎn)聚為一類，采用的主流相似度指標(biāo)[19]如共同鄰居指標(biāo)、Salton指標(biāo)、Jaccard指標(biāo)往往主要考慮節(jié)點(diǎn)之間的共同關(guān)系而忽視了節(jié)點(diǎn)對整個網(wǎng)絡(luò)的影響;已有算法常隨機(jī)選擇初始聚類中心，隨后再加以調(diào)整，這樣的策略易導(dǎo)致聚類效果不穩(wěn)定[20]。

為了解決上述問題，借鑒文獻(xiàn)[21]的思想，對層次聚類算法進(jìn)行改進(jìn)，提出基于節(jié)點(diǎn)重要度和社團(tuán)接近度的社團(tuán)劃分算法NICP（Node Importance and Community Proximity Based Community Discovery Algorithm）以探測網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。該算法迭代地選擇重要節(jié)點(diǎn)作為初始聚類中心，并將與社團(tuán)最接近的節(jié)點(diǎn)有條件加入社團(tuán)。文中其余部分組織如下，第1部分介紹NICP算法;第2部分進(jìn)行實(shí)驗(yàn)分析;第3部分總結(jié)全文并指出未來研究方向。

1?社團(tuán)發(fā)現(xiàn)算法

復(fù)雜網(wǎng)絡(luò)可以建模為G=（V，E），其中V為節(jié)點(diǎn)集合;E為邊集合。n=|V|為G的節(jié)點(diǎn)總數(shù)，A是G的n×n維鄰接矩陣。要研究的問題是：對于網(wǎng)絡(luò)G，如何根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的相似性找到其社團(tuán)集合CR.

1.1?評價指標(biāo)

針對網(wǎng)絡(luò)的真實(shí)社團(tuán)劃分未知和已知的情況，研究者們嘗試采用不同的社團(tuán)劃分評價指標(biāo)對社團(tuán)結(jié)構(gòu)進(jìn)行量化。主要的量化指標(biāo)如下

1.1.1?準(zhǔn)確率

準(zhǔn)確率（Precision，P）指示了被正確劃分的節(jié)點(diǎn)數(shù)占總劃分規(guī)模的比例，其定義如下

P=|CR|∩|CRT||CR|

（1）

式中?|CR|T是網(wǎng)絡(luò)的實(shí)際社團(tuán)結(jié)構(gòu)。

1.1.2?模塊度

模塊度Q是一種用于評價劃分結(jié)果的重要指標(biāo)[5]，考量的是社區(qū)內(nèi)實(shí)際連邊和隨機(jī)連邊概率的差異。定義為

式中?m為網(wǎng)絡(luò)的總邊數(shù);u和v為網(wǎng)絡(luò)中的節(jié)點(diǎn)。auv為鄰接矩陣A中第uv個元素的值，即若u和v之間有連邊，則為1，否則為0.D（u）和D（v）分別為u和v的度;Cu和Cv分別是u和v所屬的社團(tuán)，當(dāng)Cu=Cv時，δ（Cu，Cv）=1;否則，δ（Cu，Cv）=0.

模塊度的取值范圍是[-1，1]，值越大表示網(wǎng)絡(luò)的社團(tuán)化程度越高，相應(yīng)地，認(rèn)為社團(tuán)發(fā)現(xiàn)算法性能越好。

1.1.3?局部模塊度

Q通常也稱為全局模塊度，其計算時間復(fù)雜度高且需已知網(wǎng)絡(luò)整體結(jié)構(gòu)。為了解決這些問題，文獻(xiàn)[22]提出了局部模塊度Ql評價指標(biāo)，其簡化定義如下

Ql=|Ei||Ei|+|Eo|（3）

式中?|Ei|為社團(tuán)內(nèi)部的邊數(shù);|Eo|該社團(tuán)對外連接的邊數(shù)。一個社團(tuán)內(nèi)部邊越多，外部邊越少，則其Ql值越大，社團(tuán)結(jié)構(gòu)越清晰。

1.2?NICP算法

NICP基于層次聚類的思想提出算法基本思路：從網(wǎng)絡(luò)G中找到最重要的節(jié)點(diǎn)u作為首個初始聚類中心以構(gòu)建初始社團(tuán)。在剩余節(jié)點(diǎn)中尋找與該社團(tuán)最接近的節(jié)點(diǎn)v，計算v與該社團(tuán)合并后將為社團(tuán)帶來的局部模塊度增量ΔQl;若ΔQl>0，即v的加入將使社團(tuán)的內(nèi)聚力得到增強(qiáng)，則將v合并到u所在的社團(tuán)，否則開始構(gòu)建新的社團(tuán)。對合并后的小社團(tuán)重復(fù)上述尋找并添加最接近節(jié)點(diǎn)的過程，直到某個接近節(jié)點(diǎn)的加入將導(dǎo)致ΔQl≤0，這時一個社團(tuán)劃分完成。重新在剩余的節(jié)點(diǎn)中尋找最重要的節(jié)點(diǎn)作為下一個社團(tuán)的初始聚類中心，并重復(fù)上述社團(tuán)劃分過程，直到網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都劃分完畢。算法的關(guān)鍵點(diǎn)是：①最重要節(jié)點(diǎn)的判定，即社團(tuán)初始聚類中心的確定;②接近節(jié)點(diǎn)的度量，即節(jié)點(diǎn)及社團(tuán)接近度的度量;③社團(tuán)內(nèi)聚力的評判。

1.2.1?最重要節(jié)點(diǎn)的判定

在社團(tuán)的聚類中，初始節(jié)點(diǎn)的選擇在很大程度上影響了社團(tuán)的內(nèi)聚力和穩(wěn)定性。已有層次聚類算法常隨機(jī)選取初始聚類中心，后續(xù)再進(jìn)行社團(tuán)中心的調(diào)整，這樣的方法往往導(dǎo)致社團(tuán)劃分質(zhì)量不高，也容易引起社團(tuán)的動蕩。重要節(jié)點(diǎn)是網(wǎng)絡(luò)中能夠產(chǎn)生一定影響力并起到信息橋梁作用的節(jié)點(diǎn)，也即同時具有中心性和橋接能力[23]。據(jù)此引入節(jié)點(diǎn)重要度的概念，并選擇重要節(jié)點(diǎn)作為社團(tuán)初始聚類中心。

定義1?（節(jié)點(diǎn)重要度）I（u），為節(jié)點(diǎn)u的K-shell值和結(jié)構(gòu)洞度的線性組合

I（u）=αKS（u）+βES（u），α+β=1（4）

式中KS（u）是u的K-shell值[24]，ES（u）是通過Burt提出的網(wǎng)絡(luò)有效規(guī)模計算得到的結(jié)構(gòu)洞度[25]。參數(shù)α和β為調(diào)節(jié)系數(shù)，其值根據(jù)實(shí)際網(wǎng)絡(luò)結(jié)構(gòu)與功能設(shè)定，實(shí)驗(yàn)中設(shè)置α=0.1和β=0.9.

社團(tuán)中最重要的節(jié)點(diǎn)即重要度最大的節(jié)點(diǎn)，概念如下

定義2?（重要節(jié)點(diǎn)）NCi，為社團(tuán)Ci的重要節(jié)點(diǎn)

1.2.2?節(jié)點(diǎn)及社團(tuán)接近度的度量

社團(tuán)劃分實(shí)質(zhì)上是尋找結(jié)構(gòu)相似或性質(zhì)相似的節(jié)點(diǎn)并將其放入同一社團(tuán)中的過程，其核心問題是如何不斷尋找與社團(tuán)連接性最強(qiáng)的節(jié)點(diǎn)。這就要度量節(jié)點(diǎn)與社團(tuán)中已有各節(jié)點(diǎn)的相似度。已有方法在評價節(jié)點(diǎn)間相似度時常依賴于2個節(jié)點(diǎn)的共同關(guān)系，如一般認(rèn)為共享鄰居數(shù)量越多相似性越大;文中則認(rèn)為節(jié)點(diǎn)的相似度不僅與節(jié)點(diǎn)間擁有的共同關(guān)系有關(guān)，還與節(jié)點(diǎn)對另一節(jié)點(diǎn)的直接影響有關(guān)，因此提出接近度的概念。

定義3?（投入精力）ENuv，節(jié)點(diǎn)u對節(jié)點(diǎn)v投入的精力，表達(dá)節(jié)點(diǎn)的直接影響，定義為

ENuv= auv/D（u）（6）

定義4?（節(jié)點(diǎn)接近度）θuv，節(jié)點(diǎn)u與節(jié)點(diǎn)v的接近度，定義為

θuv= ENuv+sENus ENsv（7）

式中?s為u和v的共享鄰居。從上式可知接近度不僅表達(dá)了節(jié)點(diǎn)u對節(jié)點(diǎn)v的直接影響，也表達(dá)了2個節(jié)點(diǎn)間的共同關(guān)系。

以圖1的拓?fù)錇槔?，?jié)點(diǎn)a的鄰居集合為{b，c，d，g4，g5，g6，g7，g8}，根據(jù)公式（7）得到θab=0.250 0，

θac=0.125 0，

θad=0.312 5，

θag4=θag5=

θag6=θag7=

θag8=0.146 0

.根據(jù)計算結(jié)果可知，對于a來說，最接近的節(jié)點(diǎn)是d，這也和圖1中的實(shí)際情況是吻合的。

推而廣之，節(jié)點(diǎn)的社團(tuán)接近度即為節(jié)點(diǎn)與社團(tuán)內(nèi)部所有節(jié)點(diǎn)的接近度之和。

定義5?（社團(tuán)接近度）θuC，節(jié)點(diǎn)u和社團(tuán)C的接近度

1.2.3?社團(tuán)內(nèi)聚力的評判

采用局部模塊度進(jìn)行社團(tuán)內(nèi)聚力的評判。若某個節(jié)點(diǎn)的加入導(dǎo)致當(dāng)前社團(tuán)的局部模塊度增大，則將該節(jié)點(diǎn)加入社團(tuán)，否則視為新社團(tuán)起始的標(biāo)志。

NICP算法的具體描述如下

輸入：G，α，β

輸出：CR

1）CR={}，Ql=0;

2）對V按節(jié)點(diǎn)重要度降序排序形成節(jié)點(diǎn)序列VI;

3）選擇VI中重要度最大的節(jié)點(diǎn)v作為社團(tuán)初始聚類中心，VI=VI-{v}，Ct={v};

4）建立Ct社團(tuán)：

①找到與Ct相連的所有節(jié)點(diǎn)，建立節(jié)點(diǎn)集合

VCt;

②通過計算θ值，從

VCt中查找與Ct社團(tuán)最接近的節(jié)點(diǎn)u;

③若ΔQl>0，則將u加入社團(tuán)Ct，Ct=Ct+{u}，

VI=VI-{u}，轉(zhuǎn)至①;

否則，CR=CR+Ct，若

VI={}，轉(zhuǎn)至⑤，否則轉(zhuǎn)至③，開始新社團(tuán)的劃分;⑤算法結(jié)束，輸出CR.

算法引入了2個關(guān)鍵環(huán)節(jié)來保證其穩(wěn)定性和精度：根據(jù)節(jié)點(diǎn)的中心性和橋接性確定社團(tuán)的初始聚類中心，提高社團(tuán)劃分質(zhì)量并避免社團(tuán)劃分過程中的動蕩;兼顧節(jié)點(diǎn)的共享關(guān)系和直接影響更準(zhǔn)確地計算節(jié)點(diǎn)與社團(tuán)的接近度，保證聚類的精度。另外，NICP算法利用局部模塊度增量自動確定一個社團(tuán)是否結(jié)束，無需事先給定社團(tuán)數(shù)量。

2?實(shí)驗(yàn)分析

為了定量驗(yàn)證NICP算法的可行性和有效性，在人工網(wǎng)絡(luò)—三社團(tuán)網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)—足球隊(duì)俱樂部Football網(wǎng)絡(luò)數(shù)據(jù)集[3]上分別與有代表性的靜態(tài)社團(tuán)發(fā)現(xiàn)算法GN和FN[8]進(jìn)行了綜合評測。實(shí)驗(yàn)在主頻為3.2 GHz，內(nèi)存大小為16 GB的Intel Core i5處理器上完成，程序運(yùn)行環(huán)境為Python 2.7.

表1為2個測試網(wǎng)絡(luò)的基本信息。

2.1?三社團(tuán)網(wǎng)絡(luò)

圖2為三社團(tuán)網(wǎng)絡(luò)示意圖，通過NICP算法的發(fā)現(xiàn)過程見表2.

從表2可以清晰地看到，NICP算法的社團(tuán)發(fā)現(xiàn)過程：首先通過節(jié)點(diǎn)重要度找到社團(tuán)的初始聚類中心（3個社團(tuán)的初始聚類中心分別為6，7，18號節(jié)點(diǎn)），然后逐步尋找最接近節(jié)點(diǎn)，再通過局部模塊度的增大或減小決定將該節(jié)點(diǎn)加入社團(tuán)或開始一個新的社團(tuán)。通過對比圖2和表2可以看到，NICP算法的發(fā)現(xiàn)結(jié)果和原網(wǎng)絡(luò)完全一致。

表3給出各算法在三社團(tuán)網(wǎng)絡(luò)中的發(fā)現(xiàn)結(jié)果。

從表3可以看出，NICP算法的準(zhǔn)確率和模塊度與GN，F(xiàn)N算法一樣，3個算法均能準(zhǔn)確地對三社團(tuán)網(wǎng)絡(luò)進(jìn)行劃分。

2.2?Football

Football是2000年美國大學(xué)橄欖球聯(lián)賽的網(wǎng)絡(luò)數(shù)據(jù)。其中，節(jié)點(diǎn)代表參賽球隊(duì)，若兩支球隊(duì)之間進(jìn)行過一場比賽則形成連邊。該網(wǎng)絡(luò)共涉及115所大學(xué)的球隊(duì)，分為12個社團(tuán)，對應(yīng)聯(lián)賽的12個聯(lián)盟。表4給出各算法的社團(tuán)發(fā)現(xiàn)結(jié)果。

從表4可以看出，NICP算法無論是準(zhǔn)確率還是模塊度都比傳統(tǒng)經(jīng)典算法高，說明NICP算法能更有效地劃分網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)。

3?結(jié)?論

1）為解決復(fù)雜網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)問題提出了一種改進(jìn)的基于層次聚類的社團(tuán)發(fā)現(xiàn)算法NICP.

2）針對已有社團(tuán)發(fā)現(xiàn)算法中初始聚類中心選擇隨機(jī)的問題，考慮節(jié)點(diǎn)的中心性和橋接性提出節(jié)點(diǎn)重要度的概念，選擇最重要節(jié)點(diǎn)作為初始聚類中心，提高社團(tuán)發(fā)現(xiàn)的效率和穩(wěn)定性;針對聚類過程中相似度計算過分依賴節(jié)點(diǎn)間共享鄰居的問題，結(jié)合節(jié)點(diǎn)間的共享關(guān)系和節(jié)點(diǎn)自身的影響提出節(jié)點(diǎn)接近度的概念，并擴(kuò)展至節(jié)點(diǎn)-社團(tuán)接近度，并以此作為節(jié)點(diǎn)與社團(tuán)聚類相似度判定的依據(jù);針對已有算法常需要事先設(shè)定社團(tuán)個數(shù)的問題，將局部模塊度的減小作為判定條件，自動發(fā)現(xiàn)新的社團(tuán)。

3）將NICP算法和GN，F(xiàn)N算法應(yīng)用在經(jīng)典人工網(wǎng)絡(luò)和實(shí)際網(wǎng)絡(luò)中的結(jié)果表明，NICP算法社團(tuán)發(fā)現(xiàn)結(jié)果的準(zhǔn)確率和模塊度指標(biāo)都更高，證實(shí)了該算法具有可行性和有效性。

參考文獻(xiàn)（References）：

[1]汪小帆，劉亞冰.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)算法綜述[J].電子科技大學(xué)學(xué)報，2009，38（5）：537-543.WANG Xiao-fan，LIU Ya-bing.Overview of algorithms for detecting community structure in complex networks[J].Journal of University of Electronic Science and Technology of China，2009，38（5）：537-543.

[2]朱慶生，蔣天弘，周明強(qiáng).基于自然最近鄰居的社團(tuán)檢測算法[J].計算機(jī)應(yīng)用研究，2014，31（12）：3560-3563.ZHU Qing-sheng，JIANG Tian-hong，ZHOU Ming-qiang.Community detection algorithm based on natural nearest neighbor[J].Application Research of Computers，2014，31（12）：3560-3563.

[3]Girvan M，Newman M E J.Community structure in social and biological networks[J].Proceedings of National Academy of Sciences of the United States of America，2002，99（12）：7821-7826.

[4]Kernighan B W，Lin S.An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal，1970（49）：291-307.

[5]Newman M E J，Girvan M.Finding and evaluating community structure in networks[J].Physical Review E，2004，69（2）：026113.

[6]Radicchi F，Castellano C，Cecconi F，et al.Defining and identifying communities in networks[J].Proceedings of the National Academy of Sciences of the United States of America，2004，101（9）：2658-2663.

[7]Sales-Pardo M，Guimera R，Moreira A A，et al.Extracting the hierarchical organization of complex systems[J].Proceedings of the National Academy of Sciences of the United States of America，2007，104（39）：15224-15229.

[8]Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics，2003，69（6 Pt 2）：066133.

[9]Blondel V D，Guillaume J L，Lambiotte R，et al.Fast unfolding of community hierarchies in large networks[J].Journal of Statistical Mechanics：Theory and Experiment，2008，10：10008.

[10]Luxburg U.A tutorial on spectral clustering[J].Statistics and Computing，2007，17（4）：395-416.

[11]付立東.一種對分劃分的復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測方法[J].西安科技大學(xué)學(xué)報，2012，32（5）：648-651.FU Li-dong.Detecting of communities in complex networks with two partitioning approach[J].Journal of Xian University of Science and Technology，2012，32（5）：648-651.

[12]Zhang H，Qiu B，Giles C L，et al.An LDA-based community structure discovery approach for large-scale social networks[C]//Muresan G，Altiok T，Melamed B，Zeng D.Proceedings of 2007 IEEE Intelligence and Security Informatics，New Brunswick，NJ USA，2007：200-207.

[13]黃發(fā)良，肖南峰.基于線圖與PSO的網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)[J].自動化學(xué)報，2011，37（9）：1140-1144.HUANG Fa-liang，XIAO Nan-feng.Discovering overlapping communities based on line graph and PSO[J].Acta Automatica Sinica，2011，37（9）：1140-1144.

[14]李孝偉，陳福才，劉力雄.一種融合節(jié)點(diǎn)與鏈接屬性的社交網(wǎng)絡(luò)社區(qū)劃分算法[J].計算機(jī)應(yīng)用研究，2013，30（5）：1477-1480.LI Xiao-wei，CHEN Fu-cai，LIU Li-xiong.Combined node and link attributes of social network community detection algorithm[J].Application Research of Computers，2013，30（5）：1477-1480.

[15]Palla G，Derényi I，F(xiàn)arkas I，et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature，2005，435：814-818.

[16]Shen H W，Cheng X Q，Cai K，et al.Detect overlapping and hierarchical community structure in networks[J].Physica A Statistical Mechanics & Its Applications，2009，388（8）：1706-1712.

[17]Nepusz T，Petróczi A，N-gyessy L，et al.Fuzzy communities and the concept of bridgeness in complex networks[J].Physical Review E，2008，77（2）：016107.

[18]Fortunato S，Barthelemy M.Resolution limit in community detection[J].Proceedings of the National Academy of Sciences of the United States of America，2007，104（1）：36-41.

[19]姜雅文，賈彩燕，于?劍.基于節(jié)點(diǎn)相似度的網(wǎng)絡(luò)社團(tuán)檢測算法研究[J].計算機(jī)科學(xué)，2011，38（7）：185-189.JIANG Ya-wen，JIA Cai-yan，YU Jian.Community detection in complex networks based on vertex similarities[J].Computer Science，2011，38（7）：185-189.

[20]閔?亮，邵良杉，趙永剛.基于節(jié)點(diǎn)相似度的社團(tuán)檢測[J].計算機(jī)工程與應(yīng)用，2015，51（9）：77-81.MIN Liang，SHAO Liang-shan，ZHAO Yong-gang.Community detection based on node similarity[J].Computer Engineering and Applications，2015，51（9）：77-81.

[21]馮?健，丁媛媛.基于重疊社區(qū)和結(jié)構(gòu)洞度的社會網(wǎng)絡(luò)結(jié)構(gòu)洞識別算法[J].計算機(jī)工程與科學(xué)，2016，38（5）：898-904.FENG Jian，DING Yuan-yuan.A structural hole identification algorithm in social networks based on overlapping communities and structural hole degree[J].Computer Engineering & Science，2016，38（5）：898-904.

[22]Clauset A.Finding local community structure in networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics，2005，72（2）：026132.

[23]Feng J，Shi D D，Luo X Y.An identification method for important nodes based on K-shell[J].Journal of Complex Networks，2018，6（3）：342-352.

[24]任卓明，劉建國，邵?鳳，等.復(fù)雜網(wǎng)絡(luò)中最小K-核節(jié)點(diǎn)的傳播能力分析[J].物理學(xué)報，2013，62（10）：466-471.REN Zhuo-ming，LIU Jian-guo，SHAO Feng，et al.Analysis of the spreading influence of the nodes with minimum K-shell value in complex networks[J].Acta Physica Sinica，2013，62（10）：466-471.

[25]Burt R.Structural holes and good ideas[J].American Journal of Sociology，2004，110（2）：349-399.