• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      一種基于局部擴(kuò)展優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法*

      2018-02-26 10:13:12楊青泉王慧慧
      關(guān)鍵詞:適應(yīng)度局部種子

      李 慧,楊青泉,王慧慧

      (首都師范大學(xué)教育技術(shù)系,北京100048)

      1 引言

      復(fù)雜網(wǎng)絡(luò)是現(xiàn)實(shí)世界中復(fù)雜系統(tǒng)的高度抽象,如生物系統(tǒng)中的新陳代謝網(wǎng)、蛋白質(zhì)相互作用網(wǎng),科技系統(tǒng)中的因特網(wǎng)、萬維網(wǎng),社會系統(tǒng)中的科學(xué)家協(xié)作網(wǎng)、電子郵件網(wǎng)等。除了小世界特性和無標(biāo)度特性外,社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)最重要的拓?fù)浣Y(jié)構(gòu)特征之一,已成為多學(xué)科交叉研究的熱點(diǎn)[15]。挖掘復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu),對分析網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、理解網(wǎng)絡(luò)的功能及預(yù)測網(wǎng)絡(luò)的行為等具有重要的理論意義和實(shí)用價(jià)值。

      2002年,Girvan和Newman首次提出著名的社區(qū)發(fā)現(xiàn)算法GN,引起了國內(nèi)外研究者的廣泛關(guān)注,隨后在社區(qū)挖掘領(lǐng)域取得了一系列創(chuàng)新性研究成果[6,7]。經(jīng)典的社區(qū)發(fā)現(xiàn)算法包括圖分割、層次聚類、譜聚類、模塊度優(yōu)化及基于模型的方法等,主要圍繞非重疊社區(qū)探測問題展開,具有一定的局限性:(1)需要網(wǎng)絡(luò)的結(jié)構(gòu)信息、社區(qū)規(guī)模和社區(qū)劃分?jǐn)?shù)目等先驗(yàn)知識;(2)全局搜索和計(jì)算影響算法的運(yùn)行速度,計(jì)算復(fù)雜度高;(3)難以發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中社區(qū)的重疊屬性。2005年,Palla等人[8]拓展了傳統(tǒng)社區(qū)模式,允許節(jié)點(diǎn)同時(shí)屬于多個(gè)社區(qū),提出基于派系過濾的重疊社區(qū)發(fā)現(xiàn)算法,開啟了重疊社區(qū)結(jié)構(gòu)識別的研究熱潮,迅速成為社區(qū)挖掘的前沿研究熱點(diǎn)。派系過濾、標(biāo)簽傳播[9]、局部邊聚類優(yōu)化[10]、局部擴(kuò)展優(yōu)化[11,12]等重疊社區(qū)發(fā)現(xiàn)方法,無需完整的網(wǎng)絡(luò)結(jié)構(gòu)信息等先驗(yàn)知識,基于局部拓?fù)浣Y(jié)構(gòu)揭示網(wǎng)絡(luò)整體或局部的社區(qū)結(jié)構(gòu),在計(jì)算代價(jià)、網(wǎng)絡(luò)局部社區(qū)特性挖掘等方面具有更多優(yōu)勢。

      基于局部擴(kuò)展優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法,通常從不同種子節(jié)點(diǎn)開始,根據(jù)給定的優(yōu)化函數(shù),探索種子所在的局部社區(qū)結(jié)構(gòu),由所有局部社區(qū)結(jié)構(gòu)融合成整個(gè)網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu),代表性算法有LFM(Local Fitness Maximization)算法[11]和 GCE(Greedy Clique Expansion) 算法[12]。Lancichinetti等人提出的基于局部結(jié)構(gòu)適應(yīng)度的社區(qū)擴(kuò)展方法LFM是第一個(gè)能同時(shí)發(fā)現(xiàn)重疊社區(qū)及其層次結(jié)構(gòu)的算法。LFM隨機(jī)選取初始種子節(jié)點(diǎn),基于適應(yīng)度函數(shù)的貪婪優(yōu)化,從種子節(jié)點(diǎn)開始逐步合并使節(jié)點(diǎn)適應(yīng)度增加的鄰居節(jié)點(diǎn)或刪除使其減小的節(jié)點(diǎn),直至適應(yīng)度函數(shù)為負(fù)值,得到種子節(jié)點(diǎn)所在的局部社區(qū);搜索過程中,任意節(jié)點(diǎn)可以被多次訪問,使得節(jié)點(diǎn)能夠包含在多個(gè)社區(qū),從而發(fā)現(xiàn)網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu);調(diào)節(jié)分辨率參數(shù)可以獲得社區(qū)的層次結(jié)構(gòu)。LFM算法對初始種子節(jié)點(diǎn)較敏感,隨機(jī)選取種子節(jié)點(diǎn)可能導(dǎo)致劃分結(jié)果的不穩(wěn)定,誤選種子節(jié)點(diǎn)將不能得到合理的社區(qū)結(jié)構(gòu);當(dāng)初始種子節(jié)點(diǎn)位于稀疏的重疊區(qū)域時(shí),會出現(xiàn)左右搖擺的社區(qū)漂移問題,帶來大量的計(jì)算冗余;在局部擴(kuò)展過程中存在刪除節(jié)點(diǎn)操作,可能導(dǎo)致最初的種子節(jié)點(diǎn)被刪除,使得擴(kuò)展過程不再圍繞該種子進(jìn)行,違背社區(qū)的“局部性”[13,14]。GCE 算法首先選取所有節(jié)點(diǎn)規(guī)模不小于k的最大團(tuán)作為種子,然后采用貪心策略從種子開始逐步添加適應(yīng)度函數(shù)最大的節(jié)點(diǎn),直至適應(yīng)度函數(shù)不再增大,得到種子所在的局部社區(qū)Ct;計(jì)算 Ct與已檢測到的社區(qū) C1,C2,…,Ct-1之間的距離,如小于給定的閾值則舍棄Ct,否則保留Ct。GCE算法選取的種子存在相似性,導(dǎo)致不同種子擴(kuò)展得到相似或者冗余的社區(qū)。在種子擴(kuò)展過程中存在社區(qū)刪除操作,使得最終獲得的重疊社區(qū)只能覆蓋整個(gè)網(wǎng)絡(luò)的一部分節(jié)點(diǎn),即算法結(jié)束后存在一部分社區(qū)標(biāo)簽未知的節(jié)點(diǎn)。

      針對上述問題,本文提出一種基于節(jié)點(diǎn)聚集系數(shù)和適應(yīng)度函數(shù)的局部擴(kuò)展式重疊社區(qū)識別算法CFLEM(Local Expansion Method based on Clustering-coefficient and Fitness),主要步驟包括基于節(jié)點(diǎn)聚集系數(shù)的種子選取、基于適應(yīng)度函數(shù)最大化的自然社區(qū)識別以及社區(qū)結(jié)果的對比與合并。本文的主要貢獻(xiàn):

      (1)基于節(jié)點(diǎn)聚集系數(shù)的種子過濾規(guī)則能夠得到局部性好、結(jié)構(gòu)穩(wěn)定的自然社區(qū)識別結(jié)果,避免了結(jié)果抖動(dòng)性問題。

      (2)對社區(qū)識別結(jié)果的對比與合并,能夠在保證高社區(qū)覆蓋率的前提下盡量減少冗余社區(qū)。

      本文分別在 LFR(Lancichinetti-Fortunato-Radicchi)人工網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上對CFLEM算法的性能進(jìn)行測試,并與具有代表性的基于局部擴(kuò)展優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法進(jìn)行對比分析,結(jié)果表明本文算法在稀疏程度不同的網(wǎng)絡(luò)上均能發(fā)現(xiàn)較高質(zhì)量的重疊社區(qū)結(jié)構(gòu)。

      2 基本概念及定義

      2.1 社區(qū)

      復(fù)雜網(wǎng)絡(luò)可以建模為圖 G=(V,E),其中V={v1,v2,…,vn} 為節(jié)點(diǎn)的非空有限集,n為節(jié)點(diǎn)數(shù);E={e1,e2,…,em} 為邊的非空有限集,m 為邊數(shù)。節(jié)點(diǎn)vi的度定義為該節(jié)點(diǎn)的鄰居數(shù),表示為,其中A是圖G的鄰接矩陣。社區(qū)是圖G的節(jié)點(diǎn)內(nèi)聚子圖,其內(nèi)部節(jié)點(diǎn)連接緊密,不同社區(qū)間的節(jié)點(diǎn)連接稀疏,反映了網(wǎng)絡(luò)的模塊化與異質(zhì)性。

      定義1(社區(qū)相似度) 給定圖G中的任意2個(gè)社區(qū)C1和C2,社區(qū)相似度定義為:

      δ(C1,C2)表示社區(qū)C1和C2的相似程度,取值范圍為[0,1],值越大社區(qū)相似性越高。

      2.2 適應(yīng)度函數(shù)

      其中,f(C+{v})和f(C-{v})分別表示在同分辨率情況下的節(jié)點(diǎn)v在社區(qū)C內(nèi)部和在社區(qū)C外部的結(jié)構(gòu)適應(yīng)度。隨著分辨率α的增加,網(wǎng)絡(luò)逐漸呈現(xiàn)細(xì)粒度化趨勢,直至每個(gè)節(jié)點(diǎn)自成一個(gè)獨(dú)立的社區(qū)。根據(jù)節(jié)點(diǎn)適應(yīng)度f(v)可以判定節(jié)點(diǎn)v是重疊節(jié)點(diǎn)還是離散點(diǎn)。

      2.3 聚集系數(shù)

      定義4(節(jié)點(diǎn)的聚集系數(shù)) 假設(shè)圖G=(V,E)中節(jié)點(diǎn)vi有ki個(gè)鄰居節(jié)點(diǎn),則節(jié)點(diǎn)vi的聚集系數(shù)CCi定義為其所有鄰居節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)Ei與可能存在的最大邊數(shù)ki(ki-1)/2的比值,表示為:

      節(jié)點(diǎn)vi的聚集系數(shù)CCi是衡量網(wǎng)絡(luò)集團(tuán)化程度的重要參數(shù),用于描述節(jié)點(diǎn)的聚集程度,即與節(jié)點(diǎn)vi相連的兩個(gè)節(jié)點(diǎn)也相連的可能性。節(jié)點(diǎn)的聚集系數(shù)越大,表明其局部聚集性較高,成為干擾點(diǎn)和離散點(diǎn)的概率相對越小。

      3 算法思想與分析

      本文綜合運(yùn)用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息和節(jié)點(diǎn)的屬性,提出一種基于局部擴(kuò)展優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法,首先根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的拓?fù)涮卣?聚集系數(shù))選取種子節(jié)點(diǎn)作為初始社區(qū),然后采用貪心策略將初始社區(qū)擴(kuò)展為局部自然社區(qū),最后對比、合并不同的局部社區(qū)獲得重疊社區(qū)結(jié)構(gòu)。具體過程見算法1。

      算法1CFLEM算法

      輸入:網(wǎng)絡(luò)G=(V,E),分辨率參數(shù)α。

      輸出:重疊社區(qū)結(jié)構(gòu)C。

      步驟1初始化,C=。

      步驟2根據(jù)種子選取算法,得到種子集合S。

      步驟3當(dāng)S≠時(shí),選擇某個(gè)種子,執(zhí)行步驟4;否則執(zhí)行步驟6。

      步驟4種子擴(kuò)展成局部自然社區(qū)D,調(diào)整種子集合S。

      步驟5將D加入到C中,返回步驟3。

      步驟6對比、合并局部社區(qū)。

      步驟7返回重疊社區(qū)結(jié)構(gòu)C,結(jié)束。

      3.1 種子選取

      種子選取是基于局部擴(kuò)展優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法的關(guān)鍵步驟,對社區(qū)識別結(jié)果的影響不容小覷。LFM算法隨機(jī)選取種子節(jié)點(diǎn),不可避免地導(dǎo)致社區(qū)發(fā)現(xiàn)結(jié)果不穩(wěn)定。GCE算法選取網(wǎng)絡(luò)中所有節(jié)點(diǎn)規(guī)模不小于k的最大團(tuán)作為種子,避免了社區(qū)發(fā)現(xiàn)結(jié)果不穩(wěn)定的問題。但是,較小的k容易導(dǎo)致種子規(guī)模過大、擴(kuò)展得到的局部自然社區(qū)數(shù)增多,形成冗余社區(qū);較大的k則容易導(dǎo)致局部自然社區(qū)數(shù)減少,社區(qū)發(fā)現(xiàn)結(jié)果的覆蓋率降低;由于不同最大團(tuán)之間存在相似性,導(dǎo)致不同種子擴(kuò)展得到的局部社區(qū)是相似的甚至冗余的。

      針對上述問題,本文借鑒從中心節(jié)點(diǎn)出發(fā)進(jìn)行社區(qū)發(fā)現(xiàn)可以提高社區(qū)識別質(zhì)量的思想[15],提出了選取網(wǎng)絡(luò)的核心節(jié)點(diǎn)作為社區(qū)劃分的種子節(jié)點(diǎn)。核心節(jié)點(diǎn)通常位于網(wǎng)絡(luò)中節(jié)點(diǎn)連接緊密的區(qū)域,對信息傳播的貢獻(xiàn)較大。網(wǎng)絡(luò)中的不同社區(qū)與核心節(jié)點(diǎn)之間往往存在對應(yīng)關(guān)系,因此本文采用節(jié)點(diǎn)的聚集系數(shù)作為拓?fù)涮卣髦笜?biāo)來選取種子節(jié)點(diǎn),具體過程見算法2。

      算法2種子選取算法

      輸入:網(wǎng)絡(luò) G=(V,E)。

      輸出:種子集合S。

      步驟1初始化,S=。

      步驟2將節(jié)點(diǎn)按聚集系數(shù)從大到小排序,形成候選種子列表L,所有節(jié)點(diǎn)初始化為無標(biāo)記。

      步驟3取出L中第一個(gè)節(jié)點(diǎn)v,如果v未標(biāo)記,設(shè)置標(biāo)記并將其加入種子集合S。

      步驟4標(biāo)記v的鄰居節(jié)點(diǎn)N(v),從列表L中移除已標(biāo)記的節(jié)點(diǎn)集

      步驟5當(dāng)L≠時(shí),繼續(xù)執(zhí)行步驟3;否則,輸出種子集合S。

      種子選取算法能夠在網(wǎng)絡(luò)中發(fā)掘彼此分散的、局部聚集系數(shù)大的節(jié)點(diǎn),通過這些種子節(jié)點(diǎn)擴(kuò)展而成的自然社區(qū)的局部性好,社區(qū)發(fā)現(xiàn)結(jié)果對全網(wǎng)絡(luò)的覆蓋率高。

      3.2 局部擴(kuò)展

      在擴(kuò)展階段,CFLEM算法通過最大化局部社區(qū)適應(yīng)度函數(shù)的方法對種子節(jié)點(diǎn)進(jìn)行擴(kuò)展得到自然社區(qū),主要包含兩個(gè)步驟:添加當(dāng)前社區(qū)C的鄰居中f(v)為正值的節(jié)點(diǎn)和刪除社區(qū)C中f(v)為負(fù)值的節(jié)點(diǎn),使得社區(qū)C的適應(yīng)度函數(shù)f(C)達(dá)到最大。CFLEM算法采用批添加節(jié)點(diǎn)和批刪除節(jié)點(diǎn)的方法擴(kuò)展社區(qū)C,即首先遍歷C的每一個(gè)鄰居節(jié)點(diǎn)v并記錄其f(v),在遍歷結(jié)束后將f(v)>0的節(jié)點(diǎn)統(tǒng)一加入社區(qū);然后再遍歷社區(qū)C,記錄其每個(gè)節(jié)點(diǎn)v的f(v),遍歷結(jié)束后將f(v)<0的節(jié)點(diǎn)統(tǒng)一移出社區(qū)。具體過程見算法3。

      算法3局部擴(kuò)展算法

      輸入:網(wǎng)絡(luò)G=(V,E),種子s,分辨率參數(shù)α。

      輸出:社區(qū)C;

      C←{s};

      for each neighbor vertex v of C do

      計(jì)算節(jié)點(diǎn)適應(yīng)度f(v)

      end for

      將節(jié)點(diǎn)適應(yīng)度值大于零的鄰居節(jié)點(diǎn)統(tǒng)一加入社區(qū)C;

      for each vertex v of C

      計(jì)算節(jié)點(diǎn)適應(yīng)度f(v)

      end for

      將所有適應(yīng)度值小于零的節(jié)點(diǎn)統(tǒng)一移出社區(qū)C;

      返回C,結(jié)束。

      3.3 社區(qū)合并

      重疊社區(qū)發(fā)現(xiàn)算法允許2個(gè)不同社區(qū)包含若干公共節(jié)點(diǎn),因此種子擴(kuò)展得到的自然社區(qū)之間存在一定的相似性。當(dāng)相似性達(dá)到一定程度時(shí),可能產(chǎn)生“過度重疊”現(xiàn)象,因此有必要對社區(qū)發(fā)現(xiàn)結(jié)果進(jìn)行后處理,發(fā)現(xiàn)其中的冗余社區(qū),簡化社區(qū)結(jié)構(gòu)。

      針對局部擴(kuò)展得到的自然社區(qū),CFLEM算法采用公式(1)計(jì)算任意2個(gè)社區(qū)的相似度,即以它們之間共同節(jié)點(diǎn)在較小的社區(qū)中所占的比例來衡量社區(qū)是否需要合并。如果δ大于某個(gè)給定的閾值ε,則判定需要合并社區(qū)。具體過程見算法4。

      算法4社區(qū)合并算法

      輸入:社區(qū)集合{C},閾值ε。

      輸出:社區(qū)集合{C'}。

      for each c in C do

      if{C'}中存在社區(qū)c'和c的相似度大于ε

      將c合并至社區(qū)c'

      else

      將c加入社區(qū)集合{C'}

      end if

      end for

      返回{C'},結(jié)束。

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

      CFLEM算法的實(shí)現(xiàn)過程可以概括為三個(gè)階段:(1)根據(jù)聚集系數(shù)調(diào)整種子節(jié)點(diǎn)并生成初始社區(qū);(2)將每個(gè)初始社區(qū)擴(kuò)展為局部社區(qū);(3)對比合并社區(qū)。階段(1)需要計(jì)算種子及其鄰居節(jié)點(diǎn)的聚集系數(shù),最壞情況下計(jì)算給定網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的聚集系數(shù)時(shí),時(shí)間復(fù)雜度為O(d2),其中d為節(jié)點(diǎn)的平均度。階段(2)將每個(gè)初始社區(qū)擴(kuò)展為局部社區(qū)的時(shí)間復(fù)雜度為O(n2),n表示社區(qū)的節(jié)點(diǎn)規(guī)模,若存在M個(gè)種子節(jié)點(diǎn)和初始社區(qū),那么階段(2)的總時(shí)間開銷為 O(M珔n2),珔n 表示平均社區(qū)節(jié)點(diǎn)規(guī)模。當(dāng)分辨率參數(shù)α較小時(shí),新節(jié)點(diǎn)的加入導(dǎo)致f(C)增大的機(jī)會更大,使社區(qū)C能夠接納更多的節(jié)點(diǎn),達(dá)到更大的社區(qū)規(guī)模(即珔n比較大),時(shí)間復(fù)雜度隨之增大,最壞情況下時(shí)間復(fù)雜度為O(N2),其中N為網(wǎng)絡(luò)中節(jié)點(diǎn)的規(guī)模。反之,當(dāng)α越來越大時(shí),新節(jié)點(diǎn)的加入對增大f(C)值的貢獻(xiàn)越小,使新節(jié)點(diǎn)加入當(dāng)前社區(qū)的難度增大,從而形成較小規(guī)模的社區(qū)(即珔n比較小),時(shí)間復(fù)雜度將逐漸趨于線性O(shè)(N)。階段(3)最壞情況下的時(shí)間復(fù)雜度為O(M2)。因此,CFLEM算法的時(shí)間復(fù)雜度在最壞情況下為O(d2+N2+M2)。在復(fù)雜網(wǎng)絡(luò)中,由于節(jié)點(diǎn)的平均度dN,種子的個(gè)數(shù)M <N,因此總的來說,CFLEM算法的時(shí)間復(fù)雜度為O(N2)。

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

      本文采用不同規(guī)模、不同屬性的人工網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集測試算法性能,設(shè)置如下2類實(shí)驗(yàn):

      (1)測試當(dāng)節(jié)點(diǎn)數(shù)及混雜系數(shù)變化時(shí)算法性能的變化規(guī)律,網(wǎng)絡(luò)數(shù)據(jù)為LFR網(wǎng)絡(luò)數(shù)據(jù)生成器[16]模擬生成的人工網(wǎng)絡(luò)。

      (2)比較各算法發(fā)現(xiàn)不同網(wǎng)絡(luò)結(jié)構(gòu)的性能,網(wǎng)絡(luò)數(shù)據(jù)為6個(gè)不同規(guī)模、不同類型的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集。

      為了實(shí)現(xiàn)算法的對比分析,采用模塊度函數(shù)Qo作為度量指標(biāo)。Newman等人[17]最先提出的模塊度函數(shù)Q已成為評價(jià)不可重疊社區(qū)發(fā)現(xiàn)算法的重要指標(biāo)。針對重疊社區(qū)劃分的質(zhì)量評價(jià),Shen等人[18]提出了擴(kuò)展模塊度函數(shù)Qo,其函數(shù)表達(dá)式為:

      其中,v、w為節(jié)點(diǎn);K是網(wǎng)絡(luò)包含的社區(qū)數(shù);Ov是節(jié)點(diǎn)v所屬社區(qū)的數(shù)目;Avw為鄰接矩陣A中的元素,如果節(jié)點(diǎn)v、w相連,則Avw=1,否則Avw=0;m=為網(wǎng)絡(luò)中邊的數(shù)目;d是節(jié)點(diǎn)v的度值,v表示在隨機(jī)網(wǎng)絡(luò)中節(jié)點(diǎn)v和節(jié)點(diǎn)w之間存在連邊的可能性。

      當(dāng)復(fù)雜網(wǎng)絡(luò)的社區(qū)內(nèi)部節(jié)點(diǎn)連接越緊密而不同社區(qū)間節(jié)點(diǎn)連接越稀疏時(shí),Qo函數(shù)取值越大,算法社區(qū)劃分的準(zhǔn)確率越高,算法性能越好。

      4.1 不同清晰度的人工網(wǎng)絡(luò)上算法性能的比較

      為了比較具有不同清晰度網(wǎng)絡(luò)上的算法性能,采用不同規(guī)模的人工網(wǎng)絡(luò)測試CFLEM算法與LFM算法隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)及混雜系數(shù)變化的規(guī)律。4類人工網(wǎng)絡(luò)由LFR網(wǎng)絡(luò)數(shù)據(jù)生成器模擬獲得,分別為稀疏網(wǎng)絡(luò)小社區(qū)(SS)、稀疏網(wǎng)絡(luò)大社區(qū)(SL)、稠密網(wǎng)絡(luò)小社區(qū)(DS)和稠密網(wǎng)絡(luò)大社區(qū)(DL),對應(yīng)的LFR參數(shù)(網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N、節(jié)點(diǎn)平均度值珋k、節(jié)點(diǎn)最大度值kmax、社區(qū)最大規(guī)模Cmax、社區(qū)最小規(guī)模Cmin、節(jié)點(diǎn)度指數(shù)t1、社區(qū)規(guī)模指數(shù)t2、重疊節(jié)點(diǎn)數(shù)On、重疊節(jié)點(diǎn)屬于社區(qū)數(shù)Om和混雜系數(shù)μ)見表1。其中,混雜系數(shù)μ反映了網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的清晰程度,該值越小社區(qū)結(jié)構(gòu)越清晰,當(dāng)μ∈[0.7,0.9]時(shí)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)通常不明顯,因此分別在4類網(wǎng)絡(luò)上生成μ∈[0.1,0.6]的測試網(wǎng)絡(luò)。

      Table 1 Parameters setting of synthetic networks表1 人工網(wǎng)絡(luò)數(shù)據(jù)集的參數(shù)設(shè)置

      實(shí)驗(yàn)針對不同算法設(shè)置不同的參數(shù),并選取各參數(shù)下Qo值中的最大值作為最終結(jié)果進(jìn)行對比。具體地,LFM 算法中,設(shè)置參數(shù) α ∈[0.8,1.6],取值間隔為0.1,運(yùn)行次數(shù)r=3;CFLEM算法中,設(shè)置參數(shù) α ∈[0.6,1.2],ε ∈[0,0.9],取值間隔均為0.1。隨著網(wǎng)絡(luò)規(guī)模(節(jié)點(diǎn)數(shù)、邊數(shù))的增加和混雜系數(shù)μ的增大,CFLEM算法與LFM算法在不同清晰度的4類人工網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果如圖1所示。

      總體來看,隨著混雜系數(shù)μ的增加,網(wǎng)絡(luò)中社區(qū)的內(nèi)部節(jié)點(diǎn)連接社區(qū)外部節(jié)點(diǎn)的機(jī)會增大,導(dǎo)致社區(qū)結(jié)構(gòu)變得模糊,社區(qū)發(fā)現(xiàn)的難度變大,使得2種算法社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量降低,因此在4類人工網(wǎng)絡(luò)上2種算法得到的Qo值均有不同程度的下降。其中,LFM算法相對于CFLEM算法的下降幅度更大,尤其在稀疏網(wǎng)絡(luò)小社區(qū)(SS)和稀疏網(wǎng)絡(luò)大社區(qū)(SL)中,當(dāng)社區(qū)結(jié)構(gòu)越來越不明顯時(shí),CFLEM算法展現(xiàn)出一定的優(yōu)勢。

      從圖1中可以看出,CFLEM算法在絕大多數(shù)網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn)結(jié)果要好于LFM算法,原因在于CFLEM算法選取網(wǎng)絡(luò)中的核心節(jié)點(diǎn)作為種子,擴(kuò)展得到的社區(qū)具有更好的局部性;LFM算法則隨機(jī)選取種子,在局部擴(kuò)展時(shí)將節(jié)點(diǎn)適應(yīng)度函數(shù)為負(fù)的種子刪除,導(dǎo)致擴(kuò)展過程不再圍繞該種子進(jìn)行,從而得到局部性較差的社區(qū)。

      對比CFLEM算法、LFM算法在稀疏網(wǎng)絡(luò)小社區(qū)(SS)、稀疏網(wǎng)絡(luò)大社區(qū)(SL)、稠密網(wǎng)絡(luò)小社區(qū)(DS)和稠密網(wǎng)絡(luò)大社區(qū)(DL)的社區(qū)識別結(jié)果,2種算法在稀疏網(wǎng)絡(luò)上的準(zhǔn)確度更好。原因在于:當(dāng)固定混雜系數(shù)μ時(shí),稀疏網(wǎng)絡(luò)相對于稠密網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)更為明顯,能夠較準(zhǔn)確地發(fā)現(xiàn)其中的自然社區(qū)。

      綜上所述,與FLM算法相比,CFLEM算法在不同清晰度的4類人工網(wǎng)絡(luò)數(shù)據(jù)集上能夠取得較高質(zhì)量的社區(qū)發(fā)現(xiàn)結(jié)果。

      4.2 不同結(jié)構(gòu)的真實(shí)網(wǎng)絡(luò)上算法性能的比較

      為了對比分析算法CFLEM、LFM、GCE的結(jié)構(gòu)發(fā)現(xiàn)能力,測試網(wǎng)絡(luò)采用6個(gè)不同規(guī)模、不同類型的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集:人物關(guān)系網(wǎng)絡(luò)(Karate、Football)、動(dòng)物關(guān)系網(wǎng)絡(luò)(Dolphins)、游戲網(wǎng)絡(luò)(Risk)、論文合作網(wǎng)絡(luò)(CA-GrQc)和產(chǎn)品銷售記錄網(wǎng)絡(luò)(Amazon),其基本信息見表2,更多信息參見http://www-personal.umich.edu/~ mejn/netdata、http://snap.stanford.edu/data 和 http://en.wikipedia.org/wiki/Risk_(game)。

      Table 2 Datasets of real-world networks表2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集表

      由于絕大多數(shù)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的社區(qū)結(jié)構(gòu)是未知的,因此除了重疊模塊度函數(shù)Qo外,本文還采用社區(qū)連接密度和網(wǎng)絡(luò)覆蓋率Ro來綜合評價(jià)算法性能。社區(qū)連接密度Do定義為:

      其中,K為網(wǎng)絡(luò)中的社區(qū)數(shù),Do可以看作當(dāng)α=1時(shí)網(wǎng)絡(luò)中所有K個(gè)社區(qū)的局部結(jié)構(gòu)適應(yīng)度的平均值。

      網(wǎng)絡(luò)覆蓋率Ro定義為:

      其中,N、K分別為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)和社區(qū)數(shù),Ci表示第i個(gè)社區(qū)。社區(qū)連接密度Do和網(wǎng)絡(luò)覆蓋率Ro的取值均為[0,1],值越大表明社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量越好。

      對于 GCE 算法,設(shè)置其參數(shù) α∈[0.8,1.6],取值間隔為0.1,參數(shù) k∈{3,4},ε =0.6;CFLEM算法和LFM算法的參數(shù)設(shè)置與4.1節(jié)相同,并選取各參數(shù)下的最優(yōu)結(jié)果進(jìn)行對比。各算法在6個(gè)真實(shí)網(wǎng)絡(luò)下的社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量的Qo、Do、Ro值分別如圖2a、圖2b、圖2c所示,其中橫坐標(biāo)軸表示真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的編號,縱坐標(biāo)軸分別表示3種算法在對應(yīng)數(shù)據(jù)集上的社區(qū)發(fā)現(xiàn)結(jié)果的Qo、Do、Ro值。

      由圖2a可以看出,針對大部分真實(shí)網(wǎng)絡(luò),CFLEM算法得到的Qo值最優(yōu),二者較GCE算法具有較為明顯的優(yōu)勢,表明CFLEM算法能夠得到質(zhì)量較高的重疊社區(qū)結(jié)構(gòu)。

      圖2b表明,CFLEM算法在所有真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上都取得了最高的社區(qū)連接密度Do,LFM算法得到的社區(qū)連接密度相對較低,原因在于CFLEM算法的種子節(jié)點(diǎn)選取方法優(yōu)于LFM算法隨機(jī)選取種子的方法,社區(qū)擴(kuò)展過程圍繞所選種子進(jìn)行,得到了局部性較好的社區(qū)。

      如圖2c所示,CFLEM算法和LFM算法在不同網(wǎng)絡(luò)上均具有較高且較穩(wěn)定的網(wǎng)絡(luò)覆蓋率Ro,而GCE算法的Ro值較差且波動(dòng)較大。LFM算法從無社區(qū)標(biāo)簽的節(jié)點(diǎn)中隨機(jī)選取種子,在算法結(jié)束時(shí)僅剩余極少數(shù)標(biāo)簽不明確的節(jié)點(diǎn),因此其社區(qū)覆蓋率很高。與GCE算法相比,CFLEM算法所選種子之間的相似性更低,擴(kuò)展得到的自然社區(qū)能夠覆蓋更多的網(wǎng)絡(luò)節(jié)點(diǎn);而且CFLEM算法對社區(qū)發(fā)現(xiàn)結(jié)果進(jìn)行了后處理,合并冗余社區(qū),保證了網(wǎng)絡(luò)的高覆蓋率,更符合社區(qū)的真實(shí)情況。GCE算法將冗余的社區(qū)直接舍棄,導(dǎo)致算法結(jié)束時(shí)存在一部分社區(qū)標(biāo)簽未知的節(jié)點(diǎn),社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量較低。

      綜合來看,在6個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上,CFLEM算法社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量最高,LFM算法的結(jié)果質(zhì)量次之,GCE算法的結(jié)果質(zhì)量相對較低。3種算法的結(jié)果均存在不同程度的波動(dòng),但CFLEM算法的波動(dòng)相對較小。

      5 結(jié)束語

      本文提出一種基于節(jié)點(diǎn)聚集系數(shù)和適應(yīng)度函數(shù)的局部擴(kuò)展式重疊社區(qū)發(fā)現(xiàn)算法——CFLEM。該算法選取網(wǎng)絡(luò)的核心節(jié)點(diǎn)作為社區(qū)劃分的種子節(jié)點(diǎn),采用貪心策略將種子擴(kuò)展為局部自然社區(qū),然后對社區(qū)發(fā)現(xiàn)結(jié)果進(jìn)行后處理,合并冗余社區(qū)從而保持社區(qū)的高覆蓋率。在LFR人工網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明:與LFM、GCE算法相比,CFLEM算法能夠在稀疏程度不同的網(wǎng)絡(luò)上獲得更優(yōu)的社區(qū)發(fā)現(xiàn)結(jié)果。下一步的工作將拓展CFLEM算法至加權(quán)網(wǎng)絡(luò)中,致力于加權(quán)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題研究。

      猜你喜歡
      適應(yīng)度局部種子
      改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法
      局部分解 巧妙求值
      非局部AB-NLS方程的雙線性B?cklund和Darboux變換與非線性波
      桃種子
      幸運(yùn)的小種子
      幼兒園(2018年15期)2018-10-15 19:40:36
      可憐的種子
      局部遮光器
      吳觀真漆畫作品選
      基于空調(diào)導(dǎo)風(fēng)板成型工藝的Kriging模型適應(yīng)度研究
      中國塑料(2016年11期)2016-04-16 05:26:02
      少數(shù)民族大學(xué)生文化適應(yīng)度調(diào)查
      同江市| 德安县| 瑞安市| 西吉县| 武强县| 青浦区| 错那县| 安宁市| 礼泉县| 吴桥县| 芜湖市| 永新县| 封丘县| 即墨市| 雷波县| 宝兴县| 青河县| 本溪| 鹿泉市| 镇沅| 永寿县| 德昌县| 大新县| 安福县| 拜城县| 买车| 和田县| 壤塘县| 永州市| 远安县| 磐安县| 泰来县| 屏边| 泸州市| 灌南县| 九龙城区| 长寿区| 蚌埠市| 昂仁县| 将乐县| 兰坪|