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

摘要

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

目录

文摘

英文文摘

第一章 绪论

1.1 引言

1.2 复杂网络社区划分问题的提出背景,研究意义及研究现状

1.3 本文的内容及文章结构

1.3.1 本文主要内容

1.3.2 文章结构

1.3.3 本文创新工作

第二章 复杂网络社区划分问题概述

2.1 复杂网络的特性及基本量

2.1.1 复杂网络复杂性的体现

2.1.2 描述网络拓扑性质的基本量介绍

2.1.3 介绍几种常见的网络演化模型

2.2 社区结构的定义

2.2.1 基于连接频数的定义

2.2.2 强社区和弱社区的定义

2.2.3 LS集

2.2.4 派系

2.3 复杂网络社区划分的评价指标

2.3.1 模块度函数Q

2.3.2 模块密度D

2.3.3 社区度C

2.3.4 一种改进的模块度函数Q

2.4 复杂网络社区划分的算法概述

2..4.1基于优化的算法

2.4.2 启发式方法

2.4.3 其他复杂网络社区结构发现方法

2.5 复杂网络社区划分问题的数学描述

2.5.1 一些相关定义

2.5.2 复杂网络划分问题的数学描述

第三章 单亲遗传算法简介

3.1 遗传算法简介

3.1.1 遗传算法的基本思想[64]

3.1.2 遗传算法的特点[64]

3.2 遗传算法的操作设计及基本流程

3.2.1 遗传算法的基本概念和术语

3.2.2 遗传算法的操作设计

3.2.3 算法的基本结构

3.2 单亲遗传算法

3.2.1 单亲遗传算法简介

3.2.2 单亲遗传算法的主要特点及应用

第四章 基于遗传算法的复杂网络社区结构发现

4.1 算法设计

4.1.1 算法流程

4.1.2 适应度函数

4.1.3 编码方案

4.1.4 初始化方法

4.1.5 遗传算子

4.1.6 寻优算子

4.2 算法实现

4.2.4 群体规模

4.2.2 变异概率

第五章 数值实验及结果分析

5.1 两个较特殊的网络

5.1.1 实验一

5.1.2 实验二

5.2 ZACHARY KARATE CLUB网络[61]

5.2.1 实验一

5.2.2 实验二

5.3 COLLEGE FOOTBALL NETWORK网络[62]

第六章 结论

参考文献:

致谢

攻读硕士学位期间发表的学术论文