基于多目标密母算法的复杂网络社团检测研究
发布时间：2020-11-07 19:53
随着科技的迅速发展,复杂网络已不知不觉地影响着人们的生活。例如,从有形的交通网络、通信网络、电力网络到无形的经济网络、信息网络、社交网络等。这些网络都可以抽象为图的形式表示,用节点表示对象,节点与节点的连接表示对象之间存在的某种关系。社团结构是复杂网络的一个重要属性,它具有社团内部连接紧密,外部连接稀疏的特点。发现复杂网络社团结构的特征,有助于分析网络行为、揭示网络中潜在规律。近年来,研究者提出了一系列的算法来发现复杂网络的社团结构。社团检测中常用的是优化方法,就是将社团检测问题转化成目标优化问题。由于现实生活中网络复杂,结构繁多,在社团检测中优化多个目标函数的方式,能更好的发现网络社团结构。因此本文采用多目标优化方式,结合局部搜索算子,构造出一种新的多目标密母算法。本文主要工作和创新如下:1、研究了复杂网络社团结构及多目标优化算法。对于社团结构紧密和稀疏的判定,研究者根据不同的准则对社团定义了同的衡量标准,如模块度、模块密度、社团分数等。结合了不同目标同时优化,有助于综合考虑社团的多个特征,本文重点研究了多目标算法,并分析了不同算法的特点。2、提出了一个基于多目标密母算法的社团检测算法。算法采用社团分数和模块度作为优化目标函数,利用均匀交叉和点变异操作进行进化,编码方案采用基于邻接点的编码方式,该编码方式不需要提前知道社团数目,方便用来处理实际中大多数不知道社团数目的网络。3、采用随机游走的种群初始化策略。随机游走的初始化方式,与传统的随机初始化相比,它能保证产生的每个个体都是安全个体。以马尔科夫转移概率为节点游走标准,不仅保证了个体的有效性,而且维护了种群的多样性。4、引入模拟退火操作算子作为局部搜索策略。模拟退火算法是一种启发式算法,其本身有较好的搜索能力。本文对模拟退火算法做了一些改进,用支配关系作为评判个体优劣的唯一标准,这样的调整有利于搜索优秀个体。在人工合成网络平台生成的网络和现实世界的实际网络中进行仿真实验,并与其他算法进行了对比分析,实验结果验证了本文算对社团检测的有效性。
【学位单位】：河南大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：O157.5;TP301.6
【部分图文】：
随机图模型是 ER 图，在不断的发展中 ER 图成为了复杂网络领域中分析网络结构种随机网络模型。1998 年，根据“六度分离”理论，复杂网络中的“小世界”被发小世界模型是对网络更深入的研究，这种模型可以发现网络中的点和边之间有着聚系和平均路径长度。1999 年，Barabasi 等人提出了无标度网络[38]理论，无标度网络上是一种无规则的网络。在现实网络中，大多数边所表示的关系都不是随机的，因出现几个节点的连接密度较高，大多数节点连接密度相对较低的情况，这符合马太。因此这种无规则符合马太定律的网络就被统称为无标度网络模型。随着对复杂网不断研究发现，它还具有社团结构这一重要特性。社团结构由多个“团”、“群”或”’构成，“团”’内部结构紧簇，“团”与“团”之间连接稀疏。它可以用拓扑结构来表示，以下是复杂网络四种特性网络的模型图。
随机图模型是 ER 图，在不断的发展中 ER 图成为了复杂网络领域中分析网络结构种随机网络模型。1998 年，根据“六度分离”理论，复杂网络中的“小世界”被发小世界模型是对网络更深入的研究，这种模型可以发现网络中的点和边之间有着聚系和平均路径长度。1999 年，Barabasi 等人提出了无标度网络[38]理论，无标度网络上是一种无规则的网络。在现实网络中，大多数边所表示的关系都不是随机的，因出现几个节点的连接密度较高，大多数节点连接密度相对较低的情况，这符合马太。因此这种无规则符合马太定律的网络就被统称为无标度网络模型。随着对复杂网不断研究发现，它还具有社团结构这一重要特性。社团结构由多个“团”、“群”或”’构成，“团”’内部结构紧簇，“团”与“团”之间连接稀疏。它可以用拓扑结构来表示，以下是复杂网络四种特性网络的模型图。
因此这种无规则符合马太定律的网络就被统称为无标度网络模型。随着对复杂网络的不断研究发现，它还具有社团结构这一重要特性。社团结构由多个“团”、“群”或“类”’构成，“团”’内部结构紧簇，“团”与“团”之间连接稀疏。它可以用拓扑结构模型来表示，以下是复杂网络四种特性网络的模型图。图 2-1 规则网络模型 图 2-2 ER 图网络模型
【参考文献】
本文编号：2874400
【学位单位】：河南大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：O157.5;TP301.6
【部分图文】：
随机图模型是 ER 图，在不断的发展中 ER 图成为了复杂网络领域中分析网络结构种随机网络模型。1998 年，根据“六度分离”理论，复杂网络中的“小世界”被发小世界模型是对网络更深入的研究，这种模型可以发现网络中的点和边之间有着聚系和平均路径长度。1999 年，Barabasi 等人提出了无标度网络[38]理论，无标度网络上是一种无规则的网络。在现实网络中，大多数边所表示的关系都不是随机的，因出现几个节点的连接密度较高，大多数节点连接密度相对较低的情况，这符合马太。因此这种无规则符合马太定律的网络就被统称为无标度网络模型。随着对复杂网不断研究发现，它还具有社团结构这一重要特性。社团结构由多个“团”、“群”或”’构成，“团”’内部结构紧簇，“团”与“团”之间连接稀疏。它可以用拓扑结构来表示，以下是复杂网络四种特性网络的模型图。
随机图模型是 ER 图，在不断的发展中 ER 图成为了复杂网络领域中分析网络结构种随机网络模型。1998 年，根据“六度分离”理论，复杂网络中的“小世界”被发小世界模型是对网络更深入的研究，这种模型可以发现网络中的点和边之间有着聚系和平均路径长度。1999 年，Barabasi 等人提出了无标度网络[38]理论，无标度网络上是一种无规则的网络。在现实网络中，大多数边所表示的关系都不是随机的，因出现几个节点的连接密度较高，大多数节点连接密度相对较低的情况，这符合马太。因此这种无规则符合马太定律的网络就被统称为无标度网络模型。随着对复杂网不断研究发现，它还具有社团结构这一重要特性。社团结构由多个“团”、“群”或”’构成，“团”’内部结构紧簇，“团”与“团”之间连接稀疏。它可以用拓扑结构来表示，以下是复杂网络四种特性网络的模型图。
因此这种无规则符合马太定律的网络就被统称为无标度网络模型。随着对复杂网络的不断研究发现，它还具有社团结构这一重要特性。社团结构由多个“团”、“群”或“类”’构成，“团”’内部结构紧簇，“团”与“团”之间连接稀疏。它可以用拓扑结构模型来表示，以下是复杂网络四种特性网络的模型图。图 2-1 规则网络模型 图 2-2 ER 图网络模型
【参考文献】
相关期刊论文 前3条
1 李金忠;夏洁武;曾小荟;曾劲涛;刘新明;冷明;孙凌宇;;多目标模拟退火算法及其应用研究进展[J];计算机工程与科学;2013年08期
2 张君;;从七桥问题想到的用欧拉图来解决计算机应用问题[J];内蒙古民族大学学报;2012年02期
3 张敏;罗文坚;王煦法;;一种基于正态分布交叉的ε-MOEA[J];软件学报;2009年02期
相关博士学位论文 前1条
1 左益;基于全局优化和局部学习的进化多目标优化算法[D];西安电子科技大学;2016年
相关硕士学位论文 前1条
1 侯田;基于多目标优化算法的网络社区检测方法研究[D];西安电子科技大学;2012年
本文编号：2874400
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/2874400.html
