文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 在复杂网络中划分社区结构的一种多目标遗传算法
侵权投诉

在复杂网络中划分社区结构的一种多目标遗传算法

甘

肃

科

技

第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蓝牙设备交互网络、电力调度网络引,

在复杂网络中划分社区结构的一种多目标遗传算法

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email