第2 9卷第 1 0期 2 0 1 3年 5月
甘肃科技 Ga n s u S c i e n c e a n d T e c h n o l o g y
0 . 1 0 . 2 9 ^r Ma y . 2 0 1 3
在复杂网络中划分社区结构的一种多目标遗传算法 陈艺璇 (兰州大学信息科学与工程学院,甘肃兰州 7 3 0 0 0 0 )
摘
要:研究了在复杂网络中查找社区结构的一种多目标遗传算法,该算法对能够识别内部联系紧密但相互之间联
系稀疏的节点群的两组函数进行了优化。算法在不同的等级中设定一套网络分区,在这些等级中,拥有较少数量社
区的解包含了拥有更多社区个数的深层次解。社区的数目自动取决于目标函数更佳的权衡值。通过在模拟和真实网络进行的实验对比表明,该算法能够成功发现网络结构,并且与其他多目标优化算法相比也具有一定的竞争力。 关键词:数据挖掘;复杂网络;社区结构;多目标进化算法 中圈分类号: T P 3 9 3
在现实世界中,复杂网络是体现各种网络系统关系的有效形式,比如我们最常见的合作网,互联网,万维网,生物网,交通运输网,社交网等。这些网 络都可以以图表的形式展现出来,点代表目标对象, 两点之间的边代表这些对象之间的联系。由于近年来进化算法在解决多目标优化的问题上已经取得了
被分区后社区的分值被定义为: C S= s c o r e ( S i ) ( 4 )
L a n c i c h i n e t t i介绍了一个模块 S的社区适应度
的概念,把模块 s内节点的内部度和外部度设为 ( . s )和I j} ( S )。那么该模块 S的社区适应度就可以 表示为: =
成功,因此,本文重点研究了基于多目标遗传算法 ( M u l i— t O b j e c i t v e G e n e i t c A l g o r i t h m,简称 M O G A )的 复杂网络社区结构查找问题,设计了一种多目标解决方案,该方案对两个目标函数进行了优化,通过在人工网络和真实网络的实验证实该方法能够有效划 分复杂网络的社区结构。
∑ 5丽
( 5 )
其中 a被称为解析度参数,是一个为正数的实值参数,用来控制社区的大小。对于一个固定的, 当I j} ( I s )= O时, P ( s )达到其最大值。
1 目标函数的
定义 在复杂网络社区结构划分的研究中,常用到以
2多目标遗传算法的复杂网络社区结 构划分 在各个领域都会有许多问题本身就具有多重目 标因素,特别是在网络划分的过程中,要达到两个相 互矛盾的目的。一个是将同一社区内节点之间的联系最大化,一个是社区之间联系的最小化。因此,社区划分问题不能简单地表述为了实现一个目的而尽量不去满足另一目标,将其描述为一个多目标分群问题更为合适。 研究的目标是把一个网络划分成一个个由点集{ s一, s }组成的,内部边数密集,相互边数稀疏的社区。为了达到这一目的,需要构造两个目标函数, 个将每个社区内部的联系数量最大化,另一个将社区之间的联系数量最小化。 一
下两个相关定义,一是 P i z z u t i提出的将社区里节点 人度最大化的质量标准,二是 l _ a n c i c h i n e t t i定义的 一
种将社区出度最小化的标准。
定义为节点 i与. s中其他节点的连接密度, 其表达式为:
面 I i n (| s ) 其中 l s I表示 s的集合。
( 1 )
s的 r次幂的平均值,表示为 ( s ),定义为: )= 一
( 2 )
个社区 S的体积被定义为 I s内部点之间 =
第一个目标函数采用了社区分值的概念来衡量 某个网络中社区划分的质量,社区的分值越高,分群的密度就越大。因此,最大化的第一个目标即为由
的总边数。即 ( 3 )
s的分值被定义为( S )= M( S )× t, 。一个网络公式( 4 )所得的该社区分值 c s。

一种基于多种群遗传算法的复杂网络社区结构发现新算法, 该算法无须预先知道社区...遗传算法 中图分类号: 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) 是一种解决实际复杂系统设计问题...
遗传算法在多目标优化圈中为是最优的解 决方法,而且...将所得的全部新个体都划分到同一个种群内,相当 于...在收敛上, 适应度高的个体将取代 原有的结构相似的...
热门文档