[發(fā)明專利]一種基于共識社團(tuán)布谷鳥算法的動(dòng)態(tài)網(wǎng)絡(luò)聚類方法及系統(tǒng)

在審

• 申請?zhí)枺?/td>: 202110961258.8
• 申請日: 2021-08-20
• 公開（公告）號: CN113837221A
• 公開（公告）日: 2021-12-24
• 發(fā)明（設(shè)計(jì)）人: 陳國強(qiáng);馬巖;趙艷麗;周宏基
• 申請（專利權(quán)）人: 河南大學(xué)
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N3/00;G06N3/04;G06Q50/00
• 代理公司: 鄭州大通專利商標(biāo)代理有限公司 41111
• 代理人: 張立強(qiáng)

本發(fā)明公開一種基于共識社團(tuán)布谷鳥算法的動(dòng)態(tài)網(wǎng)絡(luò)聚類方法及系統(tǒng)，該方法包括：采用標(biāo)簽傳播算法得到初始時(shí)刻的社團(tuán)劃分，獲得社團(tuán)內(nèi)共識；從第2個(gè)時(shí)刻開始，采用基于有序鄰居列表的編碼方式生成鳥巢群落；采用經(jīng)過重定義的萊維飛行公式對鳥巢的位置進(jìn)行更新，按照放棄算子對部分鳥巢進(jìn)行重建；對鳥巢進(jìn)行排序，經(jīng)過精英選擇策略從群落中保留適應(yīng)度好的鳥巢；鳥巢對社團(tuán)內(nèi)共識進(jìn)行投票以獲得當(dāng)前時(shí)刻的社團(tuán)間共識，將社團(tuán)間共識插入到群落當(dāng)中；重新計(jì)算社團(tuán)內(nèi)共識用于下一時(shí)刻群落的更新，選擇knee解作為最優(yōu)解，輸出該時(shí)刻所對應(yīng)的動(dòng)態(tài)網(wǎng)絡(luò)劃分結(jié)果，直至得到每個(gè)時(shí)刻下的社團(tuán)結(jié)構(gòu)。本發(fā)明可以保證當(dāng)前時(shí)刻的社團(tuán)向與上一時(shí)刻相似的方向進(jìn)化。

技術(shù)領(lǐng)域

本發(fā)明屬于動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)檢測技術(shù)領(lǐng)域，尤其涉及一種基于共識社團(tuán)布谷鳥算法的動(dòng)態(tài)網(wǎng)絡(luò)聚類方法及系統(tǒng)。

背景技術(shù)

隨著計(jì)算機(jī)技術(shù)的迅猛發(fā)展，從復(fù)雜網(wǎng)絡(luò)中發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)在這十幾年里得到了廣泛研究。復(fù)雜網(wǎng)絡(luò)可以將現(xiàn)實(shí)中抽象的復(fù)雜系統(tǒng)進(jìn)行建模，其中節(jié)點(diǎn)代表系統(tǒng)中的實(shí)體，邊代表實(shí)體間的聯(lián)系。復(fù)雜網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)已經(jīng)在社會(huì)網(wǎng)絡(luò)、信息網(wǎng)絡(luò)、生物網(wǎng)絡(luò)中得到了充分的應(yīng)用。例如，在科學(xué)家協(xié)作網(wǎng)絡(luò)中，社團(tuán)結(jié)構(gòu)表示發(fā)表過相同或相似領(lǐng)域的科學(xué)家們；在Web頁面網(wǎng)絡(luò)，社團(tuán)結(jié)構(gòu)表示有著相同或相似主題的一組頁面；在蛋白質(zhì)相互作用網(wǎng)絡(luò)中，社團(tuán)結(jié)構(gòu)表示提供相同或者輔助作用的蛋白質(zhì)集合。尋找這種結(jié)構(gòu)的研究問題稱為社團(tuán)檢測(聚類)問題。

