一种社交网络的增量社区检测算法及实现优化

来源：计算机技术与发展杂志2018年第10期北京时间：

作者：王冰玉;吴振宇;沈苏彬

摘要：社区检测是社交网络中常用的分析手段,目的是发现网络中联系较为紧密的节点集群,提取集群,从而进一步探索集群隐含的信息。 现实中的社交网络随时间不断增大,传统的社区检测算法在不断增大的网络中运行会十分耗时,这是传统社区检测算法的一个极大弊端。 针对该问题,基于传统的 K-Clique 社区检测算法,提出一种增量 K-Clique 社区检测算法。 与传统 K-Clique 相比,增量 K-Clique 使用网络中新增的边和节点去更新已有的社区检测结果,而非在时间片更新时对整个网络重新进行社区检测,算法忽略极少部分的细节换取整体的高效性。 实验结果表明,增量社区检测算法较传统算法在执行效率上提高显著,且检测结果与传统 K-Clique 几乎吻合。

关键词：社交网络;社区检测;增量更新