一种采用二级影响结构相似度的动态社团更新算法

摘要 目前各领域网络均呈现出规模巨大、结构复杂且动态变化的特点,传统的社团划分算法不能很好的适应这种动态复杂网络.为解决动态变化引起的社团划分变动的问题,在节点间二级影响结构相似度及相关定义的基础上提出了静态社团划分算法LBS算法,并进一步给出动态社团更新算法IULBS算法.LBS算法通过节点的连接偏好构造成链,进而由连接偏好链合并成社团结构.LBS算法在保证高质量社团划分的同时具有较低的时间复杂度,且在社团增量更新方面具有优势.在此基础上,IULBS算法在网络发生变化时检查变化相关节点,对不同类别节点采用相应的社团更新策略,实现动态复杂网络上的社团增量更新.通过实验,在多个真实网络和模拟网络上与经典算法进行对比,证实了本文算法的划分质量较高且时间效率更优