[發明專利]基于遺傳算法的異構社會網絡社區檢測方法

無效

• 申請號: 201310651893.1
• 申請日: 2013-12-04
• 公開（公告）號: CN103605793A
• 公開（公告）日: 2014-02-26
• 發明（設計）人: 劉靜;焦李成;曾玉潔;馬文萍;馬晶晶;李陽陽
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06N3/12
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 王品華;朱紅星

1.一種基于遺傳算法的異構社會網絡社區檢測方法，包括如下步驟：

1)對異構網絡中的節點類別數k和每類節點的個數n₁，n₂，…，n_k進行統計，得到網絡中節點總個數n=n₁+n₂+…+n_k；用每類節點的個數和節點之間聯系信息構建描述異構社會網絡的k維鄰接矩陣A，A的大小為n₁×n₂…×n_k；

2)令初始種群的大小pn=50，根據節點總個數n隨機產生pn個采用符號編碼的個體，用這些個體組成初始種群p₀；設置交叉概率pc=0.8，變異概率pm=0.2，初始代數g₀=1，最大代數mg=50，當前代數g=g₀，令第g代父代種群p_g等于初始種群p₀，即p_g=p₀；

3)計算第g代父代種群p_g中每個個體的適應度函數值D：

D=Σc=1mL(Vc)-L(V‾c)|Vc|-L(V)n,]]>

式中，m是個體中的基因值種類個數，V¹,V²,…,V^m是由個體得到的m個社區的節點集合，V是網絡中所有節點集合，即V=V¹∪V²∪…∪V^m，是節點集合V^c在V中的差集，即1≤c≤m，|V^c|是社區V^c中的節點個數，L(V^c)是第c個社區內的連邊條數，是從第個c社區連接到網絡中除第c個社區之外的其他社區的連邊條數，L(V)是網絡中的總連邊條數；

4)根據第g代父代種群p_g中每個個體的適應度函數值D，對第g代父代種群p_g進行精英保留操作和錦標賽選擇操作，得到更新后的第g代父代種群p_g’；

5)隨機產生第一隨機數rand₁，并對第一隨機數rand₁和交叉概率pc進行比較，如果rand₁<pc，執行第6)步；否則，得到與更新后的第g代父代種群p_g’相等的第g代子代種群chp_g，即chp_g=p_g’，執行第7)步；

6)對更新后的第g代父代種群p_g’進行單路交叉操作，得到第g代子代種群chp_g；

7)對第g代子代種群chp_g中每個個體R進行變異操作，得到更新后的第g代子代種群chp_g’；

8)令當前代數g=g+1，將當前代數g與最大代數mg進行比較，若g≤mg，則第g代的父代種群p_g與更新后的第g-1代子代種群chp_g-1’相等，即p_g=chp_g-1’，返回步驟3)；否則，執行步驟9）；

9)取更新后的第g-1代子代種群chp_g-1’中適應度函數值最高的個體，將該個體還原成對應的異構網絡，解碼得到劃分出的社區結構。