復雜網(wǎng)絡模糊重疊社區(qū)檢測研究進展

肖 婧，張永建，許小可,2

(1.大連民族大學信息與通信工程學院，遼寧 大連 116600；2.貴州省公共大數(shù)據(jù)重點實驗室貴州大學，貴陽 550025)

復雜網(wǎng)絡模糊重疊社區(qū)檢測研究進展

肖 婧1，張永建1，許小可1,2

(1.大連民族大學信息與通信工程學院，遼寧 大連 116600；2.貴州省公共大數(shù)據(jù)重點實驗室貴州大學，貴陽 550025)

模糊重疊社區(qū)檢測通過擴展隸屬度取值空間，實現(xiàn)了重疊節(jié)點與社區(qū)之間復雜且模糊隸屬關系的精確化測量，不僅能夠有效提升重疊社區(qū)結構檢測的精確性，而且能夠深度挖掘出節(jié)點和社區(qū)的重疊特性。文中首先分析了模糊重疊社區(qū)檢測與傳統(tǒng)離散重疊社區(qū)檢測的關系；然后對二者的國內外相關研究現(xiàn)狀進行闡述和分析，其中在模糊重疊社區(qū)檢測方法研究中根據(jù)模糊隸屬度獲取方式的不同將當前相關研究分為擴展標簽傳播、非負矩陣分解、基于邊界節(jié)點的兩階段檢測、模糊聚類、模糊模塊度優(yōu)化五大類進行綜述，重點分析了基于進化算法的模糊模塊度優(yōu)化方法；最后對模糊重疊社區(qū)檢測研究未來的發(fā)展趨勢進行了分析和展望。

社區(qū)檢測；離散重疊；模糊重疊；模糊模塊度優(yōu)化；進化算法

0 引言

復雜網(wǎng)絡社區(qū)檢測是指從復雜網(wǎng)絡中挖掘出有實際意義的模塊或層次結構的過程，能夠提取出網(wǎng)絡拓撲結構特征，有助于理解和分析網(wǎng)絡的拓撲特性、功能特性及動力學特性，挖掘出網(wǎng)絡中蘊含的屬性關聯(lián)性等深層次信息并對網(wǎng)絡行為進行預測[1-5]，因此具有重要的理論研究價值。近年來，復雜網(wǎng)絡社區(qū)檢測在互聯(lián)網(wǎng)基礎設施優(yōu)化、在線銷售產品推薦、社交網(wǎng)絡及生物網(wǎng)絡分析、反恐組織識別、政治選舉預測等諸多領域中的應用需求日益凸顯[6-7]，因此對其進行研究具有重要的現(xiàn)實意義。

針對重疊社區(qū)結構的檢測是復雜網(wǎng)絡社區(qū)檢測中的一種特殊形式。由于現(xiàn)實世界網(wǎng)絡中節(jié)點具有天然的多社區(qū)歸屬特性[8]，因此“重疊”是大多數(shù)真實網(wǎng)絡的重要特征。研究真實網(wǎng)絡社區(qū)結構的重疊特性，對于探索網(wǎng)絡中重要節(jié)點在拓撲及屬性功能上的多面性特性，掌握重疊節(jié)點與社區(qū)之間的拓撲及屬性關聯(lián)性，挖掘社區(qū)之間的功能相似性及差異性等均具有重要意義，因此重疊社區(qū)檢測成為近年來復雜網(wǎng)絡社區(qū)檢測領域的研究熱點[1-8]。

重疊社區(qū)結構中存在一些同時隸屬于多個社區(qū)的重疊節(jié)點，是重疊社區(qū)結構的重要特征，也是重疊社區(qū)檢測的重要內容。一方面，重疊節(jié)點在拓撲及屬性等特性上具有多樣性，該特性是重疊社區(qū)結構形成的重要因素；另一方面，重疊節(jié)點是社區(qū)之間連接的橋梁，對社區(qū)之間的連接關系、信息交互及動態(tài)演化起到關鍵性作用[9-10]。鑒于此，重疊社區(qū)檢測的任務主要包括兩方面：一是如何更加完整、精確地挖掘網(wǎng)絡中的重疊節(jié)點及其社區(qū)分布，提升對于網(wǎng)絡中重疊社區(qū)結構的檢測能力；二是如何更加精確、細致地體現(xiàn)重疊節(jié)點與所屬各社區(qū)之間的拓撲與屬性關聯(lián)性，并由此揭示重疊社區(qū)結構中隱含的深層次拓撲信息。

現(xiàn)實世界中復雜網(wǎng)絡的重疊社區(qū)結構通常具有較強的復雜性和模糊性。復雜性表現(xiàn)在重疊節(jié)點可同時隸屬多個社區(qū)，且不同重疊節(jié)點實際隸屬的社區(qū)數(shù)目可能存在較大差異。模糊性主要體現(xiàn)在重疊節(jié)點與社區(qū)之間的隸屬關系以及社區(qū)結構的重疊程度上，一方面節(jié)點對于不同社區(qū)的隸屬程度存在較大差異，重疊節(jié)點與社區(qū)之間的隸屬關系具有模糊性；另一方面真實網(wǎng)絡中并沒有嚴格的社區(qū)劃分界限[10]，重疊社區(qū)的邊界及不同社區(qū)之間的重疊程度均存在一定模糊性。實際網(wǎng)絡環(huán)境下，根據(jù)檢測分析需求和用戶解釋的不同，對重疊節(jié)點的判定準則和計算依據(jù)也存在較大差異，使重疊節(jié)點、重疊社區(qū)結構及節(jié)點和社區(qū)的重疊程度通常存在較大差異[4,8]，因此具有較大的模糊性。鑒于此，對于真實世界中復雜網(wǎng)絡的重疊社區(qū)檢測，一方面需要盡可能提升對于重疊社區(qū)結構的識別和提取能力，即重疊社區(qū)檢測的精確性；另一方面，需要側重于體現(xiàn)出網(wǎng)絡中更細致化、多樣化的社區(qū)結構信息，如量化并區(qū)分重疊節(jié)點與各社區(qū)之間的隸屬程度，從而為不同環(huán)境及需求下真實網(wǎng)絡重疊社區(qū)結構的挖掘與分析提供較為精確可靠的測度信息。通過在檢測結果中體現(xiàn)出重疊社區(qū)結構的復雜性及模糊性，為網(wǎng)絡功能及動力學特性分析、鏈路預測、社區(qū)動態(tài)演化預測等更深層次的復雜網(wǎng)絡挖掘提供參考依據(jù)。

根據(jù)重疊節(jié)點與社區(qū)之間隸屬程度的量化程度差異，可將復雜網(wǎng)絡的重疊社區(qū)檢測分為兩類：即離散重疊(Crisp Overlap)社區(qū)檢測和模糊重疊(Fuzzy Overlap)社區(qū)檢測。目前國內外絕大多數(shù)重疊社區(qū)檢測研究僅限于離散重疊社區(qū)檢測[1-5]，相關檢測方法的數(shù)量及種類較多，其中典型代表性方法包括：派系過濾、鏈接聚類、局部擴展、模塊度優(yōu)化、多目標優(yōu)化及標簽傳播等。該類檢測方法的前提假設為重疊節(jié)點對所屬社區(qū)具有完全且一致的隸屬關系(Full Membership)，在此假設下雖然能夠檢測出重疊社區(qū)結構，但無法體現(xiàn)出重疊節(jié)點對不同社區(qū)不完全且非一致的隸屬關系。因此，該種假設實質上是簡化了對于真實重疊社區(qū)結構中復雜且模糊拓撲關系的刻畫，限制了對于重疊社區(qū)結構內在隱含深層次拓撲信息的探索能力。

近年來，針對重疊社區(qū)檢測的研究延伸出了新的分支，即模糊重疊社區(qū)檢測(Fuzzy Overlapping Community Detection)。2011年Gregory針對社交網(wǎng)絡的社區(qū)檢測首次提出了“模糊重疊劃分(Fuzzy Overlapping Partition)”的概念[6]。模糊重疊社區(qū)檢測與傳統(tǒng)離散重疊社區(qū)檢測的區(qū)別在于：允許重疊節(jié)點對所屬社區(qū)具有不完全且不一致的隸屬關系，利用[0,1]連續(xù)區(qū)間內分布的模糊隸屬度(Fuzzy Membership Degree)量化重疊節(jié)點對不同社區(qū)的相對隸屬程度，同一節(jié)點對所有社區(qū)的隸屬度總和為“1”。此外，模糊重疊社區(qū)檢測與模糊社區(qū)檢測的區(qū)別在于，不僅前者在檢測過程中利用隸屬度測度，而且在檢測結果中體現(xiàn)所有節(jié)點對所有社區(qū)完整且相對的隸屬度分布信息，從而體現(xiàn)重疊社區(qū)結構。

模糊重疊社區(qū)檢測實質上是通過擴展離散重疊社區(qū)檢測的隸屬度取值空間，更加細致完整地測量了節(jié)點與社區(qū)之間的隸屬關系及隸屬程度，因此能夠加強對于真實重疊社區(qū)結構中復雜且模糊拓撲結構的探索能力。模糊重疊社區(qū)檢測在針對科學家合作網(wǎng)絡、社會網(wǎng)絡、生物網(wǎng)絡等基于個體關聯(lián)性構成的復雜網(wǎng)絡重疊社區(qū)檢測中具有重要的理論和應用研究價值。美國密西根理工大學、法國里昂大學、英國布里斯托大學、澳大利亞墨爾本大學、西北工業(yè)大學等國內外研究機構都在此領域開展了探索性研究，近期研究成果頻頻出現(xiàn)在《IEEE TRANSACTIONS ON FUZZY SYSTEMS》、FUZZ-IEEE等國際重要期刊和會議上。

本文對復雜網(wǎng)絡中模糊重疊社區(qū)檢測的研究進行綜述，組織結構為：首先對重疊社區(qū)檢測問題的基本概念進行闡述，分析了模糊重疊社區(qū)檢測與傳統(tǒng)離散重疊社區(qū)檢測的關聯(lián)性，重點分析了模糊重疊社區(qū)檢測的功能性優(yōu)勢；然后對二者的國內外研究現(xiàn)狀進行闡述和分析，其中，在對模糊重疊社區(qū)檢測研究的介紹中，根據(jù)重疊節(jié)點模糊隸屬度分布獲取方式的不同，將當前相關研究分為擴展標簽傳播、非負矩陣分解、基于邊界節(jié)點的兩階段檢測、模糊聚類及模糊模塊度優(yōu)化五大類檢測方法進行綜述，重點分析了基于進化算法(Evolutionary Algorithms, EAs)模糊模塊度優(yōu)化方法的功能性優(yōu)勢及面臨的技術挑戰(zhàn)；最后對模糊重疊社區(qū)檢測的研究難點及未來發(fā)展趨勢進行了分析和展望。

1 相關基本概念

1.1 模糊重疊社區(qū)檢測定義

圖1 社區(qū)檢測分類及可行搜索空間Fig.1 Classification of community detection and feasible region of community partition

復雜網(wǎng)絡社區(qū)檢測的社區(qū)劃分可行搜索空間如圖1所示。按照檢測復雜度及功能性遞增的順序分為非重疊社區(qū)劃分(或稱為硬劃分)、離散重疊社區(qū)劃分和模糊重疊社區(qū)劃分3類，其中硬劃分最簡單且易實現(xiàn)，可看作離散重疊社區(qū)劃分和模糊重疊社區(qū)劃分的特例；模糊重疊社區(qū)劃分的復雜度最高且檢測難度最大，是對傳統(tǒng)離散重疊社區(qū)劃分的功能性補充和擴展。

上述3類社區(qū)檢測及對應社區(qū)劃分的定義說明如下：

1)非重疊社區(qū)劃分，又稱為硬劃分(Hard Partition)。定義網(wǎng)絡中任意節(jié)點僅能隸屬于單個社區(qū)，且與所屬社區(qū)之間具有完全的隸屬關系。

2)離散重疊劃分(Crisp Overlapping Partition)，又稱為脆性重疊劃分或非模糊重疊劃分。定義網(wǎng)絡中每個節(jié)點可同時隸屬于多個社區(qū)，且對不同社區(qū)的隸屬程度只能為完全隸屬或完全不隸屬，即隸屬度在二進制空間{0,1}內取值。任意重疊節(jié)點對所有所屬社區(qū)具有完全相同的隸屬度，且隸屬度取值為“1”。因此，離散重疊社區(qū)檢測過程中僅需考慮節(jié)點與社區(qū)之間是否存在隸屬關系，而不必衡量節(jié)點與社區(qū)之間的隸屬程度。

3)模糊重疊劃分(Fuzzy Overlapping Partition)。定義網(wǎng)絡中任意節(jié)點不僅可同時隸屬于多個社區(qū)，而且允許節(jié)點對所屬不同社區(qū)具有不同的隸屬程度。隸屬度在十進制連續(xù)空間[0,1]內取值，當隸屬度取值為“0”時代表完全不隸屬，當隸屬度取值為“1”時代表完全隸屬，當隸屬度取值介于“0”和“1”之間時代表部分隸屬。隸屬度數(shù)值越大說明節(jié)點對社區(qū)的隸屬程度越強，約束條件為任意節(jié)點對網(wǎng)絡中所有社區(qū)的隸屬度總和恒為“1”。模糊重疊通過擴展離散重疊的隸屬度取值空間，大幅細化了節(jié)點對于社區(qū)的隸屬程度，因此能夠更精細地描述節(jié)點與社區(qū)之間復雜且模糊的隸屬關系。

1.2 模糊重疊社區(qū)檢測數(shù)學模型

下面對上述3類社區(qū)檢測對應社區(qū)劃分的數(shù)學模型進行說明。不失一般性，以無向加權網(wǎng)絡為例，其對應子圖可表示為G=(V,E,W)，其中V代表網(wǎng)絡中n個節(jié)點組成的集合，E代表網(wǎng)絡中m條邊組成的集合，W為規(guī)模為n*n邊權重矩陣(或鄰接矩陣)，元素wij代表節(jié)點i和j之間的連接權重，i,j=1,…,n。網(wǎng)絡社區(qū)檢測的過程可視為在子圖G上找到一個規(guī)模為n*c的社區(qū)劃分U={uik}，i=[n]，k=[c]，如式(1)所示，U中每個元素uik代表網(wǎng)絡中任意節(jié)點i對于任意社區(qū)k的隸屬度。

