[科普中国]-增量式动态社区发现方法

在线社会网络数据量大、动态性强，快速准确发现隐含社区结构并得到隐结构演化信息是实际应用的迫切需求。针对算法效率问题，许多增量式动态社区发现算法被提出，该方法的假设前提仍然是平滑性假设，认为动态社区演化过程中，大部分的拓扑结构保持相对稳定，仅有小部分结构会变化，所以，在识别前一时刻社区结构的基础上，仅对改变的网络结构部分进行重计算，而其余结构保持不变，以此提升计算效率123。当前的增量策略主要分为基于物理学原理的增量策略和基于图特征的增量策略。

（1）基于物理学原理的增量策略将网络看成复杂物理世界．受牛顿万有引力定律的启发，Yang3等人将网络节点间关系分为吸引力和排斥力两种，通过迭代增量计算，使得所形成的社区内部吸引力越来越大，社区间的边上的排斥力越来越大，最终连接边断裂，形成分割的社团结构。

（2）基于图特征的增量式动态社区发现方法一般首先利用静态社区发现算法发现初始时间快照上的社区结构，然后辨识后续网络快照中结构变化的部分，对这小部分改变的结构进行计算，从而避免对全网络重新计算2。主要的增量策略有基于图分割特征的、基于谱特征的、基于矩阵分解等方法。

总之，增量式动态社区发现方法与基于概率生成模型的方法相比，计算性能要高，但这类算法在计算性能上的提高是以计算结果质量的部分降低为代价的。