[發(fā)明專利]基于共鄰矩陣譜信息的多目標(biāo)社區(qū)檢測方法

有效

• 申請?zhí)枺?/td>: 201210066846.6
• 申請日: 2012-03-14
• 公開（公告）號: CN102594909A
• 公開（公告）日: 2012-07-18
• 發(fā)明（設(shè)計）人: 李陽陽;陳靜;焦李成;劉若辰;公茂果;馬文萍;尚榮華;于昕
• 申請（專利權(quán)）人: 西安電子科技大學(xué)
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 陜西電子工業(yè)專利中心 61205
• 代理人: 王品華;朱紅星

1.一種基于共鄰矩陣譜信息的多目標(biāo)社區(qū)檢測方法，包括如下步驟：

(1)根據(jù)網(wǎng)絡(luò)的節(jié)點(diǎn)和邊的信息，建立網(wǎng)絡(luò)的N階鄰接矩陣A：若節(jié)點(diǎn)i和j之間有邊相連，則A_i，j＝1，否則A_i，j＝0，N為網(wǎng)絡(luò)中節(jié)點(diǎn)的個數(shù)；

(2)根據(jù)鄰接矩陣A建立網(wǎng)絡(luò)的共鄰矩陣M，該M中的元素M_i，j為：表示節(jié)點(diǎn)i和k之間的邊的連接關(guān)系，如果節(jié)點(diǎn)i和k之間有邊相連，則A_i，k＝1，否則A_i，k＝0，A_j，k表示節(jié)點(diǎn)j和k之間的邊的連接關(guān)系，如果節(jié)點(diǎn)j和k之間有邊相連，則A_j，k＝1，否則A_j，k＝0，k的取值為從1到N；

(3)將M_i，j更新為：M′_i，j＝(M_i，j+1)×A_i，j，對i和j分別從1取到N，得到由M′_i，j構(gòu)成的修正后的共鄰矩陣M′；

(4)根據(jù)修正后的共鄰矩陣M′求出對角矩陣D及D的逆矩陣D^-1；

(5)根據(jù)共鄰矩陣M′和逆矩陣D^-1求出標(biāo)準(zhǔn)矩陣：NO＝D^-1M′，然后對標(biāo)準(zhǔn)矩陣NO進(jìn)行特征值分解，求出特征值λ₁，λ₂，…，λ_N和對應(yīng)的特征向量V₁，V₂，…，V_N，對N個特征值降序排列為λ′₁≥λ′₂≥…≥λ′_N，與這N個降序排列的特征值相對應(yīng)的降序排列后的特征向量分別為V′₁，V′₂，…，V′_N，每個降序排列后的特征向量都用列表示，把所有降序排列后的特征向量按列堆疊構(gòu)成了一個矩陣V′，那么V′中每一列代表一個降序排列后的特征向量，每一行則代表了一個節(jié)點(diǎn)，節(jié)點(diǎn)的維數(shù)為N，求出降序排列后的特征向量V′₂的最大值和最小值分別為：a＝max(V′₂)，b＝min(V′₂)；

(6)設(shè)定自適應(yīng)多目標(biāo)和聲搜索算法的各個參數(shù)，初始化大小為S的父代和聲記憶庫H(t)＝{H₁(t)，H₂(t)，…，H_S(t)}，t＝0：每一個和聲H_i(t)，i＝1，2，…，S包括標(biāo)記部分和中心部分兩個部分，標(biāo)記部分為h1(t)={flag1,flag2,...,flagKmax},]]>flag1,flag2,...,flagKmax]]>均是0-1之間隨機(jī)分布的隨機(jī)數(shù)，中心部分為均是a-b之間隨機(jī)分布的隨機(jī)數(shù)，K_max為設(shè)定的參數(shù)，表示社區(qū)的最大個數(shù)；

(7)確定父代和聲記憶庫H(t)＝{H₁(t)，H₂(t)，…，H_S(t)}中的每一個和聲的社區(qū)中心，計算每一個和聲中每一個節(jié)點(diǎn)到所有社區(qū)中心的距離，把所有節(jié)點(diǎn)劃分到距離最近的那個社區(qū)中，得到每個和聲的社區(qū)劃分；

(8)根據(jù)得到的社區(qū)劃分計算父代和聲記憶庫中每個和聲的適應(yīng)度；

(9)設(shè)t＝t+1，求出當(dāng)前迭代的和聲保留概率、音調(diào)微調(diào)概率和帶寬，用和聲搜索算法產(chǎn)生子代和聲記憶庫H(t)；

(10)對子代和聲記憶庫H(t)執(zhí)行步驟(7)-(8)；

(11)合并父代和聲記憶庫和子代和聲記憶庫，并對其進(jìn)行快速非支配排序，產(chǎn)生臨時子代和聲記憶庫H′(t)；

(12)對臨時子代和聲記憶庫H′(t)進(jìn)行局部學(xué)習(xí)，得到更新的臨時子代和聲記憶庫H″(t)；

(13)對更新的臨時子代記憶庫H″(t)進(jìn)行快速非支配排序，選出前S個和聲，將其作為父代和聲記憶庫H(t)，對父代和聲記憶庫H(t)進(jìn)行快速非支配排序，得到非支配和聲；

(14)判斷當(dāng)前迭代次數(shù)是否滿足最大迭代次數(shù)，如滿足，執(zhí)行步驟(15)，否則返回步驟(9)；

(15)取出父代和聲記憶庫H(t)中的非支配和聲作為最終的解集；

(16)從最終的解集中找出模塊度最大的和聲，將這個和聲放入大小為1的和聲記憶庫中，作為父代和聲記憶庫，并執(zhí)行步驟(7)，得到對應(yīng)的社區(qū)劃分，作為最終的社區(qū)劃分結(jié)果。