论文部分内容阅读
对社区结构的研究能深入了解复杂网络,同时也能挖掘复杂网络潜藏功能。但随着信息发展,复杂网络规模越发庞大,网络的伸缩性使复杂网络结构变得模糊,这导致社区发现算法在处理具有模糊结构大规模复杂网络问题时难以达到满意的效果。本文针对现有社区发现算法在大规模复杂网络存在计算效率低下和在具有模糊结构的复杂网络中社区发现精度降低的问题,提出了两种改进方法。主要研究内容如下:(1)为了解决现有社区发现算法在大规模复杂网络社区发现中存在计算精度和计算效率偏低的问题,提出一种基于谱聚类的多目标社区发现算法(SMOEA)。首先,使用谱聚类算法处理编码后的复杂网络,借助谱聚类的子图划分特性充分利用节点和边的信息,提高多目标社区发现算法中初始种群的质量。其次,利用多目标社区发现算法寻找非支配解集,从而得到较优的解。在多目标粒子群算法的进化过程中采用一种网格约简的数据归减方法对种群进行约减,提高算法的计算效率,使其能够完成较大规模的复杂网络社区发现问题。在人工网络和9个真实网络上的实验结果表明,该算法在社区发现性能和计算复杂度方面,都要优于MRMOEA、RMOEA和MCMOEA三种代表性的基于多目标的社区发现算法。(2)为了解决现有社区发现算法在具有模糊结构的大规模复杂网络社区发现时存在性能降低的问题,提出了一种基于结构增强的极大团社区发现算法(MCSE)。算法先通过结构增强的方法,增加可能属于同一社区的节点间的链接,去除不同社区节点间的链接,使复杂网络的社区结构变得清晰。其次,使用极大团社区发现算法处理结构增强后的复杂网络,用于处理重叠社区发现问题。最后,通过将节点相似度和搜索极大团集合这两部分计算并行化处理,提高MCSE算法的计算效率,方便其处理大规模复杂网络。在人工网络和4个真实网络上的实验结果表明,该算法在社区发现性能和计算复杂度方面,都要优于CPM、EdgeBoost和MCMOEA三种不同类型的代表性社区发现算法。同时通过实验证明了并行算法的有效性。