IC：动态社会关系网络社区结构的增量识别算法

摘要

社会关系网络(SNS)中社区结构的识别有助于得出有意义的个体间活动模式和社会发展规律，传统的静态SNS社区结构识别的方法不能发现SNS的变化规律，而最近受到广泛关注的动态SNS社区识别方法普遍存在可扩展性差的缺点.描述了动态SNS的数学模型，并在此基础上提出了动态SNS中发现社区结构的增量式新方法.提出方法利用动态网络时间局部性即相邻采样时刻网络变化不大的特点，通过增量分析避免对整个网络中的个体全部重新划分，达到较高的算法效率．分析和实验结果表明，效率高于现有方法，在大规模网络上(105结点量级)效率提升在一个数量级以上，发现的社区结构很好的反映出社会关系网络的本质结构.