(1)

3類社區(qū)檢測對應社區(qū)劃分的數(shù)學公式如式(2)～(5)所示，其中式(2)中Mpcn代表所有類型社區(qū)檢測對應可行社區(qū)劃分的集合，物理含義為任意節(jié)點對任意社區(qū)隸屬度的取值空間為[0,1]，任意節(jié)點對所有社區(qū)的隸屬度總和不超過社區(qū)總數(shù)c，而任意社區(qū)內所有節(jié)點的隸屬度總和小于網(wǎng)絡節(jié)點總數(shù)n。式(3)中Mhcn代表社區(qū)硬劃分，Mhcn是Mpcn的子集，不僅限制任意節(jié)點僅能隸屬于一個社區(qū)，而且對任意社區(qū)的隸屬度在{0,1}空間內取值。式(4)中Mccn代表離散重疊社區(qū)劃分集合，Mccn是Mpcn的子集，限制任意節(jié)點對任意社區(qū)的隸屬度在二值空間{0,1}內取值。式(5)中Mfcn代表模糊重疊社區(qū)劃分集合，Mfcn是Mpcn的子集，限制任意節(jié)點對所有社區(qū)的隸屬度總和恒為“1”。

(2)

(3)

Mccn={U∈Mpcn;uik∈{0,1},?i,k}

(4)

(5)

1.3 模糊重疊社區(qū)檢測功能性說明

圖2 模糊重疊社區(qū)檢測網(wǎng)絡示例Fig.2 Network of fuzzy overlapping community detection

為更直觀地體現(xiàn)模糊重疊社區(qū)檢測的定義、特征及功能性優(yōu)勢，以Psorakis等提出的已知真實重疊社區(qū)結構的無向加權網(wǎng)絡[11]為例進行說明。圖2a為示例網(wǎng)絡的拓撲連接關系，其對應真實重疊社區(qū)結構如圖2b所示。

對該網(wǎng)絡進行模糊重疊社區(qū)檢測，能夠得到模糊重疊社區(qū)劃分Mfcn，包含所有節(jié)點的社區(qū)分布及相應隸屬度。基于此實現(xiàn)模糊重疊社區(qū)檢測相比較于非重疊社區(qū)檢測、傳統(tǒng)離散重疊社區(qū)檢測的特殊功能性優(yōu)勢主要包括以下4項。

1.3.1 獲得重疊節(jié)點及完整社區(qū)隸屬度分布

通過模糊重疊社區(qū)檢測，能夠獲得所有節(jié)點對各社區(qū)完整、相對且非一致的模糊隸屬度分布U，如表1所示，由此精確體現(xiàn)重疊節(jié)點的社區(qū)分布及對不同社區(qū)的隸屬程度差異。

根據(jù)表1所示的節(jié)點模糊隸屬度分布U，模糊重疊社區(qū)檢測不僅可實現(xiàn)離散重疊社區(qū)檢測的基本檢測功能，即檢測出重疊節(jié)點{4,5,6,9,10,13,14}，而且能夠更進一步定量體現(xiàn)出所有重疊節(jié)點對所有社區(qū){k1,k2,k3,k4}的隸屬程度差異。

1.3.2 精細化測量重疊節(jié)點的重疊程度差異

基于節(jié)點的模糊隸屬度分布U，不僅可獲知所有節(jié)點的重疊性和社區(qū)隸屬程度差異，而且能夠更精確地測量節(jié)點的重疊程度。節(jié)點的重疊程度主要體現(xiàn)在隸屬社區(qū)數(shù)目的多少以及對重疊社區(qū)隸屬程度的差異性兩方面，節(jié)點隸屬社區(qū)數(shù)目越多且同時對所屬社區(qū)的隸屬度越接近，說明節(jié)點的重疊程度越大。模糊重疊社區(qū)檢測不僅能夠與離散重疊社區(qū)檢測一樣，從重疊節(jié)點隸屬社區(qū)數(shù)目的多少衡量節(jié)點重疊程度大小，而且能夠從更具體的隸屬度數(shù)值差異中更精細地測量節(jié)點重疊程度。

表1 節(jié)點模糊隸屬度分布UTab. 1 Fuzzy Membership Degree distribution U of nodes

圖3 網(wǎng)絡節(jié)點重疊程度測量Fig.3 Overlapping degree of nodes

根據(jù)表1中節(jié)點的隸屬度數(shù)值分布及隸屬社區(qū)數(shù)目，可設計如式(6)所示的測量指標Oi全面測量重疊節(jié)點的重疊程度。

(6)

1.3.3 定量測量社區(qū)重疊程度及重疊節(jié)點重要性

與離散重疊社區(qū)檢測不同，模糊重疊社區(qū)檢測除了能夠更加精細地測量重疊節(jié)點的重疊程度，還能夠根據(jù)節(jié)點隸屬度分布U定量描述重疊社區(qū)之間的重疊程度以及重疊節(jié)點對于社區(qū)重疊程度的貢獻度。

1)基于U可計算社區(qū)與社區(qū)之間的相關性Z=UTU，而Z中非對角線元素即代表不同社區(qū)之間的重疊程度的測量值，計算公式如式(7)所示。

(7)

根據(jù)式(7)測量結果可知，示例網(wǎng)絡的所有重疊社區(qū){k1,k2},{k1,k3},{k2,k3},{k3,k4}中，社區(qū)k1與k2之間重疊程度最高，而社區(qū)k3與k4之間重疊程度最低。

2)基于U可計算重疊節(jié)點對于社區(qū)重疊程度的貢獻度B，計算公式如(8)所示。B值取值較大的節(jié)點在社區(qū)之間的連接及通信方面起到較為重要的作用，對于社區(qū)之間的連接穩(wěn)定性具有重要影響，因此其重要程度較高。通過重疊節(jié)點的貢獻度計算，可精確判定重疊節(jié)點的重要性大小，有助于分析及預測網(wǎng)絡社區(qū)結構的動態(tài)演化特性。

(8)

根據(jù)示例網(wǎng)絡計算結果可知，對于重疊程度最高的兩社區(qū)k1與k2，重疊節(jié)點v4、v5和v6對于社區(qū)重疊程度的貢獻度分別為40.06%、36.85%和23.06%，即節(jié)點v4的貢獻程度最高，因此其重要性最大，對于社區(qū)結構的演化起到關鍵性決定作用。

1.3.4 反映重疊節(jié)點的連邊強度差異

2 離散重疊社區(qū)檢測方法及性能分析

目前離散重疊社區(qū)檢測仍然是復雜網(wǎng)絡重疊社區(qū)檢測領域的研究重點和熱點[1-5]?，F(xiàn)有絕大多數(shù)重疊社區(qū)檢測方法所得檢測結果均為離散重疊劃分，檢測目標及評價準則為精確、高效、穩(wěn)定地提取出網(wǎng)絡中的重疊社區(qū)結構，并盡可能提升對于規(guī)模較大、社區(qū)模糊程度較高、重疊程度較高的復雜網(wǎng)絡的檢測能力。離散重疊社區(qū)檢測的典型代表性方法主要包括以下幾類，包括派系過濾、鏈接聚類、局部擴展、模塊度優(yōu)化、多目標優(yōu)化和標簽傳播等，以下分別予以說明。

2.1 派系過濾

派系過濾(Clique Percolation)，如CPM[13]、CPMw[14]、CFinder[15]、SCP[16]等。該類方法的核心概念為“全連通子圖”，核心思想為網(wǎng)絡中密度較高的連邊構成k-團，即包含k個節(jié)點的全耦合子圖，團之間通過共享節(jié)點而緊密連接，所有相鄰k-團組成的最大全連通子圖構成k-團社區(qū)。網(wǎng)絡的重疊社區(qū)結構是由多個k-團社區(qū)構成的重疊集合，通過團過濾算法識別出同時隸屬于多個不相鄰k-團的重疊節(jié)點，從而檢測出重疊社區(qū)結構。團規(guī)模參數(shù)k取[3,6]之間的較小數(shù)值容易得到較好的檢測結果。

該類方法中基于k-團的社區(qū)結構定義較為嚴格，雖然有利于發(fā)現(xiàn)網(wǎng)絡中有結合力的局部社區(qū)結構以及高度重疊的社區(qū)結構，但僅能檢測到特定的基于k-團的社區(qū)結構，使檢測精度受到影響。此外，該類方法需要得到網(wǎng)絡中所有的k-團，近似指數(shù)級的時間復雜度使該類方法不適用于大規(guī)模網(wǎng)絡中的重疊社區(qū)檢測。

2.2 鏈接劃分

鏈接劃分(Link Partitioning)，如LINK[17]、LinkComm[18]、DBLINK[19]、CDAEO[20]等。該類方法的核心思想是將鏈接而不是節(jié)點作為聚類對象，利用鏈接的相似度進行社區(qū)劃分。通常利用Jaccard指數(shù)等相似性函數(shù)計算鏈接相似度，再根據(jù)相似度進行層次聚類以獲得鏈接社區(qū)劃分，隸屬于不同社區(qū)的鏈接的交點即為重疊節(jié)點。

該類方法利用了鏈路屬性的唯一性特性，能夠在一定程度上克服基于節(jié)點的檢測方法難以識別重疊度較高的社區(qū)結構的問題，但并不能保證比基于節(jié)點的檢測方法獲得更好的社區(qū)劃分[21]。此外，該類方法通常將所有鏈接都劃分到特定的鏈接社區(qū)中，容易形成過度重疊現(xiàn)象[19]。最終的檢測結果需要將鏈接社區(qū)劃分轉化為節(jié)點社區(qū)劃分，增加了該類方法的時間復雜度。

2.3 局部擴展

局部擴展(Local Expansion)，如LFM[22]、GCE[23]、DEMON[24]、OSLOM[25]、UEOC[26]及SLEM[27]等。該類方法主要基于核心團生長進化的觀點，核心思想是從不同種子節(jié)點或離散團開始擴張，通過優(yōu)化局部效益函數(shù)探索種子節(jié)點或團所在的局部最優(yōu)社區(qū)結構，通過融合局部最優(yōu)社區(qū)結構獲得網(wǎng)絡重疊社區(qū)劃分。通常情況下采用離散團作為初始種子能夠獲得更好的檢測效果，有利于發(fā)現(xiàn)具有高度重疊特性的社區(qū)結構。

該類方法能夠同時獲得重疊社區(qū)劃分和多層次社區(qū)劃分，局部搜索方法使其需要相對較少的局部信息，并具有較快的搜索速度，因此適用于大規(guī)模網(wǎng)絡重疊社區(qū)檢測。然而，種子節(jié)點的選取、局部效益函數(shù)的構建、效益函數(shù)優(yōu)化質量等對于檢測結果有較大影響，若種子選取不佳或局部效益函數(shù)優(yōu)化性能不足，容易使檢測結果陷入局部最優(yōu)。

2.4 標簽傳播

標簽傳播，如BMLPA[39]、MLPAO[40]等。該類方法的核心思想為節(jié)點通過與鄰域節(jié)點之間交互社區(qū)歸屬標簽信息，更新節(jié)點自身的社區(qū)歸屬標簽，使網(wǎng)絡中所有節(jié)點對應的標簽分布達到動態(tài)平衡，具有相同標簽的節(jié)點構成社區(qū)，而具有多個社區(qū)標簽的節(jié)點為重疊節(jié)點，由此得到重疊社區(qū)結構。

該類方法由于采用了局部搜索的思想，因此通常在計算效率上具有一定優(yōu)勢，適用于大規(guī)模復雜網(wǎng)絡社區(qū)檢測。然而，標簽更新方式存在較大差異，一方面節(jié)點標簽選擇依據(jù)通常為鄰居節(jié)點標簽中出現(xiàn)次數(shù)最多社區(qū)標簽，沒有考慮節(jié)點標簽的歷史信息；另一方面標簽傳播過程中錯誤傳播的風險較大。上述原因使得該類算法檢測結果具有較大的不確定性，容易陷入局部最優(yōu)。

2.5 模塊度優(yōu)化

該類檢測方法的關鍵在于重疊模塊度函數(shù)和啟發(fā)式優(yōu)化算法，一方面，需構建基于節(jié)點或鏈接拓撲相似性的高性能重疊模塊度函數(shù)，提升對于重疊社區(qū)劃分的評價能力以及對于最優(yōu)重疊社區(qū)劃分的搜索引導能力；另一方面，需設計高性能的優(yōu)化算法，保證在大規(guī)模社區(qū)劃分搜索空間中收斂到最優(yōu)的重疊社區(qū)劃分。該類方法由于將評價指標即重疊模塊度函數(shù)直接作為目標函數(shù)進行優(yōu)化，克服了檢測目標與評價標準之間的差異，能夠在一定程度上提升檢測精度和效率。近年來遺傳算法[33]、蟻群算法[34-35]、粒子群優(yōu)化算法[36]等基于群智能的超啟發(fā)式優(yōu)化算法相繼被用于重疊模塊度優(yōu)化，相比較于傳統(tǒng)啟發(fā)式搜索算法提升了高維復雜搜索空間中的全局收斂性能，有效提升了最優(yōu)重疊社區(qū)劃分的檢測精度。

2.6 多目標優(yōu)化

多目標優(yōu)化(Multi-Objective Optimization)，如MOGA-Net[37]、iMEA_CDPs[38]等。該類方法的核心思想為通過增加社區(qū)劃分質量評價目標函數(shù)，提升對社區(qū)劃分的綜合評價能力以及檢測過程中對于最優(yōu)社區(qū)劃分搜索的多方向引導能力。多目標優(yōu)化能夠在單次運算中獲得多樣化、多層次、多分辨率的Pareto最優(yōu)重疊社區(qū)劃分集合，能夠使檢測所得重疊社區(qū)劃分在模塊性、精確性和重疊性等方面的性能達到最佳平衡，同時為用戶提供多樣化的檢測結果，滿足用戶多樣化檢測需求。

