一种混合的动态社区发现算法  

Mixed Dynamic Community Discovery Algorithm

作　　者：白伊史 翟海霞[1] 刘园 BAI Yi-shi;ZHAI Hai-xia;LIU Yuan(College of Computer Science and Technology,Henan Polytechnic University,Jiaozuo 454003,China)

机构地区：[1]河南理工大学计算机科学与技术学院,河南焦作454003

出　　处：《小型微型计算机系统》2023年第4期773-778,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金面上项目(61872126)资助;河南省重点科技攻关项目(192102210123)资助。

摘　　要：针对增量式动态社区发现算法存在的误差累积问题和计算复杂度受网络演化程度影响的问题,本文结合标签传播算法和模块度优化算法提出了一种混合的动态社区发现算法.该算法将网络的演变情况分为产生增量较多的剧烈演变和产生增量相对少的非剧烈演变2种情况.为了减少增量处理,对于剧烈演变,该方法将对应的网络快照看做一个完整网络,采用静态方法划分社区.对于非剧烈演变的情况,则采用增量的方式划分社区.在社区划分过程中,同时采用了基于模块度优化的Louvain算法和标签传播算法进行社区结构调整.在人工数据集和真实数据集上的实验验证了本算法的正确性和有效性.Focusing on the problem of error accumulation and that of the computation complexing closely related to increments of networks in incremental dynamic community detecting algorithm,a mixed dynamic community detecting algorithm is proposed by combining label propagation algorithm and modularity optimization algorithm in this paper.The algorithm classifies the change of social network into dramatical evolution and non-dramatic evolution.In the situation of dramatical evolution,It takes the snapshot of a dynamic social network as a completely network and detects community from the snapshot with the algorithms applied only to static networks.In the situation of non-dramatic evolution,it partitioned communities incrementy based on the historical detected communities by combining label propagation algorithm and modularity optimization-Louvain algorithm.The experiments on artificial data sets and real data sets verify the correction and effectiveness.

关 键 词：增量式动态社区发现 标签传播 模块度优化 Louvain算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]