论文部分内容阅读
近年来,随着社会网络研究的兴起,对社会网络中的社区结构进行检测,逐渐成为了研究的热点。社区结构是社会网络最重要的拓扑结构属性之一,它揭示了社会网络的隐藏规律和行为特征。而现实世界中的社会网络多数都是动态网络,动态网络的社区结构会随着时间不断演化,因此它比静态网络社区检测更富有挑战性。目前对于动态网络社区检测问题,进行的研究还只是处于起步阶段,所提出的方法也不多见。针对于传统的方法不能够自动识别社区个数,而且需要预先设定权重参数来控制对两个代价函数的不同侧重,本文基于多目标免疫算法,提出了三种动态网络社区检测算法来解决动态网络社区检测问题。本文的主要工作如下:(1)以基于人工免疫系统的的多目标优化算法,即非支配邻域免疫算法(NNIA)为基础,提出了一种新的动态网络社区检测算法。该算法以模块度和规范化的互信息熵作为优化的目标函数,用社团划分得分(CS)作为每个时刻最优解的选择标准,这样就可以克服传统算法的缺点,新算法不仅可以找到相对较好的解,发现每个时刻比较准确的社区结构,而且得到的结果也相对比较稳定。(2)针对非支配邻域免疫算法对稀疏区域的个体搜索不完善的缺点,将拉马克学习策略引入到该算法中,提出了基于拉马克多目标免疫算法的动态网络社区检测算法。通过在非支配种群的产生阶段加入局部搜索策略,来加强原算法的全局寻优能力和快速收敛能力。通过仿真试验,证明了加入局部搜索能进一步提高算法的性能。(3)为了克服基于邻接点编码方式的缺陷以及局部搜索方向不可控,我们提出了种新的基于多目标密母算法的动态社区检测算法。该算法采用直接编码的方式,使用简单的启发式搜索对初始种群进行预处理,而且根据直接编码方式的特点,采用双路交叉与单点变异方式来替代原算法中的重组和超变异操作,同时为了提高算法的性能,我们加入了基于多目标密母算法的局部搜索策略,而在选择最优解时,我们使用了模块密度作为选择标准来弥补模块度函数的不足。通过一系列的实验,证明了新的算法不仅可以准确的检测出每个时刻的社区结构,而且可以追踪到详细的社区演化特征,同时,该算法的稳定性也相对较高。