一种基于多维遗传算法的重叠社区发现方法_王琦1
需积分: 0 109 浏览量
2022-08-03
16:06:13
上传
评论
收藏 312KB PDF 举报
收
稿日期
： 2015-08-25；
修回日期
： 2015-11-09
基金项目
：
国家自然科学基金青年基金资助项目
（ 61401195）
；
南京工程学院校级青年基
金
资助项目
（ QKJB201408）
作者简介
：
王琦
（ 1980-）
，
女
，
讲
师
，
博士研究生
，
主要研究方向为数据挖掘
、
社交网络分析研究等
（ wangq@ njit ． edu． cn）
；
温
志平
（ 1975-）
，
女
，
副
教
授
，
硕士
，
主要研究方向为数据挖掘
、
社交网络分析研究等
．
一种基于多维遗传算法的重叠社区发现方法
*
王 琦
1，2
，
温
志平
1
（ 1．
南京工程学院
计算机工程学院
，
南京
211167； 2．
南京大学 计算机科学与技术系
，
南京
210093）
摘 要
：
社区结构的发现是社交网络分析研究的重要内容
。
与传统的重叠社区不同
，
最近的研究表明某些真实
网络中在社区重叠部分要比社区内部节点间的连接更加密集
，
而现有的算法没有考虑此类社区结构
。
基于遗传
算法
，
提出了一种新颖的方法来发现此类社区划分
。
为了刻画节点属于多个社区的重叠现象
，
首次将多维染色
体和均匀块交叉算子引入到社区发现算法中
。
通过实验证明
，
提出的算法可以很好地发现社交网络中重叠和非
重叠的社区结构
。
关键词
：
社团发现
；
重叠社团
；
多维染色体
；
从属网络
中图分类号
： TP393
文献标志码
： A
文章编号
： 1001-3695（ 2016） 12-3543-04
doi： 10． 3969 /j． issn． 1001-3695． 2016． 12． 006
Multidimensional genetic algorithm for overlapping c ommunity detection
Wang Qi
1，2
，Wen Zhiping
1
（ 1． College of Computer Engineering，Nanjing Institute of Technology，Nanjing 211167，China； 2． Dept． of Computer Science ＆ Technology，
Nanjing University，Nanjing 210093，China）
Abstract： Community structure identification is an important content of social network analysis． In contrast to traditi o na l defi-
nitions of overlapping network community，recent studies have found that overlaps between communities are more densely con-
nected than the non-overlapping parts whic h are common in re a l social structures，and existing methods do not consider this
kind of community structure． This paper developed an innovative algorithm for detecting dense overlapping communities based
on genetic algorithm ． In order to charact e r i ze the real situation of the nodes belonging to multiple communities，it first intro-
duced a new multidimensional chromosome and block-uniform crossover in community discovery algorithms． It performed several
experimental studies to demonstrate that this method successfully captures overlapping as well as non-overlapping communities．
Key words： community detection； overlapping community； multidimensional chromosome； affiliation networks
现
在有大量的社交网络如
Facebook、Twitter
和新浪微博
等
。
在社交网络中
，
人们可以通过社区相互联系和交换信息来
展示个人生活
。
社区结构的发现有助于捕获和跟踪网络的拓
扑结构
、
揭示复杂系统内在的功能特性
、
预测个体关系和行为
的演化趋势
，
具有很强的应用价值
。
社区发现算法的研究得到
了研究人员的广泛关注
，
很多经典算法如模块度
、
介数等被提
出来用于有效快速地挖掘不同规模的社区
［1 ～ 3］
。
在很多社交网络中
，
一个人往往同时属于多个群体或参与
多
个话题
，
这就提出了重叠社区发现的问题
。
现在的社区发现
算法都隐含一个共同的假设
，
认为社区是网络节点集合的若干
子集
，
每个子集内部节点之间的连接相对紧密
，
而不同子集节
点之间的连接相对稀疏
［4］
。
换
句话说
，
这意味着一对节点同
时属于的社区越多
，
它们之间相连的可能性就越低
。
然而最近
Yang
等人
［5］
通
过对某些真实社区
（ ground-truth communities）
（
图
1）
的研究发现
，
一些社交网络中
，
节点之间在社区间重叠
部分的连接往往比社区内部的连接更加紧密
［6］
。
这
一研究结
果与现有社区的认识形成了鲜明的对比
，
目前已有的众多社区
发现算法均没有考虑此种结构的社区
，
它们在算法中要么将社
区重叠部分分成单独的一个聚类
，
要么将重叠部分的所有社区
合并成一个更大的社区
，
因而无法正确识别出这类重叠社区
。
Yang
等人
［7］
在从属网络模型
［8］
的基础上提出了一个
新的重叠
社区发现方法来发现此类社区结构
。
但是该算法中忽略了社
区大小对于网络结构的影响
，
而社区的规模又是从属网络的一
个重要属性
；
此外在其方法中需要列举不同的社区结构来找到
最合适的社区划分
。
为此
，
本文引入多维遗传算法来研究社区
结构
，
通过遗传进化过程对网络的最佳社区结构进行搜索
，
搜
索中综合考虑了个体吸引和社区规模的影响
。
图
1
重叠区域中
节点间连接密集的网络
1
相
关工作
社区反映了网络中个体行为的局部聚集特征
，
在
社交网络
中存在大量的隐性或显性社区
，
社区结构的研究成为近年来社
交网络研究的一个趋势
［1 ～ 4］
。
第
33
卷
第
12
期
2016
年
12
月
计算机应用研究
Application Ｒesearch of Computers
Vol. 33 No. 12
Dec． 2016
评论0