[發(fā)明專利]帶粒子多樣性和變異策略的離散粒子群網(wǎng)絡(luò)社團(tuán)檢測方法

在審

• 申請?zhí)枺?/td>: 201911035521.X
• 申請日: 2019-10-29
• 公開（公告）號: CN110909855A
• 公開（公告）日: 2020-03-24
• 發(fā)明（設(shè)計(jì)）人: 李向軍;劉凌鋒;劉伯成;王科選;周順;吳曉亮;卿松
• 申請（專利權(quán)）人: 南昌大學(xué)
• 主分類號: G06N3/00
• 分類號: G06N3/00;G06Q50/00
• 代理公司: 南昌贛專知識產(chǎn)權(quán)代理有限公司 36129
• 代理人: 夏軍

本發(fā)明公開了帶粒子多樣性和變異策略的離散粒子群網(wǎng)絡(luò)社團(tuán)檢測方法，包括以下步驟：(1)離散方式重新定義了粒子編碼、粒子速度、粒子位置及其進(jìn)化操作；(2)基于混合慣性權(quán)重調(diào)整策略；(3)基于自適應(yīng)性變異策略。本發(fā)明提出了一種帶粒子多樣性和變異策略的離散粒子群網(wǎng)絡(luò)社團(tuán)檢測方法，以離散方式重新定義了粒子編碼、粒子速度、粒子位置及其進(jìn)化操作，基于混合慣性權(quán)重調(diào)整策略和基于自適應(yīng)性變異策略加快方法的收斂速度且避免陷入局部最優(yōu)。通過在人工基準(zhǔn)數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果驗(yàn)證了本發(fā)明方法的有效性。

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

本發(fā)明涉及數(shù)據(jù)挖掘領(lǐng)域，尤其涉及帶粒子多樣性和變異策略的離散粒子群網(wǎng)絡(luò)社團(tuán)檢測方法。

背景技術(shù)

復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測是復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域中一個具有代表性的熱點(diǎn)問題。人們對現(xiàn)實(shí)中的許多系統(tǒng)都抽象為復(fù)雜網(wǎng)絡(luò)進(jìn)行研究，網(wǎng)絡(luò)的節(jié)點(diǎn)對應(yīng)為系統(tǒng)中的實(shí)體，網(wǎng)絡(luò)的邊對應(yīng)著實(shí)體之間的某種關(guān)系。許多研究人員對各種領(lǐng)域的網(wǎng)絡(luò)進(jìn)行了研究，例如社交網(wǎng)絡(luò)、信息網(wǎng)絡(luò)、生物網(wǎng)以及代謝調(diào)節(jié)網(wǎng)絡(luò)。經(jīng)過多年的研究，研究員們發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)具有某些共有的特性，比如小世界性、高聚集性、冪率分布性及無標(biāo)度等，且上述特性都主要與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)有關(guān)。這些發(fā)現(xiàn)促進(jìn)了研究人員們對復(fù)雜世界的認(rèn)知結(jié)構(gòu)，且掌握這些特性可以幫助人們在許多領(lǐng)域解決一系列重要問題。

社團(tuán)結(jié)構(gòu)是指網(wǎng)絡(luò)中社團(tuán)的組成結(jié)構(gòu)及相互關(guān)系，它是根據(jù)社會行為和社會關(guān)系建立。根據(jù)圖論中的定義，社團(tuán)網(wǎng)絡(luò)由網(wǎng)絡(luò)圖中的若干節(jié)點(diǎn)和連接組成。社團(tuán)網(wǎng)絡(luò)聚類將整個網(wǎng)絡(luò)劃分成若干個小“碎片”，其中同一“碎片”內(nèi)的相似性最大，不同“碎片”間的相似性則最小，這些“碎片”可以統(tǒng)稱為社團(tuán)結(jié)構(gòu)。通過社團(tuán)的發(fā)現(xiàn)可以幫助我們了解復(fù)雜網(wǎng)絡(luò)的功能和結(jié)構(gòu)特性。經(jīng)典社團(tuán)發(fā)現(xiàn)算法可以大致分為兩大類：基于優(yōu)化的方法和啟發(fā)式方法。基于優(yōu)化的方法是通過優(yōu)化預(yù)定義的目標(biāo)函數(shù)來發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)，而啟發(fā)式方法是將問題轉(zhuǎn)化為預(yù)定義啟發(fā)式規(guī)則設(shè)計(jì)問題。發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)能夠發(fā)現(xiàn)新的特性和現(xiàn)象，有助于更加深刻的理解和認(rèn)識網(wǎng)絡(luò)結(jié)構(gòu)和功能之間的關(guān)系。

傳統(tǒng)粒子群優(yōu)化算法在優(yōu)化過程中容易產(chǎn)生的局部最優(yōu)，無法滿足更深一層問題的研究。

發(fā)明內(nèi)容

為了克服現(xiàn)有技術(shù)的缺陷，本發(fā)明采用基于粒子多樣性的混合慣性權(quán)重調(diào)整策略和自適應(yīng)變異策略兩種進(jìn)化策略避免了算法的局部收斂并在此基礎(chǔ)上，提出了帶粒子多樣性和變異策略的離散粒子群網(wǎng)絡(luò)社團(tuán)檢測方法，該算法能夠有效檢測復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)，且具有穩(wěn)定的社團(tuán)劃分質(zhì)量和全局收斂性提出帶粒子多樣性和變異策略的離散粒子群網(wǎng)絡(luò)社團(tuán)檢測方法，該算法能夠有效檢測復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)，且具有穩(wěn)定的社團(tuán)劃分質(zhì)量和全局收斂性。

為達(dá)此目的，本發(fā)明采用以下技術(shù)方案：

本發(fā)明的帶粒子多樣性和變異策略的離散粒子群網(wǎng)絡(luò)社團(tuán)檢測方法，包括以下步驟：

A、首先以離散方式定義粒子編碼、粒子速度、粒子位置及其進(jìn)化操作：由于社團(tuán)檢測一個是典型的離散優(yōu)化問題，本方法從編碼到進(jìn)化操作都是采用離散方式；因而，本方法定義粒子每一維對應(yīng)的整數(shù)即為該節(jié)點(diǎn)所從屬的社團(tuán)；

定義粒子速度：單個粒子i，其速度向量表示為定義粒子位置與位置的減法操作Ξ：兩個粒子的位置向量為和兩個位置向量的減法操作Ξ表示粒子位置的變化量ΔP(即速度V)，

定義學(xué)習(xí)因子與速度的乘法操作×：速度向量的每一維乘以學(xué)習(xí)因子得到經(jīng)過“學(xué)習(xí)”的速度；速度的合并操作∧：為兩個速度向量，即其中

定義位置與速度的加法操作⊕：粒子位置為經(jīng)過與速度的加法操作⊕后的新位置為那么其中：

其中表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合，Deg(i)表示節(jié)點(diǎn)i的度數(shù)。包含節(jié)點(diǎn)i的各鄰點(diǎn)所從屬社團(tuán)標(biāo)識即，其中k表示節(jié)點(diǎn)i的各鄰點(diǎn)從屬k個不同社團(tuán)；定義了離散粒子群的進(jìn)化模型為及

本發(fā)明利用離散編碼的粒子群進(jìn)化方法檢測復(fù)雜網(wǎng)絡(luò)中的社團(tuán)數(shù)量。