該類方法的關鍵在于構建合理、高效的目標函數(shù)集合，前期實踐經驗表明，具有負相關性的目標函數(shù)集合能夠獲得質量更優(yōu)的社區(qū)劃分。然而，目前現(xiàn)有算法的目標函數(shù)多憑經驗設定，對于目標函數(shù)的種類、精確性、穩(wěn)定性及函數(shù)之間的相關性缺乏較為系統(tǒng)的分析和理論性指導。由于重疊社區(qū)檢測除了需要滿足社區(qū)劃分在精確性和模塊性上的性能需求，還要使社區(qū)劃分的重疊性盡可能達到最優(yōu)，因此多目標優(yōu)化中目標函數(shù)的選擇或構建需要從以下三方面考慮。首先，需要考慮目標函數(shù)的精確性、對于社區(qū)結構模糊程度的適應性以及函數(shù)自身的穩(wěn)定性，保證在多樣且模糊的網(wǎng)絡環(huán)境下獲得盡可能精確的檢測結果；其次，需要盡可能選擇負相關性較大的目標函數(shù)集合，獲得盡可能多樣化的Pareto最優(yōu)劃分集合；最后，需要高質量的重疊特性評價函數(shù)，保證社區(qū)劃分的重疊質量。

圖4 社區(qū)劃分拓撲質量評價函數(shù)的相關性

目前常用的社區(qū)劃分拓撲質量評價函數(shù)主要包括f1=Modularity、f2=Conductance、f3=Community Score，f4=Average ODF、f5=Cut Ratio、f6=Expansion和f7=Internal Density等。對其進行實驗測試的統(tǒng)計結果表明，f1,f2,f3和f4具有相對較好的精確度，能夠有效逼近真實社區(qū)結構；隨著網(wǎng)絡社區(qū)結構模糊程度的增強，各函數(shù)的檢測性能均存在不同程度的下降，而f1和f3表現(xiàn)出較為優(yōu)越的穩(wěn)定性，對社區(qū)結構模糊性的適應能力較強；f2,f5和f6則具有相對良好的穩(wěn)定性，能夠獲得較為穩(wěn)定的社區(qū)劃分結果；函數(shù)之間的相關性如圖4所示，根據(jù)函數(shù)之間的皮爾遜相關系數(shù)(Pearson Correlation Coefficient)可看出，f1和f7，f3和f4以及f3和f7之間存在較強的負相關性，因此適合于構建多目標優(yōu)化函數(shù)集合。社區(qū)重疊特性包括重疊質量(Overlap Quality)和重疊覆蓋(Overlap Coverage)兩方面，對應評價指標函數(shù)主要有準確率Precision、召回率Recall和綜合性指標F-score等，其作為目標函數(shù)的優(yōu)化性能以及與社區(qū)質量目標函數(shù)之間的相關性仍有待于進一步研究。

上述對于離散重疊社區(qū)檢測方法的分類主要基于識別重疊社區(qū)結構時采用的關鍵技術，不同類別的檢測方法之間沒有絕對的界限，各類檢測方法的分類總結如表2所示。近年來的離散重疊社區(qū)檢測研究傾向于將不同類別的檢測方法進行融合，通過結合不同類型方法的優(yōu)勢提高重疊社區(qū)結構的檢測質量。例如，模塊度優(yōu)化和多目標優(yōu)化通常與標簽傳播相融合，檢測過程中首先利用標簽傳播速度快的優(yōu)勢獲得具有一定社區(qū)結構的優(yōu)質初始種群，再對其進行優(yōu)化獲得最優(yōu)重疊社區(qū)劃分[30]。

綜上所述，目前離散重疊社區(qū)檢測研究已取得了豐碩的研究成果，在重疊社區(qū)結構的檢測能力及檢測效率上均取得了較大進展。然而，現(xiàn)有檢測方法由于算法設計及離散重疊概念本身的限制，在真實復雜網(wǎng)絡的重疊社區(qū)檢測中仍存在一些關鍵性問題有待解決：

1)檢測算法的設計和性能對社區(qū)檢測結果形成制約。現(xiàn)有離散重疊社區(qū)檢測算法檢測到的重疊節(jié)點數(shù)量通常不準確，大部分算法檢測得到的重疊節(jié)點數(shù)量偏少，僅占實際數(shù)量的30%左右[4]，而部分算法則存在“過度重疊”現(xiàn)象[19]。此外，為簡化檢測問題和算法設計，現(xiàn)有離散重疊社區(qū)檢測中通常將重疊節(jié)點能夠隸屬的最大社區(qū)數(shù)目統(tǒng)一設置為某一數(shù)值，如通常設置為2，即每個重疊節(jié)點僅能夠同時隸屬于兩個社區(qū)，限制了重疊節(jié)點的重疊程度，人為降低了重疊社區(qū)結構的復雜度，導致其與真實網(wǎng)絡社區(qū)結構存在較大差異。

2)離散重疊概念對社區(qū)檢測功能造成限制。在離散重疊概念下，不論何種類型的檢測方法檢測到的重疊節(jié)點對所屬社區(qū)均具有絕對且完全的隸屬關系，即隸屬程度全部為“1”。從檢測結果中我們無法判別出重疊節(jié)點與多個不同所屬社區(qū)之間的隸屬程度，也無法判別出同一社區(qū)內不同節(jié)點的隸屬程度差異。因此，離散重疊社區(qū)檢測對重疊節(jié)點隸屬程度以及重疊社區(qū)結構內在深層次拓撲特性的探索能力上均存在欠缺，使其無法有效反映出真實復雜網(wǎng)絡中重疊社區(qū)結構的復雜性和模糊性，不適用于真實世界中較為復雜的重疊網(wǎng)絡社區(qū)檢測問題。

表2 離散重疊典型社區(qū)檢測方法Tab. 2 Typical methods of crisp overlapping detection

3 模糊重疊社區(qū)檢測方法及性能分析

模糊重疊社區(qū)檢測從原理上克服了離散重疊社區(qū)檢測固有的功能性欠缺，其本質上是對離散重疊社區(qū)檢測的強化和功能性擴展。該類檢測方法一方面能夠通過模糊隸屬度分布精確衡量節(jié)點與社區(qū)之間精確化、細粒化的隸屬強度關系，提升真實復雜網(wǎng)絡環(huán)境下重疊社區(qū)結構的檢測精度；另一方面，能夠在所得社區(qū)劃分中完整體現(xiàn)所有重疊節(jié)點的社區(qū)隸屬度分布，有助于揭示重疊社區(qū)結構中隱含的深層次拓撲信息。以下分別對模糊重疊社區(qū)檢測的兩項功能優(yōu)勢進行說明：

1)模糊重疊社區(qū)檢測中模糊隸屬度的計算有助于提升重疊社區(qū)結構檢測的精確性。模糊重疊社區(qū)檢測將節(jié)點對于任意社區(qū)的隸屬程度歸一化到[0,1]十進制連續(xù)取值空間內，大幅提升了對于隸屬關系的量化程度，以及對于節(jié)點與社區(qū)之間隸屬強度的刻畫及區(qū)分能力。檢測過程中根據(jù)節(jié)點對社區(qū)的隸屬度取值分布，可以獲知當前社區(qū)劃分中每個節(jié)點對各個社區(qū)的隸屬程度強弱關系。依據(jù)該信息及真實網(wǎng)絡環(huán)境下的“重疊”判定標準及檢測需求，可以更加精準、靈活地控制重疊節(jié)點的數(shù)目、重疊節(jié)點能夠隸屬的最大社區(qū)數(shù)目及重疊社區(qū)分布，在檢測過程中避免對所有重疊節(jié)點統(tǒng)一設置的粗放式簡化處理。因此，模糊重疊社區(qū)檢測能夠有效增強真實網(wǎng)絡中重疊社區(qū)結構的識別和檢測能力，更能夠滿足重疊社區(qū)檢測中的復雜性需求。

2)真正的模糊重疊社區(qū)檢測，其檢測結果不僅能夠體現(xiàn)出重疊節(jié)點及其社區(qū)分布，而且能夠體現(xiàn)出所有節(jié)點對各個社區(qū)完整且相對的隸屬度數(shù)值分布。根據(jù)重疊節(jié)點的隸屬度分布，一方面能夠精確反映出同一重疊節(jié)點對不同社區(qū)的不同隸屬程度，以及同一社區(qū)內不同節(jié)點對本社區(qū)的隸屬程度；另一方面，根據(jù)重疊節(jié)點的隸屬度分布，以及網(wǎng)絡拓撲結構中重疊節(jié)點與不同社區(qū)之間的連接情況，能夠揭示出重疊社區(qū)結構的深層次拓撲信息，包括重疊節(jié)點的重疊程度差異、社區(qū)重疊程度差異、重疊節(jié)點對社區(qū)重疊的貢獻度及節(jié)點重要性等，并可在一定程度上挖掘出重疊社區(qū)結構中隱含的拓撲連接強度信息。因此，模糊重疊社區(qū)檢測能夠更深入地體現(xiàn)重疊社區(qū)結構中的拓撲關系。

基于上述分析可知，模糊重疊社區(qū)檢測能夠更好地滿足復雜網(wǎng)絡重疊社區(qū)檢測的兩項核心任務，使檢測結果更好地體現(xiàn)出重疊社區(qū)結構的復雜性和模糊性，因而更適用于真實復雜網(wǎng)絡環(huán)境下的重疊社區(qū)檢測問題，是目前該領域中最前沿、性能最優(yōu)且最具發(fā)展前景的一類重疊社區(qū)檢測方法。然而，雖然模糊重疊社區(qū)檢測相比較于傳統(tǒng)重疊社區(qū)檢測方法在功能性上具備明顯優(yōu)勢，但由于其檢測過程中需要定量評估每個節(jié)點對各社區(qū)的隸屬度分布，因此檢測所需信息量較大、檢測結果體現(xiàn)內容較多、檢測難度也相對較高，對算法的設計和性能均提出了較高要求。目前國內外對于模糊重疊社區(qū)檢測方法的研究相對較少[1-3]，雖然部分算法利用了隸屬度測度確定重疊節(jié)點，但現(xiàn)有隸屬度計算大多僅以節(jié)點連邊數(shù)量為依據(jù)且難以在檢測結果中體現(xiàn)出完整相對的隸屬度分布，在模糊重疊的實現(xiàn)能力和實現(xiàn)效果上均存在不足，現(xiàn)階段模糊重疊社區(qū)檢測算法的研究仍處于起步階段。

根據(jù)網(wǎng)絡分析需求及用戶解釋的不同，模糊重疊社區(qū)檢測問題可構造為多種不同形式，對應檢測算法之間存在較大差異。根據(jù)重疊節(jié)點模糊隸屬度獲取方式的不同，本文將當前國內外現(xiàn)有的基于模糊重疊思想的社區(qū)檢測方法分為五類進行闡述，包括擴展標簽傳播、非負矩陣分解、基于邊界節(jié)點的兩階段檢測、模糊聚類及模糊模塊度優(yōu)化，以下分別對各類檢測方法進行詳細說明。

3.1 基于擴展標簽傳播的模糊重疊社區(qū)檢測

擴展的標簽傳播算法是目前較為常見的一類模糊重疊社區(qū)檢測方法，其在離散重疊社區(qū)檢測的基本框架上融入了模糊重疊的思想，在為每個節(jié)點維護標簽集合的同時計算并保存節(jié)點對標簽代表社區(qū)的模糊隸屬度。算法的核心思想為根據(jù)節(jié)點的鄰域節(jié)點數(shù)目及相應標簽數(shù)目，計算節(jié)點對鄰域節(jié)點所屬社區(qū)的隸屬度，并通過設定隸屬度閾值更新標簽集合并確定節(jié)點的社區(qū)歸屬，由此得到重疊節(jié)點及其重疊社區(qū)劃分。

該類檢測方法的典型代表算法包括COPRA算法[41]、SLPA算法[42]及LPPB算法[9]等。COPRA是Gregory于2010年提出的首個基于標簽傳播的模糊重疊社區(qū)檢測算法，節(jié)點標簽對中不僅含有社區(qū)名稱，而且包含節(jié)點對該社區(qū)的歸屬系數(shù)，任意節(jié)點對所有隸屬社區(qū)的歸屬系數(shù)總和為“1”。每個節(jié)點通過平均所有鄰居節(jié)點的隸屬度系數(shù)更新隸屬度分布，通過設置參數(shù)v控制節(jié)點能夠隸屬的最大社區(qū)數(shù)目。Xie等2011年提出SLPA算法，為每個節(jié)點提供存儲信息(標簽)的記憶空間，將從記憶空間中獲取標簽的概率作為節(jié)點隸屬度，無需社區(qū)數(shù)目等先驗信息。劉世超等2015年提出一種基于標簽傳播概率的LPPB算法，將節(jié)點獲得社區(qū)標簽的概率作為隸屬度，設置隸屬度閾值為節(jié)點能夠隸屬最大社區(qū)數(shù)目的倒數(shù)，綜合網(wǎng)絡的結構傳播特性和節(jié)點的屬性特征共同計算標簽傳播的概率。

基于擴展標簽傳播的模糊重疊社區(qū)檢測最大優(yōu)勢在于具有較高的運算效率，通常具有接近線性的計算復雜度，當網(wǎng)絡社區(qū)結構較為清晰時能夠獲得較好的模糊重疊社區(qū)劃分，可處理加權、有向及二分網(wǎng)絡。然而，該類檢測方法也存在一些不足：1)標簽更新過程中，通常需要根據(jù)預定且統(tǒng)一設置的節(jié)點最大標簽數(shù)確定隸屬度閾值，通過閾值限定重疊節(jié)點隸屬社區(qū)個數(shù)及社區(qū)分布。節(jié)點最大標簽數(shù)即節(jié)點隸屬最大社區(qū)個數(shù)取值直接影響社區(qū)劃分的重疊性和模塊性，取值過低將限制重疊節(jié)點數(shù)量及重疊程度，取值過高則導致過度重疊或重復社區(qū)。因此，該參數(shù)合理取值十分關鍵，但目前仍缺乏統(tǒng)一有效的設置方法，對其進行最優(yōu)化設置通常導致較高的計算復雜度；2)由于標簽傳播過程通常具有一定的隨機性且不同節(jié)點的標簽傳播能力不同，因此當網(wǎng)絡社區(qū)結構較為模糊或社區(qū)間重疊程度較高時檢測精度將大幅下降。

3.2 基于非負矩陣分解的模糊重疊社區(qū)檢測

