主权项 |
1.一种基于遗传算法的异构社会网络社区检测方法,包括如下步骤:1)对异构网络中的节点类别数k和每类节点的个数n<sub>1</sub>,n<sub>2</sub>,…,n<sub>k</sub>进行统计,得到网络中节点总个数n=n<sub>1</sub>+n<sub>2</sub>+…+n<sub>k</sub>;用每类节点的个数和节点之间联系信息构建描述异构社会网络的k维邻接矩阵A,A的大小为n<sub>1</sub>×n<sub>2</sub>…×n<sub>k</sub>;2)令初始种群的大小pn=50,根据节点总个数n随机产生pn个采用符号编码的个体,用这些个体组成初始种群p<sub>0</sub>;设置交叉概率pc=0.8,变异概率pm=0.2,初始代数g<sub>0</sub>=1,最大代数mg=50,当前代数g=g<sub>0</sub>,令第g代父代种群p<sub>g</sub>等于初始种群p<sub>0</sub>,即p<sub>g</sub>=p<sub>0</sub>;3)计算第g代父代种群p<sub>g</sub>中每个个体的适应度函数值D:<maths num="0001"><![CDATA[<math><mrow><mi>D</mi><mo>=</mo><munderover><mi>Σ</mi><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>m</mi></munderover><mfrac><mrow><mi>L</mi><mrow><mo>(</mo><msup><mi>V</mi><mi>c</mi></msup><mo>)</mo></mrow><mo>-</mo><mi>L</mi><mrow><mo>(</mo><msup><mover><mi>V</mi><mo>‾</mo></mover><mi>c</mi></msup><mo>)</mo></mrow></mrow><mrow><mo>|</mo><msup><mi>V</mi><mi>c</mi></msup><mo>|</mo></mrow></mfrac><mo>-</mo><mfrac><mrow><mi>L</mi><mrow><mo>(</mo><mi>V</mi><mo>)</mo></mrow></mrow><mi>n</mi></mfrac><mo>,</mo></mrow></math>]]></maths>式中,m是个体中的基因值种类个数,V<sup>1</sup>,V<sup>2</sup>,…,V<sup>m</sup>是由个体得到的m个社区的节点集合,V是网络中所有节点集合,即V=V<sup>1</sup>∪V<sup>2</sup>∪…∪V<sup>m</sup>,<img file="FDA0000431226180000012.GIF" wi="63" he="66" />是节点集合V<sup>c</sup>在V中的差集,即<img file="FDA0000431226180000013.GIF" wi="235" he="67" />1≤c≤m,|V<sup>c</sup>|是社区V<sup>c</sup>中的节点个数,L(V<sup>c</sup>)是第c个社区内的连边条数,<img file="FDA0000431226180000014.GIF" wi="132" he="77" />是从第个c社区连接到网络中除第c个社区之外的其他社区的连边条数,L(V)是网络中的总连边条数;4)根据第g代父代种群p<sub>g</sub>中每个个体的适应度函数值D,对第g代父代种群p<sub>g</sub>进行精英保留操作和锦标赛选择操作,得到更新后的第g代父代种群p<sub>g</sub>’;5)随机产生第一随机数rand<sub>1</sub>,并对第一随机数rand<sub>1</sub>和交叉概率pc进行比较,如果rand<sub>1</sub><pc,执行第6)步;否则,得到与更新后的第g代父代种群p<sub>g</sub>’相等的第g代子代种群chp<sub>g</sub>,即chp<sub>g</sub>=p<sub>g</sub>’,执行第7)步;6)对更新后的第g代父代种群p<sub>g</sub>’进行单路交叉操作,得到第g代子代种群chp<sub>g</sub>;7)对第g代子代种群chp<sub>g</sub>中每个个体R进行变异操作,得到更新后的第g代子代种群chp<sub>g</sub>’;8)令当前代数g=g+1,将当前代数g与最大代数mg进行比较,若g≤mg,则第g代的父代种群p<sub>g</sub>与更新后的第g-1代子代种群chp<sub>g-1</sub>’相等,即p<sub>g</sub>=chp<sub>g-1</sub>’,返回步骤3);否则,执行步骤9);9)取更新后的第g-1代子代种群chp<sub>g-1</sub>’中适应度函数值最高的个体,将该个体还原成对应的异构网络,解码得到划分出的社区结构。 |