学位论文 > 优秀研究生学位论文题录展示

基于单亲遗传算法的复杂网络社区划分问题研究

作　者: 智源
导　师: 行飞
学　校: 内蒙古大学
专　业: 计算数学
关键词: 复杂网络 社区结构 单亲遗传算法 寻优算子
分类号: O157.5
类　型: 硕士论文
年　份: 2011年
下　载: 51次
引　用: 2次
阅　读: 论文下载
 

内容摘要


复杂网络的研究自20世纪末逐渐兴起以来,正迅速地渗透到各个领域的研究中去,引起了数学、物理、计算机、社会学等许多领域科研工作者的广泛关注。社区结构的探测问题是复杂网络研究的一个重要分支,目前逐渐成为了复杂网络研究的一个热点。遗传算法(GA)是由美国密执安大学的Ho1land教授于1969年提出的。本文结合了遗传算法的思想,针对复杂网络社区划分问题的特点,提出采用单亲遗传算法求解这一问题,设计了新的编码方案和相应的遗传操作。复杂网络社区结构的探测是研究社区结构的基础,目前,关于社区结构的概念以及社区结构划分结果的优劣都没有一个被广泛认可的统一的标准。本文首先对复杂网络的研究背景作了介绍,并对现有社区结构的有关概念和一些衡量社区划分优劣的标准作了较为全面的综述。其次,介绍了一些求解复杂网络社区结构的较有代表性的方法。最后,结合部分有关复杂网络社区结构的新的研究成果,提出了求解这一问题的单亲遗传算法,并利用经典例子对算法进行了试算,验证了算法的有效性,分析比较了目前几种主要的评价指标作为适应度函数的结果。本文的创新工作主要有：(1)使用单亲遗传算法求解复杂网络社区划分问题,构造了新的适应度函数QF、编码方式、变异算子。(2)构造了三个寻优算子,试算结果说明效果明显。(3)设计了种群初始化方法,一定程度上提高了算法的效率(4)编制程序验证了算法的有效性,对常用的模块度函数Q、模块密度函数D、模块内外连接率差值函数C和比率函数Q进行了评价。

全文目录


摘要  4-6
ABSTRACT  6-11
第一章 绪论  11-15
  1.1 引言  11
  1.2 复杂网络社区划分问题的提出背景,研究意义及研究现状  11-13
  1.3 本文的内容及文章结构  13-15
    1.3.1 本文主要内容  13
    1.3.2 文章结构  13
    1.3.3 本文创新工作  13-15
第二章 复杂网络社区划分问题概述  15-32
  2.1 复杂网络的特性及基本量  15-19
    2.1.1 复杂网络复杂性的体现  15
    2.1.2 描述网络拓扑性质的基本量介绍  15-16
    2.1.3 介绍几种常见的网络演化模型  16-19
  2.2 社区结构的定义  19-22
    2.2.1 基于连接频数的定义  20
    2.2.2 强社区和弱社区的定义  20-21
    2.2.3 LS集  21-22
    2.2.4 派系  22
  2.3 复杂网络社区划分的评价指标  22-25
    2.3.1 模块度函数Q  22-24
    2.3.2 模块密度D  24
    2.3.3 社区度C  24
    2.3.4 一种改进的模块度函数Q  24-25
  2.4 复杂网络社区划分的算法概述  25-30
    2.4.1 基于优化的算法  25-26
    2.4.2 启发式方法  26-27
    2.4.3 其他复杂网络社区结构发现方法  27-30
  2.5 复杂网络社区划分问题的数学描述  30-32
    2.5.1 一些相关定义  30-31
    2.5.2 复杂网络划分问题的数学描述  31-32
第三章 单亲遗传算法简介  32-44
  3.1 遗传算法简介  32-34
    3.1.1 遗传算法的基本思想  32-33
    3.1.2 遗传算法的特点  33-34
  3.2 遗传算法的操作设计及基本流程  34-42
    3.2.1 遗传算法的基本概念和术语  34-35
    3.2.2 遗传算法的操作设计  35-40
    3.2.3 算法的基本结构  40-42
  3.3 单亲遗传算法  42-44
    3.3.1 单亲遗传算法简介  42-43
    3.3.2 单亲遗传算法的主要特点及应用  43-44
第四章 基于遗传算法的复杂网络社区结构发现  44-60
  4.1 算法设计  44-58
    4.1.1 算法流程  44-46
    4.1.2 适应度函数  46-48
    4.1.3 编码方案  48-51
    4.1.4 初始化方法  51-54
    4.1.5 遗传算子  54-56
    4.1.6 寻优算子  56-58
  4.2 算法实现  58-60
    4.2.1 群体规模  58
    4.2.2 变异概率  58-60
第五章 数值实验及结果分析  60-68
  5.1 两个较特殊的网络  60-62
    5.1.1 实验一  60-61
    5.1.2 实验二  61-62
  5.2 ZACHARY KARATE CLUB网络  62-66
    5.2.1 实验一  62-65
    5.2.2 实验二  65-66
  5.3 COLLEGE FOOTBALL NETWORK网络  66-68
第六章 结论  68-69
参考文献  69-74
致谢  74-75
攻读硕士学位期间发表的学术论文  75

相似论文

  1. 复杂网络的建模分析及其应用,O157.5
  2. 基于复杂网络特征的SNS社交网站传播特征研究,G206
  3. 电网分析计算中的可视化技术研究,TM769
  4. 基于复杂网络的供应链建模与网络效率研究,O157.5
  5. 复杂网络可靠性评价指标研究,O157.5
  6. 基于软件影响网络的软件度量研究,TP311.52
  7. 遇袭有向复杂网络抗毁性修复策略研究,O157.5
  8. 乌鲁木齐市公交网络结构特性分析研究,U491.17
  9. 基于车辆出行特征的交通网络评价方法研究,U491.13
  10. 面向企业集群的产品网络构建及集群特性研究,F273.2;F224
  11. 山东半岛蓝色经济区海洋产业复杂网络演化研究,F127
  12. 随机环境下风险模型破产概率及复杂网络中的随机过程,F840
  13. 公共交通骨干网络模式研究,U491.17
  14. 天津市公共交通网络复杂性研究,U491.17
  15. 面向复杂产品的配置设计方案评价,TH122
  16. 基于复杂网络的林业应用系统功能结构模型研究,S757.1
  17. 虚拟社区中兴趣传播模型的研究,TP393.094
  18. 维基百科的网络结构及可信分析,TP393.02
  19. 基于不同机制复杂网络结构的科学论文甄别方法研究,G311
  20. 基于复杂网络的知识价值链建模及应用研究,F272
  21. 基于复杂网络的海洋排污权配置及其交易机制研究,F205;X32

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学（组合学） > 图论
© 2012 www.xueweilunwen.com