非負矩陣分解(Non-negative Matrix Factorization, NMF)是機器學習領域中一種常用的特征提取和維度減少算法，近年來被用于求解模糊重疊社區(qū)檢測問題。算法的核心思想認為社區(qū)的形成源于共享群體從屬關系，一個節(jié)點同時可隸屬于多個社區(qū)，而兩節(jié)點之間的交互程度越高，隸屬于同一社區(qū)的概率越大，共享社區(qū)的數(shù)目也越多。算法將代表節(jié)點之間期望交互次數(shù)或相似程度的特征矩陣V在非負約束(V≈WH)下分解為兩個相乘的矩陣W和H，其中矩陣W代表了節(jié)點對不同社區(qū)的隸屬度分布，歸一化矩陣W中的每個元素w衡量了相應節(jié)點與社區(qū)的隸屬程度。該類檢測方法的典型代表算法包括Zhao等2010年提出的對稱NMF算法s-NMF[43]，Psorakis等2011年提出的貝葉斯NMF算法[44]，李玉翔提出的基于貝葉斯先驗的NMF算法BNMF-CD[45]。

該類算法的最大優(yōu)勢在于檢測結果中能夠定性和定量地評價節(jié)點對所屬社區(qū)隸屬關系的絕對程度，然而存在的不足之處包括：1)矩陣乘法使其需要耗費較多的計算時間和存儲空間，進行高維矩陣分解時復雜度較高，不適用于規(guī)模較大的網(wǎng)絡；2)傳統(tǒng)NMF算法通常需要預先給定或通過優(yōu)化模塊度來確定社區(qū)數(shù)目[46]，不可避免會帶來較高的計算開銷；3)為了根據(jù)隸屬度分布確定重疊社區(qū)結構，通常需要人為設定隸屬度閾值，以確定各節(jié)點與社區(qū)之間的最終隸屬關系，但由于閾值設置的精確性和穩(wěn)定性限制，所得重疊社區(qū)劃分的質量造成影響。

3.3 基于邊界節(jié)點的兩階段模糊重疊社區(qū)檢測

基于邊界節(jié)點的兩階段檢測方法是目前研究較多的一類模糊重疊社區(qū)檢測方法。核心概念為“邊界節(jié)點”或稱“連接節(jié)點”，即社區(qū)硬劃分中不僅與自身所在社區(qū)存在連接，而且與其他社區(qū)存在連接的節(jié)點。核心思想為“邊界節(jié)點”不論是在拓撲結構還是在功能層面均具有多面性，因而是重疊節(jié)點的主要來源。

圖5 基于邊界節(jié)點的兩階段模糊重疊社區(qū)檢測

該類方法在檢測過程中不限定具體的檢測算法，而是采用一種通用的基于邊界節(jié)點的兩階段檢測模式，流程圖如圖5所示，相應的操作流程說明如下：1)第一階段采用現(xiàn)有較為成熟的社區(qū)檢測方法，如快速模塊度算法CNM[47]、LM算法[48]等，進行社區(qū)結構的硬劃分。識別硬劃分中社區(qū)內與其他社區(qū)存在連接的“邊界節(jié)點”，以及具有單一社區(qū)歸屬的“孤立節(jié)點”，兩類節(jié)點在圖5中分別用空心和實心圓圈表示。2)第二階段通過影響系數(shù)函數(shù)Md計算[47]、基于局部信息的鄰居投票機制[48]、基于混合整數(shù)非線性規(guī)劃模型OverMod的局部模塊度優(yōu)化[49]等方法，度量“邊界節(jié)點”對鄰域社區(qū)的貢獻或計算“邊界節(jié)點”對鄰域社區(qū)的隸屬度，根據(jù)貢獻大小或隸屬度數(shù)值確定“邊界節(jié)點”最終的社區(qū)歸屬，由此得到社區(qū)硬劃分對應的重疊社區(qū)軟劃分。該類檢測方法的典型代表算法包括2014年西安電子科技大學劉勇提出基于快速模塊度算法CNM和新的影響系數(shù)函數(shù)Md的兩階段檢測算法[47]；2014年陳俊宇等基于LM和新的鄰居投票機制兩階段檢測算法LM-NV[48]；2014年Laura Bennett等提出基于新混合整數(shù)非線性規(guī)劃模型OverMod的兩階段檢測算法[49]等。

該類算法通常能夠快速有效地得到網(wǎng)絡的重疊社區(qū)結構。一方面，由于只需考慮“邊界節(jié)點”的重疊性，大幅減少了重疊節(jié)點檢測的計算復雜度；另一方面，由于有效結合了現(xiàn)有的非重疊社區(qū)檢測算法，使算法的通用性和可移植性得到提升。然而，該類算法的問題主要包括以下兩點：1)重疊節(jié)點的檢測質量很大程度上依賴于第一階段的社區(qū)硬劃分結果，若硬劃分準確度較低會嚴重影響重疊節(jié)點的檢測質量，容易導致錯分點并使重疊節(jié)點判斷誤差增大，使重疊社區(qū)劃分的精確性和穩(wěn)定性受到制約。2)該類方法基于一個默認的前提假設，即通過在優(yōu)質的社區(qū)硬劃分上識別重疊節(jié)點能夠獲得優(yōu)質的重疊社區(qū)劃分。然而，實驗結果證明最優(yōu)的重疊社區(qū)劃分可能不是由最優(yōu)的硬劃分生成得來的[44]，因此該項假設的合理性和通用性仍有待于進一步研究。

3.4 基于模糊聚類的模糊重疊社區(qū)檢測

模糊聚類檢測算法也是一種常見的模糊重疊社區(qū)檢測方法。該類方法的基本思想為網(wǎng)絡中連接相對緊密的節(jié)點構成社區(qū)，將社區(qū)看作對象(節(jié)點或團體)之間緊密連接關系的集合，任意對象對于任意集合的連接緊密程度用介于0和1之間的模糊隸屬度進行度量，根據(jù)對象與集合之間的隸屬度進行模糊聚類從而獲得重疊社區(qū)結構。該類算法中較為通用的操作流程如下：首先將網(wǎng)絡節(jié)點映射為歐式空間中的數(shù)據(jù)點集，然后通過構建“距離”因子(如余弦距離等)，衡量節(jié)點與節(jié)點、節(jié)點與社區(qū)、社區(qū)與社區(qū)之間的相似度，最后依據(jù)相似度進行模糊C均值聚類FCM[50-51]、概率C均值聚類PCM[5]等聚類操作，得到最終的重疊社區(qū)結構。

該類檢測方法的典型代表性算法包括2013年Wang等提出基于FCM的模糊聚類算法，通過隨機游走和SRW局部相似性測度計算并構建節(jié)點之間的距離矩陣，將其映射到低維空間并利用FCM進行聚類[51]。該算法雖然能夠得到模糊重疊社區(qū)劃分，但檢測所得社區(qū)結構的模塊度較低。2015年Samira等提出基于改進PCM的模糊聚類算法，由于節(jié)點對社區(qū)的隸屬度總和不為“1”，因此無法得到真正的模糊重疊社區(qū)劃分[5]。2015年西安交通大學李劉強等提出基于模糊層次聚類的CDHC算法，由于僅在社區(qū)內部計算節(jié)點對本社區(qū)的隸屬度，使隸屬度具有局部性和絕對性，無法體現(xiàn)節(jié)點對于各社區(qū)完整且相對的隸屬度分布[52]。2015年Suman Kundu等提出一種新的基于模糊粒度理論(Fuzzy Granular Theory)的知識表示框架用于社交網(wǎng)絡的模糊重疊社區(qū)檢測，即以網(wǎng)絡代表性節(jié)點為中心，合并連接緊密的鄰域節(jié)點形成微粒并將其表示為模糊集，由此將網(wǎng)絡表示成為模糊粒子集合。新算法FRC-FGSN能夠在基于粒度模型的知識表示框架下，檢測到以模糊-粗糙形式定義的社區(qū)結構[53]。

該類檢測方法中，如何有效衡量節(jié)點與社區(qū)之間的相似度對檢測結果具有重要影響。相似性測度分為局部相似性測度和全局相似性測度兩種，其中局部相似性測度計算僅需節(jié)點度及最近鄰域信息，而全局相似性測度計算則需要網(wǎng)絡拓撲全局信息?，F(xiàn)有算法通常采用基于“距離”因子的局部拓撲相似性測度[50-53]，計算相對簡單但精確度較低，此外由于部分“距離”因子中權重參數(shù)設置困難、相似度閾值和隸屬度閾值設置困難等原因，“距離”相似度測量精度受到限制，使聚類質量即社區(qū)劃分結果受到影響。

3.5 基于模糊模塊度優(yōu)化的模糊重疊社區(qū)檢測

模糊模塊度優(yōu)化(Fuzzy Modularity Maximization, FMM)是近年來新興的一類模糊重疊社區(qū)檢測方法[1]，擴展至模糊重疊的模塊度函數(shù)的相繼提出為該類檢測方法的實現(xiàn)奠定了重要的理論基礎。該類方法的基本思想是將模糊重疊社區(qū)檢測問題抽象為帶約束條件的大規(guī)模組合優(yōu)化問題，在模糊重疊模塊度函數(shù)引導下，利用優(yōu)化算法在模糊重疊約束條件對應的可行解空間內進行方向性搜索，收斂至全局最優(yōu)的重疊社區(qū)劃分，使模糊模塊度達到最優(yōu)。

基于模糊模塊度優(yōu)化的模糊重疊社區(qū)檢測方法區(qū)別于其他方法的最大不同在于采用了反向搜索的方式獲取節(jié)點對社區(qū)的最優(yōu)隸屬度分布，即在模糊重疊約束條件對應的大規(guī)?？尚须`屬度分布組合空間內，自動搜索到使模糊模塊度函數(shù)取得最優(yōu)值的節(jié)點隸屬度分布。該過程稱為反向搜索是因為社區(qū)檢測過程中不再需要基于網(wǎng)絡的拓撲結構及屬性等信息計算節(jié)點對社區(qū)的隸屬度，僅需要依據(jù)模糊模塊度在決策空間中搜索最佳的節(jié)點隸屬度分布組合。該種隸屬度計算方式具有兩項優(yōu)勢：1)避免了隸屬度計算過程中的相似度函數(shù)構建、相似度計算以及相似度閾值設置帶來的復雜性和不穩(wěn)定性；2)獲得的最終隸屬度分布是使重疊社區(qū)結構評價指標如Qov最優(yōu)化的結果，能夠體現(xiàn)重疊節(jié)點的多樣化拓撲特性差異，克服了隸屬度計算過程中由于計算指標單一(如僅計算節(jié)點連邊數(shù)目)帶來的不精確性。

該類檢測方法的關鍵技術包括兩項：1)一是選擇或構建能夠有效評價模糊重疊社區(qū)劃分質量的擴展模糊模塊度函數(shù)，提升對模糊重疊社區(qū)劃分的評價能力，避免評價過程中從模糊重疊社區(qū)劃分到離散重疊劃分或硬劃分的轉化，此外充分發(fā)揮其在目標空間搜索過程中的方向性引導作用。2)二是用于模糊模塊度優(yōu)化的優(yōu)化算法設計，主要包括啟發(fā)式優(yōu)化算法和超啟發(fā)式優(yōu)化算法兩種，充分發(fā)揮優(yōu)化算法的智能化搜索能力和全局最優(yōu)化能力，以獲得全局最優(yōu)的模糊重疊社區(qū)劃分。

3.6 模糊重疊社區(qū)檢測方法性能分析

匯總上述五類模糊重疊社區(qū)檢測方法如表3所示。

現(xiàn)有檢測方法能夠通過不同方式獲取節(jié)點對于不同社區(qū)的精確化、細?；`屬度分布，有效增強了對于節(jié)點與社區(qū)之間歸屬關系的判定能力，從而獲得高質量的重疊社區(qū)劃分。然而，現(xiàn)有模糊重疊社區(qū)檢測方法在檢測性能及檢測功能方面仍存在一定不足：

1)現(xiàn)有算法存在檢測過程依賴于社區(qū)結構的硬劃分、重疊節(jié)點挖掘依賴于復雜的相似度和隸屬度計算、相似度閾值和隸屬度閾值的合理設置困難、缺乏有效的模糊重疊社區(qū)劃分質量評價指標、檢測結果需轉化為離散重疊社區(qū)劃分或硬劃分進行評價等問題，使得檢測算法普遍存在設計復雜、穩(wěn)定性不足、通用性和易操作性差等缺陷。

2)現(xiàn)有大部分檢測方法僅是借鑒了“模糊重疊”的思想，即雖然在判定節(jié)點社區(qū)歸屬及重疊節(jié)點時計算了節(jié)點對鄰域社區(qū)的隸屬度，但該隸屬度計算大多具有局部性和絕對性。社區(qū)劃分結果中沒有體現(xiàn)節(jié)點對于各社區(qū)滿足約束條件的完整且相對隸屬度分布，檢測結果絕大多數(shù)仍為離散重疊社區(qū)劃分，因此嚴格意義上并不屬于真正的模糊重疊社區(qū)檢測，也無法基于隸屬度分布進一步揭示重疊社區(qū)結構中的深層次拓撲關系，模糊重疊社區(qū)檢測特有的功能性優(yōu)勢沒有得到很好地實現(xiàn)。

表3 模糊重疊典型社區(qū)檢測方法Tab.3 Typical methods of fuzzy overlapping detection

盡管Gregory的最新研究成果中提出一種“MakeFuzzy”方法[6]，能夠根據(jù)重疊節(jié)點對所屬社區(qū)的連邊數(shù)目計算隸屬度，將離散重疊社區(qū)劃分轉化為模糊重疊社區(qū)劃分。然而，由于一方面隸屬度計算僅依據(jù)鄰居節(jié)點數(shù)目，計算標準僅采用單一化的度信息，使隸屬度估計的精確性受到制約；另一方面僅計算節(jié)點對自身所在社區(qū)的隸屬度或貢獻程度，因此該隸屬度計算具有局部性和絕對性，對節(jié)點與所有社區(qū)之間的真實隸屬程度評估的完整性受到影響。上述原因使轉化所得模糊重疊社區(qū)劃分并不能很好地體現(xiàn)真實重疊社區(qū)結構的復雜性和模糊性。

