基于进化计算的社区挖掘算法及其应用研究

发布时间：2017-07-14 19:04

  本文关键词：基于进化计算的社区挖掘算法及其应用研究

  更多相关文章： 复杂网络 社区挖掘 扩展模块度密度 进化算法 文化基因算法

【摘要】：生活中,可以用网络来表示大量的复杂系统,比如说,朋友关系网络,交通运输网络,因特网,电话线路网络,新陈代谢网络,食物链网络等。近些年来,复杂网络成为了一个研究热点,吸引了越来越多的国内外各个领域的研究人员的关注。在早期的研究中,发现复杂网络具有小世界特性和无标度特性,但在后续的研究中,研究人员还发现复杂网络还具有极其重要的社区结构特性,社区结构定义为:同一社区内的节点之间的连接比较紧密,不同社区之间的连接比较稀疏。挖掘复杂网络中的社区结构,我们可以更好的分析网络的结构,从而理解网络的功能。此外,还有利于我们发现网络中潜在的规律进而可以对网络的行为做出预测,故社区挖掘具有十分重要的意义以及广泛的应用前景。为了研究复杂网络,研究人员提出了许多社区挖掘算法,这些算法总的来说可以归为以下三类:基于图分割的方法,基于层次聚类的方法和基于模块度(modularity)优化的方法,在这三类方法中,研究人员比较关注的是基于模块度优化的方法。模块度是Newman和Girvan提出来的,它是一个用于衡量网络社区划分质量的目标函数。通常来说,得到的模块度值越大,划分得到的社区结构也会越明显。文化基因算法(Memetic algorithm)最近在进化计算领域里受到了很多研究人员的关注,它除了对种群的全局搜索还具有对个体的局部启发式搜索,这两者的结合使其在解决某些问题的搜索效率上要比传统的遗传算法高。利用文化基因算法的优点,将其应用于复杂网络社区挖掘中。本文所做的主要工作如下:(1)研究了使用基于模块度优化的方法挖掘出的社区结构会存在分辨率限制的问题,我们通过采用一个新的目标函数——扩展模块度密度(general modularity density)来解决这个问题,该目标函数可以通过调节里面的参数来解决分辨率限制问题。(2)在研究文化基因算法(Memetic algorithm)基本理论的基础上,提出了一种可应用于复杂网络社区挖掘的文化基因算法。我们将复杂网络社区挖掘问题看成是一个单目标优化问题,把模块度Q和扩展模块度密度作为目标函数,并采用文化基因算法MA-Net分别优化这两个目标,得到了基于MA-Net框架的两种社区挖掘算法:MA-Net(Q)和MA-Net()。接着,我们在人工合成网络和真实世界网络中进行了实验,实验表明,带有局部搜索策略的文化基因算法相比于传统的遗传算法具有收敛速度快,不容易陷入局部最优,而且挖掘出的网络社区准确度比传统遗传算法更高的优点。最后,通过与GN算法比较,验证了本文的算法是有效的。
【关键词】：复杂网络 社区挖掘 扩展模块度密度 进化算法 文化基因算法
【学位授予单位】：华南理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18;O157.5
【目录】：

• 摘要5-7
• Abstract7-11
• 第一章 绪论11-16
• 1.1 研究背景和意义11-13
• 1.2 国内外研究现状13-14
• 1.3 本文的主要工作及内容安排14-16
• 第二章 常见的几种复杂网络社区挖掘算法16-28
• 2.1 复杂网络概述16-20
• 2.1.1 复杂网络的图表示16-17
• 2.1.2 复杂网络的特性17-20
• 2.1.2.1 小世界特性17-18
• 2.1.2.2 无标度特性18
• 2.1.2.3 社区结构特性18-20
• 2.2 复杂网络社区挖掘常见的几种算法20-28
• 2.2.1 基于图分割的方法20-22
• 2.2.1.1 Kernighan-Lin算法20-21
• 2.2.1.2 基于Laplace矩阵的谱平分法21-22
• 2.2.2 基于层次聚类的方法22-25
• 2.2.2.1 分裂方法23-24
• 2.2.2.2 凝聚方法24-25
• 2.2.3 基于模块度优化的算法25-28
• 2.2.3.1 模块度的定义25-26
• 2.2.3.2 基于模块度优化的算法26-28
• 第三章 基于文化基因算法的复杂网络社区挖掘28-40
• 3.1 引言28
• 3.2 文化基因算法概述28-30
• 3.3 模块度的缺陷30-32
• 3.4 模块度密度的概念32-33
• 3.5 一种应用于复杂网络社区挖掘的文化基因算法33-40
• 第四章 算法验证与分析40-59
• 4.1 引言40
• 4.2 评价标准40-41
• 4.3 仿真实验及结果分析41-58
• 4.3.1 人工合成网络实验41-46
• 4.3.2 真实世界网络实验46-58
• 4.4 本章小结58-59
• 第五章 总结与展望59-62
• 5.1 总结59-60
• 5.2 展望60-62
• 参考文献62-67
• 攻读硕士学位期间取得的研究成果67-68
• 致谢68-69
• 附件69

