[發明專利]帶粒子多樣性和變異策略的離散粒子群網絡社團檢測方法

在審

• 申請號: 201911035521.X
• 申請日: 2019-10-29
• 公開（公告）號: CN110909855A
• 公開（公告）日: 2020-03-24
• 發明（設計）人: 李向軍;劉凌鋒;劉伯成;王科選;周順;吳曉亮;卿松
• 申請（專利權）人: 南昌大學
• 主分類號: G06N3/00
• 分類號: G06N3/00;G06Q50/00
• 代理公司: 南昌贛專知識產權代理有限公司 36129
• 代理人: 夏軍

1.帶粒子多樣性和變異策略的離散粒子群網絡社團檢測方法，其特征在于，包括以下步驟：

A、首先以離散方式定義粒子編碼、粒子速度、粒子位置及其進化操作：由于社團檢測一個是典型的離散優化問題，本方法從編碼到進化操作都是采用離散方式；因而，本方法定義粒子每一維對應的整數即為該節點所從屬的社團；

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

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

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

其中表示節點i的鄰居節點集合，Deg(i)表示節點i的度數。包含節點i的各鄰點所從屬社團標識即，其中k表示節點i的各鄰點從屬k個不同社團；定義了離散粒子群的進化模型為及

本發明利用離散編碼的粒子群進化方法檢測復雜網絡中的社團數量。

B、基于混合慣性權重調整策略：線性遞減的慣性權重策略能夠隨著粒子群搜索的動態地對參數進行調整，利于粒子群早期在寬泛的區域內搜尋全局最優，在迭代后期利于粒子群體的局部精細搜索，采用差異度函數來定義粒子的多樣性，即其中Div(X_i)代表粒子i的多樣性函數，n是粒子的維數，count(P_i,P_g)表示粒子i的歷史最優位置和群體最優位置相異維數的個數；慣性權重的調整策略，即ω_i＝ω_min+(ω_max-ω_min)·Div(X_i)其中，ω_i表示粒子i的慣性權重；ω_max表示慣性權重最大值，ω_min表示慣性權重最小值；

C、基于自適應性變異策略：設定一個粒子的隨機變異概率σ，在每個粒子中的節點數值代表粒子對于社團的劃分方案，在粒子群的一次變化期間，粒子節點會有概率σ向模塊度增大的方向變化，當節點在其鄰居節點社團標識范圍內取得社團標識后的模塊度越大，則節點就更有可能屬于該社團；該策略能在一定程度上避免陷入提前收斂，且社團劃分結果也更加符合真實社團情況。

2.根據權利要求1所述的帶粒子多樣性和變異策略的離散粒子群網絡社團檢測方法，其特征在于：

步驟A中所述的了離散粒子群的進化模型定義了離散粒子的位置向量，學習因子與速度的乘法操作×及位置與速度的加法操作

3.根據權利要求1所述的帶粒子多樣性和變異策略的離散粒子群網絡社團檢測方法，其特征在于：

步驟B中所述的基于混合慣性權重調整策略，這是由于復雜網絡中的社團檢測算法在計算初期易于陷入局部最優，其中，優先設定ω_max為慣性權重最大值，ω_min為慣性權重最小值。

4.根據權利要求1所述的帶粒子多樣性和變異策略的離散粒子群網絡社團檢測方法，其特征在于：

步驟C中所述的基于自適應性變異策略，該策略為避免粒子群優化算法陷入局部收斂設定了粒子的隨機變異概率σ，其中方法有利于粒子節點向模塊度增加方向變化。