应对显著变化的动态社区检测方法

Dynamic community detection method for coping with significant changes

现实中的网络总是不断变化,网络形态和连接关系也在随着时间推移而不断演变,在动态网络中发现社区的变化一直是个重要课题。当这种变化较为显著时,将导致社区检测算法难以有效利用前一个网络快照中有价值的信息,从而导致下一个时间步的负迁移。为解决算法无法较好适应网络突变问题,提出了一个基于遗传进化思想和高阶知识转移策略的动态社区检测算法。首先利用相邻快照的邻接矩阵相似度确定使用一阶或高阶信息,然后利用蛛网模型进行种群初始化,再通过非支配排序遗传算法NSGA-Ⅱ迭代出位于Pareto前沿的多目标最优解,并设计了新的基因交叉方式以提高种群多样性。最后通过在多个真实数据集及模拟数据集上的实验结果表明,与现有算法相比,该算法在发生网络剧变时能获得时间平滑性更高的社区检测结果,同时也能保持良好的社区模块化程度。

In real-world networks,the structure and connections are constantly evolving over time.Detecting community changes within dynamic networks has always been an important research topic.When such changes are significant,it leads to difficulty for community detection algorithms to effectively utilize valuable information from the previous network snapshot,resulting in negative transfer in the next time step.To address the issue of poor algorithm adaptability to network mutations,this paper proposed a dynamic community detection algorithm based on genetic evolution ideas and higher-order knowledge transfer strategies.Firstly,it used the adjacency matrix similarity of adjacent snapshots to determine the use of first-order or higher-order information.Then,it employed the spider Web model for population initialization,followed by the non-dominated sorting genetic algorithm NSGA-Ⅱto iteratively obtain multi-objective optimal solutions on the Pareto front.It designed a novel gene crossover method to enhance population diversity.Finally,experimental results on multiple real and simulated datasets demonstrate that,compared to existing algorithms,the proposed method achieves higher temporal smoothness in community detection results during network upheavals while maintaining a good community modularity level.