考虑社区结构稳定度的增量社区并行发现算法

Incremental Parallel Community Detection Algorithm Considering the Stability of Community Structure

传统的动态网络社区发现方法是对每个时刻的网络分别通过静态算法进行社区检测,进而分析各个社区之间的关系,可能导致较高的时间开销.根据相邻时刻之间的拓扑结构变化不大的特点,提出一种考虑社区结构稳定度和增量相关节点相结合进行社区发现的方法 IPCSCDA(Incremental Parallel Community Detection Algorithm Considering The Stability Of Community Structure).算法以前一个时刻得到的社区结构为基础,通过基于Jaccard系数的社区归属判定条件来调整增量相关节点的社区归属,同时考虑每个社区的结构稳定度,以发现动态网络社区.通过增量方法分析相邻时刻网络的变化,避免了对整个网络进行重新划分,从而大大减少了算法的时间开销.在人工数据集和真实数据集上的实验表明,提出的算法具有良好的动态社区发现能力.

One of the traditional ways for detecting dynamic communities is to find the communities at each interval through the static community detection algorithms. However,it usually leads to high computation complexity. In this paper,a novel algorithm considering the stability of community structure with the strategy of incremental related vertices with the name IPCSCDA（ Incremental Parallel Community Detection Algorithm Considering The Stability Of Community Structure） is proposed. Depending on the communities found at the previous interval,the new algorithm uses Jaccard index to adjust the incremental related vertices belong to while considering the stability of community structures at the same time. The repartitioning of the whole network can be avoided by incrementally analyzing the variation of the networks,so that the time cost can be greatly reduced. Experiments on artificial and real datasets show that the proposed algorithm is capable of discovering dynamic communities effectively.