基于改进阈值与遗传算法的社区发现方法研究

论文摘要

复杂网络在对现实中诸多系统的描述方面有着突出贡献,诸如物流、互联网等等现实系统都可以使用复杂网络来进行描述。复杂网络中的一个重要的特征为社区结构特征,具体表现为:在同一社区内,结点间边较为稠密;在不同社区之间边则较为稀疏。社区发现方法可以有效探测网络内部结构,发现不同网络中潜在的规律,这对于我们理解网络功能,预测网络行为有着重要意义和价值。目前,社区发现算法大致可分为以下三种:基于优化的算法、启发式算法及其他算法。但是,这些算法或多或少的存在着运行速度不够快、精确度较低等问题。为了解决上述问题,本文针对社区发现方法,主要进行如下工作:1、针对传统的社区发现算法时间复杂度高的问题,本文将传统阈值与结构相似度的概念结合,提出一种新的社区发现算法STCA。该算法主要思想如下:(1)对于给定阈值k,计算网络两点间的结构相似度作为这两点间的边权值。(2)删除结构相似度小于k的边,并重复以上步骤(1)(2),直到没有边可以删除,计算此时社区对应的模块函数Q的值;(3)将阈值增加一定量,并重复上述过程;(4)取最大模块度对应社区为最终划分结果。通过大量的实验测试,结果表明:本文提出的STCA算法可以在确保划分精度的前提下,提升算法的运行速度。2、针对传统遗传算法在社区发现方面生成初始种群精确度较低的问题,本文提出一种新的基于改进遗传算法的社区发现方法SSGA。该方法主要思想为:将传统的遗传算法轮盘赌选择法与社区网路中结构相似度的概念结合,使染色体上的每一个基因都趋于选择结构相似度比较大的邻居结点,从而大大提升初始种群的划分精度。本算法在人工基准网络数据与真实世界网络数据下进行了实验。结果表明,本文提出的SSGA算法在提升初始种群划分精度的同时,整体划分精度也有所提升,具有更高的整体划分性能。

论文目录

• 中文摘要
• Abstract
• 1 绪论
•   1.1 研究背景及意义
•   1.2 国内外研究现状
•     1.2.1 启发式算法
•     1.2.2 基于优化的算法
•     1.2.3 其他算法
•   1.3 研究内容
•   1.4 组织结构
• 2 社区发现概述
•   2.1 基础知识
•     2.1.1 复杂网络表示形式
•     2.1.2 复杂网络统计特征
•     2.1.3 复杂网络模型
•   2.2 社区结构定义
•   2.3 经典数据集
•     2.3.1 跆拳道俱乐部
•     2.3.2 海豚社区网络
•     2.3.3 足球俱乐部网络
•   2.4 小结
• 3 基于结构相似度和阈值的社区发现方法
•   3.1 概述
•   3.2 算法思想
•     3.2.1 模块性评价函数
•     3.2.2 结构相似度
•     3.2.3 算法STCA
•     3.2.4 时间复杂度分析
•   3.3 实验结果及分析
•     3.3.1 人工基准网络
•     3.3.2 真实世界网络
•   3.4 小结
• 4 基于结构相似度和遗传算法的社区发现方法
•   4.1 概述
•   4.2 算法SSGA形式化描述
•     4.2.1 模块性评价函数
•     4.2.2 编码方式
•     4.2.3 初始种群的生成
•     4.2.4 选择和交叉算子
•     4.2.5 变异算子
•     4.2.6 SSGA算法的步骤
•   4.3 实验分析
•     4.3.1 人工基准网络
•     4.3.2 真实世界网络
•   4.4 小结
• 5 总结与展望
•   5.1 总结
•   5.2 展望
• 附录
•   附录1
• 参考文献
• 致谢

文章来源

类型: 硕士论文

作者: 席梦龙

导师: 王丽珍

关键词: 社区发现,阈值,遗传算法,结构相似度

来源: 云南大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,自动化技术

单位: 云南大学

分类号: TP18;O157.5

总页数: 80

文件大小: 7361K

下载量: 13