社區(qū)檢測可以轉(zhuǎn)化為對優(yōu)化問題求最優(yōu)解，其難度為NP級。因此，許多研究人員將進(jìn)化算法(EAs)引入到這一技術(shù)領(lǐng)域，并開發(fā)了一些有前途的解決方案。然而，這些算法只能發(fā)現(xiàn)靜態(tài)網(wǎng)絡(luò)中的社區(qū)。但是，現(xiàn)實(shí)世界的網(wǎng)絡(luò)不總是靜態(tài)的，而是處于動(dòng)態(tài)變化中。例如，在科學(xué)協(xié)作網(wǎng)絡(luò)中，社區(qū)是動(dòng)態(tài)發(fā)展的，由于科學(xué)家對研究興趣和方向發(fā)生改變，相應(yīng)的社團(tuán)結(jié)構(gòu)也會(huì)發(fā)生變化；蛋白質(zhì)與蛋白質(zhì)的相互作用隨時(shí)間和空間而變化，從而導(dǎo)致蛋白質(zhì)復(fù)合物在細(xì)胞周期過程中組裝和拆卸。隨著科學(xué)家們逐漸重視事物的動(dòng)態(tài)變化，動(dòng)態(tài)網(wǎng)絡(luò)在許多領(lǐng)域越來越受歡迎，因?yàn)樗跒楦櫨W(wǎng)絡(luò)結(jié)構(gòu)的動(dòng)態(tài)變化提供了大量的機(jī)會(huì)。

進(jìn)化聚類是目前廣泛用于動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)檢測的框架。它的主要思想是在一種時(shí)間平滑框架下，在每個(gè)時(shí)間步上生成聚類。這個(gè)時(shí)間平滑框架假定在一段很短的時(shí)間間隔內(nèi)社團(tuán)的改變很小，且最好的社團(tuán)結(jié)構(gòu)應(yīng)當(dāng)通過同時(shí)考慮當(dāng)前時(shí)刻和前一時(shí)刻的社團(tuán)結(jié)構(gòu)來獲得。因此，進(jìn)化聚類符合動(dòng)態(tài)網(wǎng)絡(luò)社區(qū)檢測涉及的兩個(gè)相互沖突的準(zhǔn)則。第一個(gè)是快照質(zhì)量的最大化，它衡量的是當(dāng)前時(shí)刻社團(tuán)對快照的效率。第二種是時(shí)間代價(jià)最小化，表示兩個(gè)聚類在連續(xù)時(shí)間步長的距離。動(dòng)態(tài)網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的檢測可表示為一個(gè)多目標(biāo)優(yōu)化問題(MOP)。為此，提出了一種動(dòng)態(tài)多目標(biāo)遺傳算法(dynamic multiobjective geneticalgorithms,DYNMOGA)[D.Chakrabarti,R.Kumar,and A.Tomkins,“Evolutionaryclustering,”in Proc.ACM SIGKDD Int.Conf.Knowl.Disc.Data Min.,2006,pp.554–560.]，利用遺傳算法發(fā)現(xiàn)動(dòng)態(tài)網(wǎng)絡(luò)中的群落，優(yōu)化了歸一化互信息(NMI)[L.Danon,A.Díaz-Guilera,J.Duch,and A.Arenas,“Comparing community structureidentifification,”J.Stat.Mech.Theory Exp.,vol.2005,no.9,2005,Art.no.P09008.]和模塊化[M.Girvan and M.E.Newman,“Community structure in social andbiological networks,”Proc.Nat.Acad.Sci.USA,vol.99,no.12,pp.7821–7826,2002.]。第一個(gè)目標(biāo)NMI是信息論中一個(gè)眾所周知的熵度量，它量化了當(dāng)前時(shí)刻和上一時(shí)刻的兩個(gè)社團(tuán)結(jié)構(gòu)的相似性。第二個(gè)目標(biāo)，模塊化，是快照質(zhì)量的最大化，它度量社團(tuán)在當(dāng)前時(shí)間代表網(wǎng)絡(luò)的程度。