摘要：科技的高速进展使人类社会大步迈入了网络时代,很多现实世界的复杂系统都可以表示为网络,如协作网,万维网,电力网,生物网和社会网络等。网络可以模型化为图,其中节点表示对象,边表示节点之间的连接。近年来,复杂网络逐渐受到了来自各个领域探讨者们越来越多的关注,例如物理学,数学,生物学,社会学等。除了小世界效应,无标度等网络属性外,社区结构是复杂网络中另外一个重要的网络属性。社区可以定性的定义为网络中节点的子集,其内部节点之间的链接比较紧密,而和网络中其它节点的链接相对稀疏。探讨复杂网络社区结构对于浅析网络的拓扑结构、理解网络的功能、发现网络中的隐藏规律以及预测网络的行为不仅具有十分重要的论述作用,而且具有广泛的运用前景。近年来,越来越多的社区检测算法被提了出来,这些算法大致可以分为三类：基于图分割的策略,基于层次聚类的策略和基于模块度(modularity)优化的策略,其中基于模块度优化的策略近年来得到了越来越多的关注。模块度函数是Newman和Girvan提出的用来评价网络社区划分质量的指标函数。一般来说,模块度值越大,对应的社区结构越显著。密母算法(Memetic algorithm)是近年来进化计算领域的一个探讨热点,它是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体,这种结合机制使其搜索效率在某些不足领域比传统遗传算法快几个数量级。本论文所做的主要工作,就是利用进化算法这些优点,将其运用于复杂网络社区检测不足。本论文所做的主要工作如下：(1)探讨了多目标优化和进化算法的基本论述,提出了一种基于分解多目标优化进化算法(MOEA/D)的复杂网络社区检测策略。在该策略中,我们把社区检测不足模型化为了一个两个目标的多目标优化不足,并利用多目标进化算法MOEA/D来优化这两个目标。(2)探讨了社区检测算法中传统模块度优化具有的分辨率限制不足,为了解决这个不足,我们利用了一个新的目标函数：扩展模块度密度(general modularity density),该目标函数是ratio association与ratio cut的凸组合,可以克服分辨率限制不足,也就是说通过调节里面的参数,我们可以以不同分辨率浅析网络,进而发现网络社区的层次结构。探讨了密母算法(memetic algorithm)的基本论述,在此基础上提出了一种复杂网络社区检测密母算法。该密母算法引入了局部搜索对策,克服了传统遗传算法收敛速度慢,容易陷入局部最优的缺点。同时,该算法将扩展模块度密度作为目标函数,可以以不同分辨率浅析网络,克服了传统模块度优化算法的分辨率限制不足。本论文得到国家863项目(批准号：2009AA12Z210)、教育部新世纪优秀人才支持计划(批准号：NCET-08-0811)、陕西省青年科技新星计划(批准号2010KJXX-03)和高校基本科研业务费重点项目(批准号：K50510020001)资助。关键词：复杂网络论文社区检测论文进化算法论文密母算法论文多目标优化论文
摘要3-5
Abstract5-9
第一章 绪论9-19
1.1 引言9-10
1.2 复杂网络的基本概念10-16
1.2.1 复杂网络的图表示10-11
1.2.2 复杂网络的特性11-14
1.2.2.1 小世界特性11
1.2.2.2 无标度特性11-12
1.2.2.3 社区结构特性12-14
1.2.3 社区检测探讨作用与探讨近况14-16
1.2.3.1 探讨作用14-15
1.2.3.2 探讨近况15-16
1.3 本论文的内容安排16-19
第二章 复杂网络社区检测的几种常见算法19-25
2.1 基于图分割的策略19-20
2.1.1 Kernighan-Lin算法19
2.1.2 谱平分法19-20
2.2 基于层次聚类的策略20-23
2.2.1 分裂策略21-22
2.2.2 凝聚策略22-23
2.3 基于模块度优化的算法23-25
2.3.1 模块度的定义23-24
2.3.2 基于模块度优化的算法24-25
第三章 基于分解多目标优化进化算法的复杂网络社区检测25-37
3.1引言25
3.2 多目标优化25-26
3.3 基于分解的多目标进化算法26-27
3.4 基于MOEA/D的复杂网络社区检测算法27-37
3.4.1 目标函数27-28
3.4.2 编码方式28-30
3.4.3 种群的初始化30
3.4.4 交叉和变异30
3.4.5 MOEA/D-Net算法概述30-31
3.4.6 实验浅析31-36
3.4.6.1 人工合成网络32-33
3.4.6.2 真实世界网络33-36
3.4.7 本章小节36-37
第四章 基于密母算法的复杂网络社区检测37-57
4.1 引言37
4.2 密母算法概述37-39
4.3 模块度的缺陷39-40
4.4 模块度密度的概念40-41
4.5 一种用于复杂网络社区检测的密母算法41-57
4.5.1 编码方式42
4.5.2 种群的初始化42-43
4.5.3 交叉和变异43-44
4.5.4 局部搜索对策44-45
4.5.5 参数设置45-46
4.5.6 实验浅析46-54
4.5.6.1 人工合成网络46-48
4.5.6.2 真实世界网络48-54
4.5.7 本章小节54-57
第五章 总结与展望57-59
5.1 总结57-58
5.2 展望58-59
致谢59-61
本站原创