【相似文献】

中国期刊全文数据库 前10条

1 蔚承建,何振亚;改进的进化计算及其应用[J];自动化学报;1998年02期

2 陆荣双,曾璐,杨文龙;模拟进化计算理论及设计方法[J];矿山机械;2005年02期

3 郝宁湘;进化计算及其哲学研究[J];自然辩证法研究;2003年11期

4 魏敏洁;一种进化计算的抽象机器模型[J];计算技术与自动化;1998年03期

5 刘健勤,魏敏洁;进化计算的可计算性[J];计算技术与自动化;1998年03期

6 刘健勤，魏敏洁，刘其兴，蔡自兴;基于信息论测度的进化计算策略[J];中南工业大学学报;1996年03期

7 袁丽华;黎明;李军华;;基于优良育种的进化计算[J];系统工程;2007年07期

8 韩泉叶;党建武;赵庶旭;;人类进化特征及模型研究[J];计算机工程与设计;2008年01期

9 侯广坤,李明;自动布局问题的进化计算算法[J];中山大学学报(自然科学版);2001年02期

10 刘进;;进化计算在计算机辅助概念设计中的应用[J];科技信息(科学教研);2007年32期

中国重要会议论文全文数据库 前5条

1 孙承意;王皖贞;贾鸿雁;;思维进化计算的产生与进展[A];2001年中国智能自动化会议论文集（上册）[C];2001年

2 柯益华;胡学姝;;油气田产量预报Г模型参数估计的进化计算[A];2001年中国智能自动化会议论文集（下册）[C];2001年

3 邵桂芳;李祖枢;陈桂强;;基于进化计算的控制结构设计方法[A];2007年中国智能自动化会议论文集[C];2007年

4 刘第楷;徐家云;李桂青;;进化计算理论在结构控制中的应用研究[A];第六届全国结构工程学术会议论文集（第一卷）[C];1997年

5 赵清杰;杨波;;基于进化计算的BP网权值训练算法及其应用探讨[A];1998年中国智能自动化学术会议论文集（下册）[C];1998年

中国博士学位论文全文数据库 前8条

1 杨海军;进化计算中的模式理论、涌现及应用研究[D];天津大学;2004年

2 陈得宝;进化计算中的若干问题及应用研究[D];南京理工大学;2008年

3 王帅强;基于进化计算的行为模型自动精化和排序学习方法的研究[D];山东大学;2009年

4 王志春;基于进化计算的复杂分类算法研究及应用[D];天津大学;2010年

5 薛明志;进化计算与小波分析若干问题研究[D];西安电子科技大学;2004年

6 季伟东;进化计算优化前向神经网络的学习方法研究[D];东北林业大学;2013年

7 陈昊;动态环境下进化计算的研究[D];南京航空航天大学;2011年

8 刘军万;微阵列基因表达数据双聚类的多目标进化计算技术研究[D];国防科学技术大学;2009年

中国硕士学位论文全文数据库 前10条

1 李佳家;基于进化计算的社区挖掘算法及其应用研究[D];华南理工大学;2016年

2 章洁;进化计算的研究及其在自适应滤波中的应用[D];电子科技大学;2005年

3 王丽爱;研究思维进化计算的多峰优化性能及研究算法参数对效率的影响[D];太原理工大学;2004年

4 彭伟民;基于线性变换的适应度函数及机器人进化计算研究[D];广东工业大学;2006年

5 王俊丽;思维进化计算——搜索算法的开发和算法性能的分析[D];太原理工大学;2003年

6 陈珂;进化计算技术在手机造型设计及评价中的应用研究[D];山东师范大学;2008年

7 弓剑军;并行思维进化计算的性能分析[D];太原理工大学;2004年

8 贾美丽;并行思维进化计算的实现[D];太原理工大学;2004年

9 陈伟;进化计算在优化问题中的应用[D];武汉理工大学;2010年

10 刘福敏;基于进化计算的动漫造型研究与实现[D];山东师范大学;2010年

，

本文编号：542246