現(xiàn)有的模糊重疊社區(qū)檢測方法中，模糊模塊度優(yōu)化方法由于具有檢測過程無需獲得社區(qū)結構硬劃分、重疊節(jié)點挖掘不依賴于復雜的相似度和隸屬度計算、社區(qū)劃分質量評價函數(shù)與優(yōu)化目標函數(shù)無差異、檢測結果能夠完整體現(xiàn)所有節(jié)點對各社區(qū)的隸屬度分布、操作簡單易實現(xiàn)等諸多性能優(yōu)勢，成為目前功能性相對最強且最具發(fā)展?jié)摿Φ囊活悪z測方法。然而，由于模糊模塊度函數(shù)最優(yōu)化本質上仍是一個典型的NP難問題，一般算法很難在規(guī)定時間內求得滿意的最優(yōu)解[1-3,55-57]，而模糊重疊社區(qū)檢測由于不僅優(yōu)化節(jié)點社區(qū)歸屬而且優(yōu)化節(jié)點隸屬度分布，進一步擴張了最優(yōu)化問題的決策空間及目標空間，加劇了模塊度優(yōu)化時存在的極端退化[58]現(xiàn)象，使得全局最優(yōu)解的搜索難度大幅增加?，F(xiàn)有模塊度優(yōu)化檢測方法中普遍使用的貪心法[59,60]、模擬退火[61,62]、譜方法[63]、極值優(yōu)化[64]、數(shù)學規(guī)劃法[65,66]等最優(yōu)化算法，均屬于基本啟發(fā)式最優(yōu)化方法，雖然具有理論比較成熟、設計簡單、魯棒性強、速度快等優(yōu)勢，但通常存在全局尋優(yōu)能力不足、求解精度低、易陷入局部最優(yōu)等缺陷，不僅難以得到全局最優(yōu)的社區(qū)劃分，而且在求解規(guī)模較大、搜索復雜度較高的全局最優(yōu)化問題時存在搜索效率急劇下降的問題[10]，因而使復雜網(wǎng)絡社區(qū)檢測中模糊模塊度函數(shù)的最優(yōu)化性能受到較大影響。

進化算法(Evolutionary Algorithms, EAs)作為智能優(yōu)化領域中國內外公認的求解NP難問題最有效的超啟發(fā)式最優(yōu)化方法，不僅對優(yōu)化問題的種類有較強的魯棒性，而且具有強大的全局最優(yōu)化能力及自組織、自學習特性，能夠在大規(guī)模復雜搜索空間中智能化且高效地收斂到全局最優(yōu)解，基于種群進化的搜索機制使其具有更強的穩(wěn)定性，因此更適合于模糊重疊社區(qū)檢測中復雜的模糊模塊度函數(shù)最優(yōu)化問題求解。鑒于此，本文將重點對基于EAs的模糊模塊度優(yōu)化模糊重疊社區(qū)檢測方法進行分析和說明。

4 基于EAs的模糊模塊度優(yōu)化模糊重疊社區(qū)檢測

4.1 基于EAs的模糊模塊度優(yōu)化方法框架

基于EAs的模糊模塊度優(yōu)化方法框架設計思路為，將模糊重疊社區(qū)檢測問題抽象為帶約束條件的模糊隸屬度分布組合優(yōu)化問題，利用遺傳算法(Genetic Algorithm, GA)、免疫克隆算法(Immune Clone Algorithm, ICA)及粒子群優(yōu)化算法(Particle Swarm Optimization, PSO)等群智能進化算法，在節(jié)點隸屬度分布對應的連續(xù)空間內進行全局搜索，在模糊模塊度引導及模糊重疊約束條件下收斂至全局最優(yōu)的隸屬度分布，由此得到真正的模糊重疊社區(qū)劃分，并根據(jù)隸屬度分布確定重疊社區(qū)結構。

基于EAs的模糊模塊度優(yōu)化社區(qū)檢測方法的數(shù)學模型如下：不失一般性，以一個具有n個節(jié)點，c個社區(qū)和m個質量評價函數(shù)的模糊重疊社區(qū)檢測問題為例，其對應帶約束條件的節(jié)點隸屬度組合優(yōu)化問題數(shù)學模型如式(9)所示。

(9)

式中U={uik}∈Rn×c為節(jié)點隸屬度分布矩陣，uik代表節(jié)點i對于第k個社區(qū)的隸屬度，i=[n]，k=[c]。x=φ(U)為隸屬度分布U的映射，代表U對應的模糊重疊社區(qū)劃分。y=F(x)定義了由決策空間到m維目標空間的映射函數(shù)，包含m個模糊重疊社區(qū)劃分質量評價函數(shù)。當m=1時為單目標優(yōu)化問題，目標函數(shù)即為模糊模塊度函數(shù)Q；當m>1時轉化為多目標優(yōu)化問題，目標函數(shù)為包含Q在內的函數(shù)集合，衡量社區(qū)劃分在多項評價標準上的性能優(yōu)劣。

基于EAs的模糊模塊度優(yōu)化方法中，種群個體在初始化及進化過程中需滿足模糊重疊社區(qū)檢測對應的多項約束條件，具體包括：1)滿足可行社區(qū)劃分對應的一般約束條件以保證個體的合法性。2)滿足模糊重疊特性對應的兩項特殊約束條件：任一節(jié)點i對任一社區(qū)k的隸屬度uki在[0,1]范圍內取值；任一節(jié)點i對所有社區(qū)的隸屬度總和取值恒為“1”。EAs在上述約束條件限定的節(jié)點隸屬度分布可行連續(xù)空間內進行全局搜索，收斂到使集合F中目標函數(shù)同時達到最優(yōu)的隸屬度分布U*，對應最優(yōu)的模糊重疊社區(qū)劃分為x*=argmaxF(x)。

構建通用的基于EAs的模糊模塊度優(yōu)化方法基本流程框架如圖6所示，對應具體步驟描述如下：

步驟1 對種群個體進行編碼并構建初始種群，解碼獲得個體對應的初始社區(qū)劃分。

步驟2 在不同類型的編碼方式下獲得種群個體對應的模糊重疊社區(qū)劃分。若采用非隸屬度矩陣編碼，按照一定準則計算初始社區(qū)劃分中每個節(jié)點對各社區(qū)的隸屬度分布；若采用隸屬度矩陣編碼，則無需隸屬度計算。

步驟3 判斷終止條件是否滿足？若滿足，則輸出當前種群中最優(yōu)模糊重疊社區(qū)劃分作為檢測結果，否則轉至步驟4。

步驟4 對父代種群執(zhí)行變異、交叉進化操作生成子代種群，進化過程保留父代個體中優(yōu)質的社區(qū)劃分基因。

步驟5 對子代種群進行Clean-Up操作，修正進化操作中社區(qū)劃分錯誤的節(jié)點，使鄰域節(jié)點盡可能劃分至同一社區(qū)。

步驟6 對修正后的子代種群個體進行適應度值評價。根據(jù)構建或選擇的Q函數(shù)的不同，判斷是否首先需要設置最優(yōu)的模糊隸屬度閾值。若需要閾值設置，則根據(jù)實驗經驗或一定的優(yōu)化方法進行設置，根據(jù)閾值將模糊重疊社區(qū)劃分轉化為相應的離散重疊社區(qū)劃分或硬劃分，再計算其模塊度函數(shù)值。若不需要閾值設置，則直接對模糊重疊社區(qū)劃分進行模糊模塊度計算。

步驟7 判斷目標函數(shù)個數(shù)m是否大于1，即是否為多目標優(yōu)化。若為單目標優(yōu)化，則直接根據(jù)子代種群個體的Q值進行精英選擇，保留優(yōu)質個體進入下一代父代種群，轉至步驟3；若為多目標優(yōu)化，則首先計算子代種群個體的其他目標函數(shù)值，并對合并之后的父代子代種群集合進行Pareto非支配排序及個體密度估計，然后根據(jù)個體精確性和分布性結果進行環(huán)境選擇，保留同等規(guī)模的Pareto最優(yōu)個體進入下一代父代種群，轉至步驟3。

上述檢測流程中需要說明的是，當模糊隸屬度函數(shù)能夠直接對節(jié)點隸屬度分布對應的模糊重疊社區(qū)劃分進行質量評價時，無需根據(jù)隸屬度閾值將模糊重疊社區(qū)劃分轉化為離散重疊社區(qū)劃分或硬劃分，由此可避免隸屬度閾值的設置。此外，由于多目標優(yōu)化中無法根據(jù)單個目標函數(shù)值確定唯一的最優(yōu)解，因此需要通過Pareto非支配排序和個體密度估計構建Pareto最優(yōu)的非支配解集，其中Pareto支配、Pareto最優(yōu)等多目標優(yōu)化概念在復雜網(wǎng)絡社區(qū)檢測中的定義可參見文獻[67]，文中在此不做詳述。

圖6 基于進化算法的模糊模塊度優(yōu)化檢測框架

為測試基于進化算法的模糊模塊度優(yōu)化算法性能，本文設計了基于廣義重疊模塊度函數(shù)GM和遺傳算法GA的單目標模糊模塊度優(yōu)化算法GM_GACD。為驗證該類算法的有效性，將其與目前國內外較為先進的多種社區(qū)檢測算法，在計算機生成網(wǎng)絡和真實世界網(wǎng)絡上進行性能測試。

1)非重疊社區(qū)檢測性能測試

將GM_GACD在擴展GN Benchmark網(wǎng)絡上進行社區(qū)檢測，所得社區(qū)劃分對應歸一化互信息NMI和正確節(jié)點檢測比例統(tǒng)計數(shù)據(jù)如表4所示。擴展GN Benchmark網(wǎng)絡含有128個節(jié)點，共被劃分為4個不同社區(qū)，每個社區(qū)包含32個結點，社區(qū)中每個節(jié)點的平均度數(shù)為16。隨著Zout值的增加，網(wǎng)絡社區(qū)結構模糊程度逐漸增強，精確檢測出社區(qū)結構的難度大幅提升。從實驗結果可以看出，當Zout>7時GM_GACD仍然能夠獲得較好的檢測精度，說明算法能夠有效實現(xiàn)非重疊網(wǎng)絡社區(qū)檢測且具有較好的穩(wěn)定性。

表4 GM_GACD算法在GN網(wǎng)絡上檢測結果

將GM_GACD與多種社區(qū)檢測算法FN、GN、VSGD[41]、MSFCM[2]、FMM/H1[1]、MOGA-Net[22]和MA[48]等，在斯坦福大學網(wǎng)絡數(shù)據(jù)集中的4種真實網(wǎng)絡上進行測試，采用標準模塊度函數(shù)Q測量算法所得非重疊社區(qū)劃分質量，實驗統(tǒng)計結果如表5所示，表中數(shù)據(jù)為各算法獨立運行20次的平均最優(yōu)值，各項對比實驗中的最優(yōu)結果均用黑體加粗表示。

從表5中統(tǒng)計數(shù)據(jù)可以看出，GM_GACD相比較于其他算法能夠得到相對較優(yōu)的模塊度數(shù)值Q，說明其不僅能夠在真實網(wǎng)絡上檢測出較為精確的社區(qū)結構，而且能夠有效識別出社區(qū)結構中的小團體，實現(xiàn)多尺度社區(qū)劃分。

表5 GM_GACD算法在真實網(wǎng)絡上非重疊社區(qū)檢測結果

2)重疊社區(qū)檢測性能測試

為測試GM_GACD在重疊網(wǎng)絡上的社區(qū)檢測性能，將GM_GACD與LINK、COPRA、CFinder、CPM和LFM幾種代表性重疊社區(qū)檢測算法，在斯坦福大學網(wǎng)絡數(shù)據(jù)集中的4種真實網(wǎng)絡上進行性能測試，采用具有重疊結構的模塊度Qov評價算法對于重疊社區(qū)結構的檢測性能，實驗結果如表6所示，表中數(shù)據(jù)為各算法獨立運行20次的平均最優(yōu)值，各項對比實驗中的最優(yōu)結果均用黑體加粗表示。

表6 GM_GACD算法在真實網(wǎng)絡上重疊社區(qū)檢測結果Tab.6 Overlapping community detection results of GM_GACD on real-world networks

從表6中統(tǒng)計數(shù)據(jù)可以看出，GM_GACD相比較于其他算法能夠得到相對較優(yōu)的模糊模塊度數(shù)值Qov，說明其能夠有效提取出真實網(wǎng)絡中的重疊社區(qū)結構。此外，根據(jù)GM_GACD模糊重疊社區(qū)檢測結果所得隸屬度分布，能夠測量節(jié)點的重疊程度差異分布，如Karate網(wǎng)絡和PolBooks網(wǎng)絡中各節(jié)點的重疊程度如圖7-8所示，節(jié)點顏色熱度圖分布對應節(jié)點重疊程度大小。

圖7 Karate網(wǎng)絡節(jié)點重疊程度分布圖

圖8 PolBooks網(wǎng)絡節(jié)點重疊程度分布圖

4.2 基于EAs的模糊模塊度優(yōu)化關鍵技術及挑戰(zhàn)

