基于复杂网络的社团结构分析算法研究

发布时间：2017-12-17 22:06

  本文关键词：基于复杂网络的社团结构分析算法研究

  更多相关文章： 复杂网络 社区结构 蚁群聚类 关键节点

【摘要】：社区结构的研究发现对于理解复杂网络的功能,分析节点间的关系,对复杂网络拓扑结构的理解和对网络行为的预测等有着重要的意义。目前许多基于复杂网络的社区结构的分析算法已经被提出来,然而这些算法也存在着许多不足。如需要先验条件、聚类精度低、完成大规模的社区结构发现的时间复杂度高等问题都是需要进一步研究的问题。目前针对复杂网络社区结构的发现问题,采用群体智能算法去研究已经成为热门研究课题之一。蚁群聚类算法模型就是一种模拟蚂蚁运动过程的群集智能算法。它是对蚂蚁们在现实生活中的清理巢穴和寻找食物等行为过程的模拟。它具有动态性、自组织、高效性、聚类质量较高、不需要先验条件等特点。本文在国内外学者对复杂网络中社区结构的发现和蚁群聚类算法的研究经验的基础之上主要做了如下工作：(1)对于中小型网络,采用节点相似度机制改进适应度局部感知函数和信息素扩散模型。开始时在二维网格上随机的放置蚂蚁,在聚类时蚂蚁通过感知周围环境的相似度和适应度,决定是移动还是停留。网格上每一代的移动都会形成一个聚类解。同时利用信息素扩散模型,根据聚类解更新节点信息素,同时改进信息素局部更新模型,使信息素能更好的引导蚂蚁聚类行为。同时根据蚂蚁与周围环境的适应度来决定蚂蚁的移动步长。算法不断迭代过程中蚂蚁不断寻找合适位置最终社区结构便在网格上呈现出来。在通用数集上,通过与一些经典算法的比较发现,此算法具有较好的聚类效果。(2)对于大型网络,复杂网络的规模大,聚类方法速度慢的问题,利用网络中关键节点对网络进行抽样。降低问题的规模。将问题转换问小规模网络。再利用上面的工作对样本节点进行聚类。同时在算法中利用了标签传播思想。最后根据剩余节点和社区的相似度,将节点分配到社区中。利用模块度函数为指标,修正聚类结构即可。在实验中发现,该方法能提高社区结构发现速度并能够得到较好质量的聚类结果。
【学位授予单位】：大连海事大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5;TP18

【参考文献】

中国期刊全文数据库 前1条

1 ;Research on Community Structure in Bus Transport Networks[J];Communications in Theoretical Physics;2009年12期

，

本文编号：1301718