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

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

第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。

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

第1页

你可能喜欢

热门文档

相关文档

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