由上述實驗分析可以看出，基于EAs的模糊模塊度優(yōu)化方法不僅能夠獲得相對較優(yōu)的非重疊社區(qū)結構，而且能夠挖掘出真實社區(qū)中存在的小團體；不僅能夠實現(xiàn)重疊社區(qū)檢測，而且能夠獲得真正的模糊重疊社區(qū)劃分?；谀：`屬度分布，能夠測得網(wǎng)絡節(jié)點的重疊程度分布等深層次重疊社區(qū)結構信息，加強對于真實重疊社區(qū)結構中復雜且模糊拓撲結構的探索能力。盡管模糊重疊社區(qū)檢測算法在檢測功能上具備一定優(yōu)勢，但由于重疊社區(qū)檢測算法發(fā)展尚未成熟，模糊重疊社區(qū)檢測問題本身的復雜度較高且檢測難度較大，因此現(xiàn)階段針對該類算法的研究仍處于起步階段，在實際應用中仍然面臨若干關鍵挑戰(zhàn)，包括個體隸屬度編碼問題、社區(qū)個數(shù)最優(yōu)設置問題、模糊模塊度函數(shù)設計問題、模糊隸屬度閾值設置問題、模糊重疊社區(qū)劃分評價問題、以及EAs全局最優(yōu)化性能問題等。

4.2.1 個體隸屬度編碼問題

EAs中種群個體對應候選可行社區(qū)劃分，編碼操作將個體每一維代表的節(jié)點與社區(qū)分布聯(lián)系起來，是應用EAs實現(xiàn)模糊重疊社區(qū)檢測的重要環(huán)節(jié)?，F(xiàn)有離散重疊及非重疊社區(qū)檢測中普遍使用的個體編碼方式主要包括兩種：字符串編碼[68]和基于基因位的局部鄰接編碼(Locus-Based Adjacency Representation, LAR)[69]，二者解碼后形成的社區(qū)劃分均為硬劃分，從社區(qū)劃分本身無法體現(xiàn)出社區(qū)重疊情況，更無法體現(xiàn)節(jié)點對不同社區(qū)的隸屬程度。為實現(xiàn)模糊重疊社區(qū)檢測，現(xiàn)有檢測算法中主要采取了兩種不同的解決方式：

1)對字符串編碼及LAR編碼所得社區(qū)硬劃分進行轉化，使其能夠體現(xiàn)出重疊社區(qū)及重疊節(jié)點對不同社區(qū)的隸屬程度[57]。通常采用的處理方法為：針對個體編碼所得社區(qū)硬劃分，首先根據(jù)節(jié)點的連接數(shù)目或鄰居節(jié)點數(shù)目，計算每個節(jié)點對自身所在社區(qū)及鄰域社區(qū)的隸屬度，然后通過設置隸屬度閾值確定每個節(jié)點的社區(qū)歸屬數(shù)目及社區(qū)分布，從而得到個體對應的模糊重疊社區(qū)劃分。然而，該種編碼轉化方式存在計算復雜、效率較低且穩(wěn)定性較差等缺陷，主要原因包括：(1)隸屬度計算存在多種方式，不同的計算標準和計算方式下同一節(jié)點對不同社區(qū)的隸屬度分布可能存在較大差異，使得重疊節(jié)點的判定存在較大不確定性，同一硬劃分可能轉化為不同的模糊重疊社區(qū)劃分，個體編碼的質量和穩(wěn)定性難以保證；(2)隸屬度閾值的最優(yōu)設置沒有統(tǒng)一有效的解決方法，且通常設置方法較為復雜。

2)在個體編碼時直接對節(jié)點的隸屬度分布進行數(shù)值化編碼，即將公式(1)中的隸屬度分布矩陣U={uik}作為個體[10]。根據(jù)算法需要也可將個體隸屬度編碼的矩陣形式轉化為向量形式，如式(10)所示。

U=[u11…un1,u12…un2,…u1k…unk…,u1c…unc]

(10)

該種基于隸屬度分布的編碼方式相比較于字符串編碼和LAR編碼的性能優(yōu)勢包括：1)能夠清晰直觀地體現(xiàn)所有節(jié)點對各社區(qū)的隸屬度分布，個體本身即為一個真正的模糊重疊社區(qū)劃分；2)通過種群在隸屬度分布組合對應可行空間中的搜索實現(xiàn)模糊重疊社區(qū)檢測，種群收斂至全局最優(yōu)解對應個體即為最優(yōu)模糊重疊社區(qū)劃分，由此避免了隸屬度計算，以及模糊劃分與離散劃分及硬劃分之間的轉化問題。然而，該種編碼方式也存在較為明顯的缺陷：1)個體編碼的維度較高，單個個體二維矩陣編碼使得種群需要三維矩陣表示，導致進化操作中的計算復雜度增加。2)要求社區(qū)數(shù)目參數(shù)c不小于真實社區(qū)數(shù)目，因此通常需要真實社區(qū)數(shù)目的相關先驗信息，在許多實際網(wǎng)絡環(huán)境下難以實現(xiàn)。此外，若參數(shù)c遠大于真實社區(qū)數(shù)目會導致較高的時間和空間計算成本。

由上述分析可知，模糊重疊社區(qū)檢測中由于需要利用并體現(xiàn)節(jié)點對社區(qū)的隸屬度分布，因此增加了EAs中個體編碼的復雜度。如何選擇和設計個體編碼方式，使其在編碼功能和編碼效率之間達到良好平衡，將是算法研究中需要解決的首個關鍵問題。

4.2.2 社區(qū)個數(shù)最優(yōu)設置問題

社區(qū)個數(shù)直接關系到檢測所得社區(qū)劃分的合理性和準確性，是檢測算法中最重要的參數(shù)。社區(qū)個數(shù)的最優(yōu)化設置是模糊重疊社區(qū)檢測中需要考慮和解決的重要問題。

現(xiàn)有模糊重疊社區(qū)檢測方法中，最優(yōu)社區(qū)數(shù)目的確定主要采用以下幾種方法：1)根據(jù)先驗知識預知真實社區(qū)個數(shù)。該種方法最為簡單，但實際網(wǎng)絡環(huán)境下通常無法獲得準確的社區(qū)個數(shù)信息。2)在LAR編碼方式下，解碼過程中能夠根據(jù)節(jié)點社區(qū)編號和鄰域節(jié)點連接情況確定個體對應社區(qū)劃分，并在此過程中自動獲得社區(qū)個數(shù)，檢測結果將根據(jù)評價指標確定最優(yōu)個體及對應社區(qū)個數(shù)。該種方法無需社區(qū)個數(shù)的先驗信息或人為干預，但無法體現(xiàn)隸屬度信息。3)社區(qū)數(shù)目遞增的優(yōu)化方法[43,51,54]。社區(qū)數(shù)目從2開始以1為步長逐步遞增，計算每個社區(qū)數(shù)目下最優(yōu)社區(qū)劃分對應的模糊模塊度函數(shù)值直至模塊度函數(shù)不再增加，確定最高模塊度數(shù)值對應社區(qū)數(shù)目為最優(yōu)社區(qū)數(shù)目[51,54]。該種方法能夠在一定程度上提升最優(yōu)社區(qū)個數(shù)設置的準確性，但模糊模塊度函數(shù)優(yōu)化受到包含社區(qū)數(shù)目在內多種因素的影響，因此容易獲得局部最優(yōu)的社區(qū)數(shù)目。4)在以MSFCM和FMM/H為代表的模糊重疊社區(qū)檢測算法中，通過遍歷方法獲得最優(yōu)社區(qū)個數(shù)。首先根據(jù)先驗知識預知社區(qū)個數(shù)的取值范圍，然后在所有可能社區(qū)個數(shù)取值下進行模糊重疊社區(qū)檢測，獲得多個局部最優(yōu)社區(qū)劃分，最后根據(jù)評價指標確定全局最優(yōu)社區(qū)劃分，并確定最優(yōu)社區(qū)個數(shù)。該種方法既能夠獲得相對精確的全局最優(yōu)社區(qū)個數(shù)，但相應的計算復雜度也較高。因此，如何精確且高效地獲得模糊重疊社區(qū)劃分的最優(yōu)社區(qū)個數(shù)也是一項有待解決的關鍵問題。

4.2.3 模糊模塊度函數(shù)設計問題

模糊模塊度函數(shù)的設計與選擇是模糊模塊度優(yōu)化方法中的核心關鍵問題，模糊模塊度函數(shù)不僅在EAs優(yōu)化過程中起到最優(yōu)社區(qū)劃分搜索的方向性引導作用，而且是社區(qū)劃分質量的評判標準，因此對于模糊重疊社區(qū)檢測性能具有決定性影響。

4.2.4 模糊隸屬度閾值設置問題

模糊重疊社區(qū)檢測過程中節(jié)點對社區(qū)的隸屬度分布通常僅僅是一系列人工權重系數(shù)，沒有清晰明確的物理含義[29]，通常需要人為指定界限值即隸屬度閾值，確定每個節(jié)點最終的社區(qū)歸屬。隸屬度閾值的設置對社區(qū)劃分質量具有重要影響，若取值過高則容易丟失重疊節(jié)點，導致社區(qū)結構重疊程度偏低；若取值較低則產生過多重疊節(jié)點，導致社區(qū)結構重疊程度偏高，容易產生過度重疊或重復社區(qū)，因此最優(yōu)隸屬度閾值的設定成為影響模糊重疊社區(qū)劃分質量的關鍵性因素。然而，現(xiàn)有研究中沒有通用且高效的最優(yōu)隸屬度閾值設定方法，通常在大量統(tǒng)計實驗過程中依據(jù)人工經驗設定[2]。由于不同網(wǎng)絡對應的最優(yōu)隸屬度閾值通常存在差異，該種方法容易引入誤差且缺乏理論依據(jù)，使最優(yōu)模糊重疊社區(qū)劃分的質量和穩(wěn)定性受到影響。因此，如何提高最優(yōu)隸屬度閾值設置的科學性和穩(wěn)定性，或通過構建性能更優(yōu)的模糊模塊度函數(shù)避免隸屬度閾值設置，將是模糊重疊社區(qū)檢測中的重要挑戰(zhàn)。

4.2.5 模糊重疊社區(qū)劃分評價問題

模糊重疊社區(qū)劃分的評價指標既可用于評估社區(qū)劃分質量，也可作為EAs的優(yōu)化目標函數(shù)，因此對于模糊重疊社區(qū)檢測結果具有重要影響。由于重疊社區(qū)劃分的特殊性和復雜性，非重疊社區(qū)劃分的評價指標并不適用于重疊社區(qū)檢測，離散重疊社區(qū)劃分的評價指標也不適用于模糊重疊社區(qū)檢測。

目前針對模糊重疊社區(qū)劃分質量評價的研究尚未完善，現(xiàn)階段存在的問題包括：1)由于目前僅有極少數(shù)重疊社區(qū)檢測方法能夠獲得真正的模糊重疊社區(qū)劃分結果，因此能夠用于評價模糊重疊社區(qū)劃分質量的評價標準及評價函數(shù)較為缺乏，已知的評價標準僅有Fuzzy Rand Index[6]和Normalized Fuzzy Mutual Information (NFMI)[53]，能夠測量兩個模糊重疊社區(qū)劃分的相似性。然而，F(xiàn)uzzy Rand Index和NFMI僅適用于已知真實模糊重疊社區(qū)結構的網(wǎng)絡，對于未知真實社區(qū)結構的真實網(wǎng)絡，大部分現(xiàn)有算法仍采用非重疊社區(qū)劃分評價指標Q對轉化后的非重疊社區(qū)劃分進行近似質量評估[39]，在一定程度上限制了模糊重疊社區(qū)劃分評估的精確性。2)絕大部分現(xiàn)有基于EAs的模糊重疊社區(qū)檢測中均將模糊模塊度函數(shù)作為唯一的目標函數(shù)進行最優(yōu)化，對于檢測結果應用標準模塊度函數(shù)進行質量評估，即對于最優(yōu)社區(qū)劃分的搜索和評價僅考慮了模塊性指標。然而，實驗研究表明，社區(qū)劃分的模塊性和與真實社區(qū)結構的一致性之間存在一定的沖突，即模塊性最優(yōu)的社區(qū)劃分不一定最符合真實社區(qū)結構。3)現(xiàn)有檢測方法中缺乏完整的質量評價標準，對于模糊重疊社區(qū)檢測，除了測量模糊重疊社區(qū)劃分的模塊性和與真實社區(qū)結構的一致性外，社區(qū)劃分的重疊性也應得到有效評估，包括檢測所得重疊節(jié)點的完整性和精確性等，因此評價標準中應增加Recall和Precision等評價指標?；谏鲜龇治隹芍?，構建或選擇高性能的模糊重疊社區(qū)劃分評價指標，并盡可能保證對于社區(qū)劃分質量評價的完整性，從而提升對檢測算法性能的評價質量，是模糊重疊社區(qū)檢測中有待完善的重要內容。

4.2.6 EAs全局最優(yōu)化性能問題

基于EAs的模糊模塊度優(yōu)化完全依靠進化種群個體在可行搜索空間中的探索性和開采性并行搜索，獲得全局最優(yōu)的模糊重疊社區(qū)劃分。隨著網(wǎng)絡規(guī)模、復雜度、模糊程度及重疊程度的增加，最優(yōu)化社區(qū)劃分搜索對應的決策空間和目標空度維度大幅增加，極端退化現(xiàn)象逐漸嚴重，全局最優(yōu)解搜索難度逐漸加大，容易導致EAs陷入局部最優(yōu)甚至求解失敗，因此EAs的全局最優(yōu)化能力對于模糊重疊社區(qū)檢測質量具有重要影響。

現(xiàn)有基于EAs的模糊重疊社區(qū)檢測中采用的EA主要為遺傳算法GA，作為傳統(tǒng)且典型的一類進化優(yōu)化算法，GA雖然較為通用，但其在大規(guī)模復雜最優(yōu)化問題上面臨收斂性能急劇下降的問題，現(xiàn)有算法中通常需要加入局部搜索操作，如爬山法、模擬退火等，以提升算法成功收斂到全局最優(yōu)解的概率。近年來，智能優(yōu)化領域中涌現(xiàn)出多種基于群智能的高性能EAs，包括差分進化算法(Differential Evolution, DE)[72]、人工蜂群算法(Artificial Bee Colony Algorithm, ABC)[73]、引力搜索算法(Gravitational Search Algorithm, GSA)[74]、社會蜘蛛優(yōu)化算法(Social Spider Optimization, SSO)[75]等。實驗研究已證實上述算法在收斂精度、收斂速度及穩(wěn)定性方面相比較于GA具有明顯優(yōu)勢，因此可嘗試將其應用于模糊模塊度優(yōu)化問題的求解，以提升全局最優(yōu)模糊重疊社區(qū)劃分質量。此外，模糊模塊度最優(yōu)化問題具有一定的特殊性，即種群個體的各維分量之間由于受網(wǎng)絡拓撲關系制約而緊密相聯(lián)。EAs優(yōu)化過程中一方面需要對交叉、變異等核心進化操作進行轉化，將個體各維分量與社區(qū)信息關聯(lián)起來，在保證合法性的基礎上，使個體在進化過程中盡可能保留優(yōu)質分量中攜帶的社區(qū)劃分信息；另一方面，需要在EAs中添加Clean-up等操作對進化操作中產生的錯誤劃分的節(jié)點進行修正，以提升相鄰節(jié)點劃分至同一社區(qū)的概率，在提升社區(qū)劃分精確度的同時加快算法搜索速度。

基于上述分析可知，如何根據(jù)實際網(wǎng)絡檢測需求選擇高收斂性能的EAs，在編碼、進化操作核心操作中有效利用網(wǎng)絡拓撲及社區(qū)信息，利用其在大規(guī)模復雜最優(yōu)化問題中的強大的全局收斂能力，提升模糊模塊度優(yōu)化質量，是基于EAs的模塊度優(yōu)化模糊重疊社區(qū)檢測研究中要解決的重要問題。

5 研究趨勢分析

模糊重疊社區(qū)檢測通過擴展隸屬度取值空間，大幅細化了對于節(jié)點與社區(qū)之間隸屬關系的刻畫，能夠在社區(qū)劃分中體現(xiàn)所有節(jié)點對所有社區(qū)完整且相對的隸屬度信息，不僅能夠更加精確、細致地反映出較為復雜且模糊的真實重疊社區(qū)結構，而且能夠挖掘出重疊社區(qū)結構中隱含的深層次拓撲信息。模糊重疊社區(qū)檢測強大的功能特性，使其對于精確挖掘復雜網(wǎng)絡的重疊社區(qū)結構、掌握網(wǎng)絡中隱含的深層次拓撲結構特征、分析社區(qū)結構的功能特性及動力學特性、預測網(wǎng)絡行為及演化態(tài)勢等具有重要意義。

真實環(huán)境中復雜網(wǎng)絡的規(guī)模日益龐大、拓撲結構日趨復雜，模糊程度及重疊程度不斷增強，用戶對于社區(qū)檢測的需求逐漸多樣化和復雜化。為提升真實網(wǎng)絡重疊社區(qū)檢測精度、盡可能深度挖掘出社區(qū)結構信息并最大化滿足用戶需求，模糊重疊社區(qū)檢測技術的應用需求日益凸顯，同時對現(xiàn)有模糊重疊社區(qū)檢測方法的性能提出了嚴峻挑戰(zhàn)。綜合分析模糊重疊社區(qū)檢測現(xiàn)階段已取得的研究成果及目前面臨的技術難題，分析未來研究方向及發(fā)展趨勢主要包含以下4個方面。

5.1 模糊模塊度優(yōu)化的擴展

從國內外相關研究可以看出，基于模糊模塊度優(yōu)化的檢測方法由于能夠獲得真正的模糊重疊社區(qū)劃分，且在易操作性、穩(wěn)定性等方面具備一定優(yōu)勢，成為目前模糊重疊社區(qū)檢測的主要方法。然而，模糊模塊度函數(shù)僅能夠評價社區(qū)劃分的模塊性性能，無法有效測量社區(qū)劃分與真實社區(qū)結構之間的相似性，以及重疊社區(qū)劃分的重疊性。隨著真實網(wǎng)絡環(huán)境下用戶多樣性檢測需求的不斷提升，最優(yōu)社區(qū)劃分同時滿足多項檢測性能需求的趨勢愈加明顯，如同時保證較高的模塊性和精確性等。

當模糊重疊社區(qū)劃分的性能指標涵蓋模塊性、精確性、重疊性等多項評價標準時，待優(yōu)化的目標函數(shù)數(shù)目將超過2項，單目標模糊模塊度優(yōu)化問題將演變?yōu)槎嗄繕藘?yōu)化問題(Multi-objective Optimization Problems, MOPs)甚至是高維多目標優(yōu)化問題(High-dimensional Multi-objective Optimization Problems, LMOPs)(目標函數(shù)數(shù)目大于4)。MOPs中由于需要同時使多項目標函數(shù)達到相對最優(yōu)，需要平衡多項目標函數(shù)之間的沖突關系，而LMOPs中高維的特性進一步加劇了MOPs的目標空間復雜度和最優(yōu)解搜索難度，是目前智能優(yōu)化領域中最難求解的優(yōu)化問題之一，需要設計高性能的多目標進化算法(Multi-Objective Evolutionary algorithms, MOEAs)才能有效求解[76]。因此，如何設計收斂精度高、分布性好、速度快且穩(wěn)定性強的MOEAs，對包含模糊模塊度函數(shù)在內的高質量函數(shù)集合進行最優(yōu)化，以獲得多尺度、多樣化的Pareto最優(yōu)社區(qū)劃分方案集合，充分利用目標函數(shù)之間的差異性和多樣性提升模糊重疊社區(qū)劃分的精確性、功能性和用戶滿意度，是模糊重疊社區(qū)檢測未來發(fā)展的必然趨勢和重點研究內容。

5.2 大規(guī)模網(wǎng)絡數(shù)據(jù)處理中精度與效率的平衡

網(wǎng)絡社區(qū)結構的模糊重疊現(xiàn)象及高精度的模糊重疊社區(qū)檢測需求廣泛存在于在線社交網(wǎng)絡等大規(guī)模復雜網(wǎng)絡環(huán)境中。一方面，大規(guī)模網(wǎng)絡社區(qū)檢測由于節(jié)點及連接數(shù)目較大，導致檢測算法的時間和空間計算復雜度相對較高；另一方面，模糊重疊社區(qū)檢測由于定量測定節(jié)點隸屬度，且在檢測結果中體現(xiàn)完整隸屬度分布，進一步加劇了計算成本。目前現(xiàn)有模糊重疊社區(qū)檢測方法難以在可行時間內有效處理十萬節(jié)點以上大規(guī)模網(wǎng)絡的社區(qū)檢測問題。因此，如何通過有效利用大規(guī)模網(wǎng)絡數(shù)據(jù)的稀疏性減少模糊模塊度計算時間成本、EAs多種群分布式計算、全局搜索與局部搜索融合等方式，在保證模糊重疊社區(qū)檢測質量的同時提升運算效率將是當前及未來模糊重疊社區(qū)檢測研究中要解決的關鍵問題。

5.3 網(wǎng)絡屬性信息的利用與社區(qū)屬性的體現(xiàn)

現(xiàn)有模糊重疊社區(qū)檢測都是基于網(wǎng)絡拓撲結構信息進行社區(qū)劃分，大多未考慮網(wǎng)絡中大量存在的屬性信息，包括節(jié)點自身特征屬性和鏈接特征屬性等。一方面，真實社交網(wǎng)絡中社區(qū)結構的形成除了顯性的拓撲結構因素外，隱性的屬性因素也具有重要影響，尤其重疊社區(qū)結構的產生可能更多依賴于節(jié)點和鏈接的屬性相似性。此外，真實網(wǎng)絡環(huán)境中可能已知部分節(jié)點的社區(qū)歸屬及隸屬度信息，若對其加以有效利用能夠有助于提升檢測精度及效率。因此，模糊重疊社區(qū)檢測過程中應盡可能加強對屬性信息的利用，通過模糊隸屬度量化并區(qū)分節(jié)點與社區(qū)之間屬性相似性，從而提升對網(wǎng)絡中重疊社區(qū)的檢測能力。另一方面，對于模糊重疊社區(qū)檢測所得的節(jié)點隸屬度分布，除了希望其能夠更加精確地反映出節(jié)點與社區(qū)之間的拓撲隸屬度，也希望其能夠體現(xiàn)節(jié)點與社區(qū)之間的屬性相似度，從而進一步挖掘出重疊社區(qū)結構的屬性信息，如重疊節(jié)點的屬性多樣性、社區(qū)屬性相似性及差異性等，從而更好地進行網(wǎng)絡功能特性、動力學特性、演化特性等分析。因此，模糊重疊社區(qū)檢測中網(wǎng)絡屬性信息有效利用，以及模糊重疊社區(qū)劃分中屬性信息的體現(xiàn)，都將是今后研究中有待解決的重要問題。

5.4 模糊重疊社區(qū)結構的動態(tài)演化更新

在社會網(wǎng)絡等基于用戶關聯(lián)性所生成網(wǎng)絡中，節(jié)點之間除了拓撲結構關系及屬性相似性關系外，還存在頻繁的信息交互，信息流動使得網(wǎng)絡具有較強的動態(tài)特性[77]。由于網(wǎng)絡動態(tài)演化過程中，各個時間片上節(jié)點的復合屬性可能為臨時或過時狀態(tài)[78]，因此節(jié)點的社區(qū)歸屬、節(jié)點的重疊性及重疊程度、社區(qū)的重疊程度等都可能發(fā)生變化。如何有效利用網(wǎng)絡歷史數(shù)據(jù)及新增數(shù)據(jù)，獲得每個時間片上的模糊重疊社區(qū)劃分，提升單個時間片上的重疊社區(qū)檢測質量，并根據(jù)不同時間片上的網(wǎng)絡快照分析重疊社區(qū)結構的動態(tài)演化過程，并對未來的演化趨勢進行預測，是模糊重疊社區(qū)檢測及動態(tài)網(wǎng)絡社區(qū)檢測未來的重要研究方向。

6 結語

模糊重疊現(xiàn)象廣泛存在于社交網(wǎng)絡等基于個體關聯(lián)性構成的真實網(wǎng)絡環(huán)境中，使網(wǎng)絡中社區(qū)結構的拓撲關系呈現(xiàn)出較強的復雜性和模糊性。對大規(guī)模社交網(wǎng)絡等真實復雜網(wǎng)絡進行模糊重疊社區(qū)檢測，能夠更加深入、全面、細致地體現(xiàn)出節(jié)點與社區(qū)之間的隸屬關系，從而更加精準地反映出復雜且模糊的真實社區(qū)結構，同時揭示出重疊社區(qū)結構中隱含的深層次拓撲信息，大幅提升對真實網(wǎng)絡重疊社區(qū)拓撲結構的檢測能力以及對拓撲關系的挖掘能力。對于發(fā)現(xiàn)社區(qū)結構顯性及隱性的拓撲結構特征、屬性特征、分析網(wǎng)絡功能特性及動力學特性、掌握并預測網(wǎng)絡演化規(guī)律等具有重要意義。

[1]Su J H, Havens T C. Quadratic program-based modularity maximization for fuzzy community detection in social networks [J]. IEEE Transactions on Fuzzy Systems, 2015, 23(5):1356-1371.

[2]Su J H, Havens T C. Community detection in social networks using a genetic algorithm [C]. Proc of IEEE International Conference on Fuzzy Systems (FUZZ-IEEE). Beijing, China, 2014: 2039-2046.

[3]Havens T C, Bezdek J C, Leckie C. A soft modularity function for detecting fuzzy communities in social networks [J]. IEEE Transactions on Fuzzy Systems, 2013, 21(6):1170-1175.

[4]Xie J R, Kelley S, Szymanski B K. Overlapping community detection in networks: the state of the art and comparative study [J]. ACM Computing Surveys, 2013, 45(4):1-37.

[5]Golsefid S M M, Zarand M H F, Bastani S S. Fuzzy community detection model in social networks [J]. International Journal of Intelligent Systems, 2015, 30:1227-1244.

[6]Gregory S. Fuzzy overlapping communities in networks [J]. Journal of Statistical Mechanics-Theory and Experiment, 2011, 2: P02017.

[7]Kundu S, Pal S K. Fuzzy-rough community in social networks [J]. Pattern Recognition Letters, 2015, 67,145-152.

[8]Bennett L, Kittas A, Liu S S. Community structure detection for overlapping modules through mathematical programming in protein interaction networks [J]. Plos One, 2014, 9(11):e112821-e112821.

[9]劉世超,朱福喜,甘琳. 基于標簽傳播概率的重疊社區(qū)發(fā)現(xiàn)算法[J].計算機學報, 2015, 38(47):1-17.

Liu Shichao, Zhu Fuxi, Gan Lin. A label-propagation-Probability-based algorithm for overlapping community detection [J]. Chinese Journal of Computers, 2015, 38(47):1-17.

[10] Nicosia V, Mangioni G, Malgeri M. Extending the definition of modularity to directed graphs with overlapping communities [J]. Journal of Statistical Mechanics-Theory and Experiment, 2009(3):3166-3168.

[11] Psorakis I, Roberts S, Ebden M, et al. Overlapping community detection using Bayesian non-negative matrix factorization [J]. Physical Review E, 2011, 83(6 Pt 2):1509-1520.

[12] Zhao K, Zhang S W, Pan Q. Fuzzy analysis for overlapping community structure of complex network [C]. Proc CCDC, 2010: 3976-3981.

[13] Palla G, Derényi I, Farkas I. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature, 2005, 435(7043): 814-818.

[14] Farkas I, Abel D, Palla G, et al. Weighted network modules [J]. New J Phys, 2007, 9(6):180-198.

[15] Palla G, Dernyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society [J]. Nature, 2005, 435: 814-818.

[16] Kumpula J M, Kivela M, Kaski K, et al. Sequential algorithm for fast clique percolation [J]. Phys Rev E 2008, 78(2):1815-1824.

[17] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multiscale complexity in networks [J]. Nature, 2010, 466(7307): 761-764.

[18] Kim Y, Jeong H. Map equation for link communities [J]. Physical Review E, 2011, 84(2):1402-1409.

[19] 朱牧,孟凡榮,周勇. 基于鏈接密度聚類的重疊社區(qū)發(fā)現(xiàn)算法[J]. 計算機研究與發(fā)展,2013,50(12):2520-2530.

Zhu Mu, Meng Fanrong, Zhou Yang. Density-based link clustering algorithm for overlapping community detection [J]. Journal of Computer Research and Development, 2013,50(12):2520-2530.

[20] Wu Z, Lin Y. Wan H, et al. A fast and reasonable method for community detection with adjustable extent of overlapping [C]. Proc of International Conference on Intelligent Systems & Knowledge Engineering. 2010:376-379.

[21] Fortunato S. Community detection in graphs [J]. Phys Rep, 2010, 486(3-5):75-174.

[22] Lancichinetti A, Fortunato S, Kertesz J. Detecting the overlapping and hierarchical community structure of complex networks [J]. New Journal of Physics, 2008, 11(3):19-44.

[23] Lee C, Reid F, McDaid A. Detecting highly overlapping community structure by greedy clique expansion [C]. Proceedings of the 4th International Workshop on Social Network Mining and Analysis. ACM, Washington DC, USA, 2010, 33-42.

[24] Coscia M, Rossetti G, Giannotti F, et al. DEMON: a local first discovery method for overlapping communities [C]. proc of the 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Ming. New York: ACM, 2012:615-623.

[25] Lancichinetti A, Radicchi F, Ramasco J J, et al. Finding statistically significant communities in networks [J]. Plos One, 2010, 6(4):336-338.

[26] Jin D, Yang B, Baquero C, et al. A markov random walk under constraint for discovering overlapping communities in complex networks [J]. Journal of Statistical Mechanics: Theory and Experiment, 2011,2011(5):50.

[27] 陳俊宇,周剛,南煜,等.一種半監(jiān)督的局部擴展式重疊社區(qū)發(fā)現(xiàn)方法[J].計算機研究與發(fā)展,2016,53(6): 1376-1388.

Chen Junyu, Zhou Gang, Nan Yu, et al. Semi-supervised local expansion method for overlapping community detection [J]. Journal of Computer Research and Development, 2016,53(6): 1376-1388.

[28] Blondel V D, Guillaume J L, Lambiotte R. Fast unfolding of communities in large networks [J]. Journal of Statistical Mechanics Theory & Experiment, 2015, 30(2):155-168.

[29] Shen H W, Cheng X Q, Guo J F. Quantifying and identifying the overlapping community structure in networks [J]. Journal of Statistical Mechanics Theory & Experiment, 2009, 2009(7):07042.

[30] Wang X, Li L, Cheng Y. An overlapping module identification method in protein-protein interaction networks [J]. BMC Bioinformatics, 2012, 13 (Suppl):343-347.

[31] Franca F O D, Coelho G P. Identifying overlapping communities in complex networks with multimodal optimization [J]. IEEE Congress on Evolutionary Computation, Cancún, México, 2013: 269-276.

[32] 張英杰,龔中漢, 陳乾坤. 基于免疫離散差分進化算法的復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)[J].自動化學報, 2015,41(4):749-757.

Zhang Yingjie, Gong Zhonghan, Chen Qiankun. Community detection in complex networks using immune differential evolution algorithm [J]. Acta Automatica Sinica, 2015, 41(4):749-757.

[33] 金弟, 劉杰, 楊博, 等. 局部搜索與遺傳算法結合的大規(guī)模復雜網(wǎng)絡社區(qū)探測[J]. 自動化學報, 2011, 37(7): 873-882.

Jin Di, Liu Jie, Yang Bo, et al. Genetic algorithm with local search for community detection in large-scale complex networks [J]. Acta Automatica Sinica, 2011, 37(7): 873-882.

[34] 金弟, 楊博, 劉杰, 等. 復雜網(wǎng)絡簇結構探測——基于隨機游走的蟻群算法[J]. 軟件學報, 2012, 23(3): 451-464.

Jin Di, Yang Bo, Liu Jie, et al. An colony optimization based on random walk for community detection in complex networks [J]. Journal of Software, 2012, 23(3): 451-464.

[35] Zhou X, Liu Y H, Zhang J D. An ant colony based algorithm for overlapping community detection in complex networks [J]. Physica A, 2015,427:289-301.

[36] 黃發(fā)良,肖南峰. 基于線圖與 PSO 的網(wǎng)絡重疊社區(qū)發(fā)現(xiàn)[J]. 自動化學報, 2011,37(9):1140-1144.

Huang Faliang, Xiao Nanfeng. Discovering overlapping communities based on line graph and PSO [J]. Acta Automatica Sinica, 2011,37(9):1140-1144.

[37] Pizzuti C. A multi-objective genetic algorithm for community detection in networks [C]. Proceedings of the 21st IEEE International Conference on Tools with Artificial Intelligence, 2009, 379-386.

[38] 劉辰龍.基于進化算法的社區(qū)檢測及其在個性化推薦的應用[D].西安：西安電子科技大學,2014.

Liu Chenlong. Evolutionary community detection algorithms and their applications in personalized recommendation [D]. Xi'an: Xidian University, 2014.

[39] Wu Z H, Lin Y F, Gregory S, et al. Balanced multi-label propagation for overlapping community detection in social networks [J]. Journal of Computer Science and Technology, 2012, 27(3):468-479.

[40] Qiang H, Yan G. A method of personalized recommendation based on multi-label propagation for overlapping community detection [J]. System science, engineering design and manufacturing informatization (ICSEM), 2012 3rd International Conference on IEEE, 2012, 1: 360-364.

[41] Gregory S. Finding overlapping communities in networks by label propagation [J]. New Journal of Physics, 2009, 12(10):2011-2024.

[42] Xie J, Szymanski B K. Towards linear time overlapping community detection in social networks [C]. Proc PAKDD Conf, 2012, 25-36.

[43] Zhao K, Zhang SW, Pan Q. Fuzzy analysis for overlapping community structure of complex network [C]. Proc CCDC, 2010, 3976-3981.

[44] Psorakis I, Roberts S, Ebden M, et al. Overlapping community detection using Bayesian non-negative matrix factorization [J]. Physical Review E, 2011, 83(6 Pt 2):1509-1520.

[45] 李玉翔, 李弼程, 郭志剛. 基于非負矩陣分解的網(wǎng)絡重疊社區(qū)發(fā)現(xiàn)研究[J]. 系統(tǒng)仿真學報,2014,26(3):643-649.

Li Yuxiang, Li Bicheng, Guo Zhigang. Research on overlapping community detection in networks using non-negative matrix factorization [J]. Journal of System Simulation, 2014, 26(3):643-649.

[46] Zhang S H, Wang R S, Zhang X S. Uncovering fuzzy community structure in complex networks [J]. Physical Review E (S1550-2376), 2007, 76(4): 046103.1-046103.7.

[47] 劉勇.復雜網(wǎng)絡的非重疊與重疊社區(qū)檢測方法[D].西安:西安電子科技大學,2014.

Liu Yong. Method for non-overlapping and overlapping communities detection in complex networks [D]. Xi'an: Xidian University， 2014.

[48] 陳俊宇,周 剛,熊小兵. 一種采用鄰居投票機制的重疊社區(qū)發(fā)現(xiàn)方法[J]. 小型微型計算機系統(tǒng), 2014, 35(10):2272-2277.

Chen Junyu, Zhou Gang, Xiong Xiaobing. Detection overlapping community structure with neighbor voting [J]. Journal of Chinese Computer Systems, 2014, 35(10): 2272-2277.

[49] Bennett L, Kittas A, Liu S S. Community structure detection for overlapping modules through mathematical programming in protein interaction networks [J]. Plos One, 2014, 9(11):e112821-e112821.

[50] Liu J. Detecting the fuzzy clusters of complex networks [J]. Pattern Recognit, 2010, 43:1334-1345.

[51] Wang W J, Liu D, Liu X, et al. Fuzzy overlapping community detection based on local random walk and multidimensional scaling [J]. Phys A, 2013, 392(24): 6578-6586.

[52] 李劉強,桂小林,安健,等. 采用模糊層次聚類的社會網(wǎng)絡重疊社區(qū)檢測算法[J].西安交通大學學報, 2015,49(2):7-13.

Li Liuqiang, Gui Xiaolin, An Jian, et al. Overlapping community detection algorithm based on fuzzy hierarchical clustering in social network [J]. Journal of Xi'an Jiaotong University, 2015,49(2):7-13.

[53] Suman K D, Sankar K P. Fuzzy-rough community in social networks [J]. Pattern Recognition Letters, 2015, 67,145-152.

[54] Nepusz T, Petroczi A, Negyessy L, et al. Fuzzy communities and the concept of bridgeness in complex networks [J]. Phys Rev E, 2008, 77(1):119-136.

[55] Zhang S, Wang R, Zhang X. Identification of overlapping community structure in complex networks using fuzzy c-means clustering [J]. Physica A Statistical Mechanics & Its Applications, 2007, 374(1):483-490.

[56] Liu J. Fuzzy modularity and fuzzy community structure in networks [J]. Physics of Condensed Matter, 2010, 77(4): 547-557.

[57] Zhan W H, Guan J H, Chen H H, et al. Identifying overlapping communities in networks using evolutionary method [J]. Physica A, 2016,442:182-192.

[58] 劉瑤,康曉慧,高紅,等. 基于節(jié)點親密度和度的社會網(wǎng)絡社團發(fā)現(xiàn)方法[J]. 計算機研究與發(fā)展,2015,52(10):2363-2372.

Liu Yao, Kang Xiaohui, Gao Hong, et al. A community detection method based on the node intimacy and degree in social network [J]. Journal of Computer Research and Development, 2015, 52(10): 2363-2372.

[59] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks [J]. Journal of Statistical Mechanics: Theory and Experiment, 2008: P10008.

[60] 冷作福. 基于貪婪優(yōu)化技術的網(wǎng)絡社區(qū)發(fā)現(xiàn)算法研究[J]. 電子學報, 2014,42(4):723-729.

Leng Zuofu. Community detection in complex networks based on greedy optimization [J]. Acta Electronica Sinica, 2014, 42(4): 723-729.

[61] Guimera R, Amaral L.Functional cartography of complex metabolic networks [J]. Nature, 2005, 433: 895-900.

[62] Medus A, Acuna G, Dorso C. Detection of community structures in networks via global optimization [J]. Physica A: Statistical Mechanics and Its Applications, 2005, 358: 593-604.

[63] Ruan J, Zhang W. Identifying network communities with a high resolution [J]. Physical Review E, 2008, 77: 1-12.

[64] 陳國強, 王宇平.基于極值優(yōu)化模塊密度的復雜網(wǎng)絡社區(qū)檢測[J]. 華中科技大學學報(自然科學版),2011,39(4):82-85.

Chen Guoqiang, Wang Yuping. Community detection in complex networks using extremal optimization modularity density [J]. Journal of Huazhong University of Science and Technology(Natural Science Edition), 2011, 39(4): 82-85.

[65] Aloise D, Cafieri S, Caporossi G, et al. Column generation algorithms for exact modularity maximization in networks [J]. Physical Review E, 2010, 82: 046112.

[66] Bennett L, Liu S, Papageorgiou L G, et al. Detection of disjoint and overlapping modules in weighted complex networks [J]. Advances in Complex Systems, 2012, 15: 11500.

[67] 黃發(fā)良, 張師超, 朱曉峰. 基于多目標優(yōu)化的網(wǎng)絡社區(qū)發(fā)現(xiàn)方法[J]. 軟件學報, 2013, 24(9):2062-2077.

Huang Faliang, Zhang Shichao, Zhu Xiaofeng. Discovering network community based on multi-objective optimization [J]. Journal of Software, 2013, 24(9): 2062-2077.

[68] Tasgin M, Bingol A. Communities detection in complex networks using genetic algorithms [C]. Proc Eur Conf Complex Syst， 2006, 1-6.

[69] Pizzuti C. Community detection in social networks with genetic algorithms [C]. Proc 10th Annu Conf Genetic Evol comput, 2008, 1137-1138.

[70] Shen H, Cheng X, Cai K, et al. Detect overlapping and hierarchical community structure in networks [J]. Physical A: Statistical Mechanics and its Applications, 2009,388:1706-1712.

[71] 周東青,王星,程嗣怡,等. 離散粒子群社區(qū)檢測算法[J]. 系統(tǒng)工程與電子技術, 2016,38(2):428-433.

Zhou Dongqing, Wang Xing, Cheng Siyi, et al. Community detection algorithm via discrete PSO [J]. Systems Engineering and Electronics, 2016, 38(2): 428-433.

[72] Bi X J, Xiao J. Classification-based self-adaptive differential evolution with fast and reliable convergence performance [J]. Soft Computing, 2011, 15(8):1581-1599.

[73] 王艷嬌,肖婧.基于改進人工蜂群算法的高維多目標優(yōu)化[J].中南大學學報(自然科學版),2015,46(6):2109-2117.

Wang Yanjiao, Xiao Jing. Optimization of multi-objective problems based on artificial bee colony algorithm [J]. Journal of Central South University(Science and Technology), 2015, 46(6): 2109-2117.

[74] Esmat R, Hossein N, Saeid S. GSA: a gravitational search algorithm [J]. Information Sciences, 2009,179, 2232-2248.

[75] Cuevas E, Cienfuegos M, Zaldívar D, et al. A swarm optimization algorithm inspired in the behavior of the social-spider [J]. Expert Systems with Applications, 2013,40 (16):6374-6384.

[76] 肖婧,畢曉君,王科俊.基于全局排序的高維多目標進化算法研究[J].軟件學報,2015,26(7):1574-1583.

Xiao Jing, Bi Xiaojun, Wang Kejun. Research of global ranking based many-objective optimization[J]. Journal of Software, 2015, 26(7):1574-1583.

[77] 索勃,李戰(zhàn)懷,陳群,等.基于信息流動分析的動態(tài)社區(qū)發(fā)現(xiàn)方法[J]. 軟件學報, 2014,25(3):547-559.

Suo Bo, Li Zhanhuai, Chen Qun, et al. Dynamic community detection based on information flow analysis [J]. Journal of Software, 2014, 25(3):547-559.

[78] 國琳,左萬利,彭濤. 基于隸屬度的社會化網(wǎng)絡重疊社區(qū)發(fā)現(xiàn)及動態(tài)集群演化分析[J]. 電子學報, 2016, 44(3):587-594.

Guo Lin, Zuo Wanli, Peng Tao. Overlapping community detection and dynamic group evolution analysis based on the degree of membership in social network [J]. Acta Electronica Sinica, 2016, 44(3):587-594.

ResearchProgressofFuzzyOverlappingCommunityDetectioninComplexNetworks

XIAO Jing1, ZHANG Yongjian1, XU Xiaoke1,2

(1.College of Information and Communication Engineering, Dalian Minzu University, Dalian 116600, China；2.Guizhou Provincial Key Laboratory of Public Big Data, Guizhou University, Guiyang 550025, China)

Through expanding value space, fuzzy overlapping detection redefines the fuzzy membership degree, which can not only improve the detection accuracy of the complicated community structures, but also explore the overlapping features of nodes and communities. In this paper, we firstly give the explanation of the difference between crisp and fuzzy overlapping detection, and then summarize their related researches. To clearly state the fuzzy overlapping detection, we introduce the available work by dividing them into five classes on the acquisition method of fuzzy membership degree, including expanded label propagation, nonnegative matrix factorization, edge nodes based two-phase detection, fuzzy clustering and fuzzy modularity optimization. The advances and challenges of the fuzzy modularity optimization based on evolutionary algorithms are discussed in detail. At last some future research topics are given.

community detection; crisp overlap; fuzzy overlap; fuzzy modularity optimization; evolutionary algorithm

1672-3813(2017)03-0008-22；

10.13306/j.1672-3813.2017.03.002

TP399

A

2016-12-12；

2017-03-01

國家自然科學基金(61374170,61603073,61773091)、遼寧省自然科學基金(201602200)、遼寧省博士科研啟動基金(201601294)、中央高?；究蒲袠I(yè)務費專項基金(DC201502060201,DCPY2016002)、黑龍江省博士后科學基金(LBH-Z12073)

肖婧(1985-)，女，湖北十堰人，博士，講師，主要研究方向為高維多目標優(yōu)化和網(wǎng)絡社團檢測。

許小可(1979-)，男，遼寧莊河人，博士，教授，主要研究方向為網(wǎng)絡科學和社交網(wǎng)絡大數(shù)據(jù)。

(責任編輯李進)