甘
肃
科
技
第2 9卷
第二个目标函数对节点的适应度进行了定义, 把社区内所有模块| s 的适应度值加起来得到社区
m a n所提经典数据集的扩展。该网络由 1 2 8个节点组成,分为 4个社区,每个社区 3 2个节点。每个节点的平均度为 l 6,以的比率连接社团外部的顶点, I y的比率连接社团内部的顶点。y被称为混合参 —
适应度值,以此作为第二个目标进行计算。. s i的适 应度值可由公式 ( 5 )得出。因此最小化的第二个目 标可以表示为: EP( S ) ( 6 )
数。当< 0 . 5时,一个节点在其社团内的邻居比属于社团外部的多。我们设立了 值从 0 . 1到O . 5各不相同的 1 0个网
络,采用规范化互信息来评估真实分区与发现的分区之间的相似性。 由图 1和图 2可以看出: 1 )当混合参数≤0 . 2 时, N M I值在 0 . 7 8以上,接近 1; Q值在 0 . 3以上,说明M O G A算法可以发现 8 0%以上的社区结构。2 )
这两个目标函数都拥有一个正数实值参数来控制社区的大小。参数值越高,划分的社区就越小。
多目标遗传算法利用这两个函数的优点,在查找范 围内有选择性地获取网络内已有的社区,而不需要
事先知道社区的具体数量。该数值由这两个目标的 最优折衷值自动决定。
当式( 2 )中用来计算社区分值的指数 r= 2时,不同 的混合参数都能取得较好的 N M I值和 Q值,表明划 分的社区都是相关联的。3 )当 y= 0 . 5,就很难识别出隐藏的社区,图中相应的 N M I和 Q值也说明了这 一
3 实验结果 为了测试 M O G A算法的可行性和有效性,基于 M a d a b平台进行实验。具体参数如下:交叉率 P =
点。
0 . 8,变异率 P= 0 . 2,精英再生为群体大小的 1 0%, 用轮盘赌选择函数。种群规模 N=3 0 0,迭代次数 t =1 0 0。
实验环境: WI N X P C e l 2 . 1 0 G I 6 0 M D D R。 3 . 1评估指标
为了判断划分是否优秀,必须定义出有效性指标来对算法所得出的结果进行评估。有效性指标也被称为质量函数,它是一种为网络的每个划分分配 分值的函数。有效性指标可以是内部的,也可以是
外部的。最受欢迎的内部质量函数是 N e w m a n和 G i r v a n提出的模块度 Q。另一方面,采用规范化互 信息( N M I )来评估真实分区与所检测出来的社区的 相似性。
图 1不同混合参数下的规范化互信息
假设 A和是一个网络的两种划分, c为混合矩阵,其元素 C 表示划分 A中的社区里面的顶点在划分 B中的社区_『里面也出现的个数。根据信息论的原理,规范化互信息 N M I ( A, B )定义为: N MI ( A, B)=
二 圣星!圣
墨
:
r 7、
∑ l C‘ l o g ( C / N )+∑ C . i l o g ( C 4/ N )
其中, C 和C。分别表示划分 A和中社区的 个数, C 表示 C中第 i行元素之和, C,
表示 C中第 _『 列元素之和, J 7 v是节点的数量。如果 A= B, N M I ( A, )= 1。如果 A和完全不同, N M I ( A, = 0。 3 . 2模拟数据集 图 2不同混合参数下的模块度
3 . 3真实数据集
研究了 M O G A算法在四个真实网络中的运用,
为了对我们的方法进行检验,采用文献[ 2]的它们分别是, Z a c h a r y空手道俱乐部网络、海豚网方法生成标准数据集,该数据集是对 G i r v a n和 N e w— 络引、 M I T蓝牙设备交互网络、电力调度网络引,

一种基于多种群遗传算法的复杂网络社区结构发现新算法, 该算法无须预先知道社区...遗传算法 中图分类号: TP393 文献标志码: A 文章编号: 1001-3695 ( 2012 ...
一种基于多种群遗传算法的复杂网络社区结构发现新算法, 该算法无须预先知道社区...关键词:复杂网络;网络社区;社区结构;多种群;遗传算法 中图分类号:T33P9 文献...
关键词:复杂网络;社区结构;评价函数;算法 中图分类...(2011)03—0031一04 社区结构是复杂网络的一种重要...本文采用单亲遗传算法来求解这一问题,下 面主要阐述...
已成为当前最重要的多学科交 叉研究领域之一[1?4...就是要探测并揭示出 异构复杂网络中固有的社区结构....文中遗传算法 LGA 也采 用 Q 函数作为目标函数和...
一种快速的优秀的基于多目标的遗传算法 摘要——多目标进化算法(EAS) ,使用非支配排序和共享的方法,关键主要表现为:1)O ( MN3)计算复杂度线索(其中 M 是目标...
外文翻译---一种基于树结构的快速多目标遗传算法_生产/经营管理_经管营销_专业资料。附录 4 附录 4 一种基于树结构的快速多目标遗传算法 介绍: 一般来讲,解决多...
一种QoS路由多目标遗传算法杨云1一,徐永红1,李千目...江苏扬州225009) 摘要:对网络拓扑结构和Qos路由指标...多目标遗传算法 中图分类号:TP393 文献标识码:A ...
社区发现是复杂网络挖掘中的重要任务之一,在恐怖组织...其目标是将网络节点集划分为多个内部链接紧密而外部...算法的质量很大程度上取决于网络社区结构质量评判指标...
关 : 遗传算法 ; 并行算法 ; 多目标优化 ; 多学科优化 键词 中图分类号 ...(Multidisciplinary Design Opti2 mization ,MDO) 是一种解决实际复杂系统设计问题...
遗传算法在多目标优化圈中为是最优的解 决方法,而且...将所得的全部新个体都划分到同一个种群内,相当 于...在收敛上, 适应度高的个体将取代 原有的结构相似的...
热门文档