基于进化和局部优先的动态网络社团检测算法

摘要

作为一种对现实中大规模复杂系统的抽象工具，复杂网络得到了广泛的关注。现实世界中的复杂系统往往随时间缓慢变化，动态网络作为刻画复杂网络动态性的有效手段，具有很高的研究价值。目前对复杂网络进行分析的方法主要集中在社团检测上。对动态网络进行社团检测，有助于人们认识网络特性以及发展趋势，具有重要的理论和实际意义。
　　传统的动态网络社团检测算法通常在每个时刻对网络快照进行划分，试图找到“模块性”较高的社团结构，然后分析社团之间的关系。这种方法忽视了动态网络的时序性，难以发现社团结构的演化性。同时，传统的社团检测算法通常以一种“自顶向下”的视角对网络进行划分，这种方法通常难以发现小于一定规模的小社团。然而，现实中这些小社团可能具有一些实际的功能和意义。另一方面，现有的动态社团检测算法通常不能检测到社团的重叠结构，而重叠性作为社团结构的重要特征，很有研究的必要。综上所述，本文提出了一种基于进化和局部优先的动态社团检测算法，对每个节点抽取其EgoMinusEgo子图，在其上使用标签传播算法进行局部社团划分，之后以一种“自底向上”的视角不断合并局部社团直至得到网络的一组划分。在执行合并策略时，引入了覆盖率和分布率两个指标分别代表当前社团拓扑结构与历史信息两个方面，使用进化聚类框架来平衡这两个指标，从而使得到的社团具有时序演化性。
　　本文在真实网络数据上对提出的动态网络社团检测方法进行了实验。实验结果表明本文提出的基于进化和局部优先的社团检测算法能够有效地检测到社团的重叠结构，同时能够检测到具有实际意义的小规模社团结构。而与其他局部优先的算法相比时，本文的算法得到的社团结构更好，同时在相邻时刻间具有更紧密的联系。