基于动态有噪网络的增量社团发现算法  

Incremental Community Detection Algorithm Based on Dynamic Noisy Network

作　　者：董哲[1] 伊鹏[1] 扈红超[1] 

机构地区：[1]国家数字交换系统工程技术研究中心,郑州450002

出　　处：《计算机工程》2014年第2期166-170,共5页Computer Engineering

基　　金：国家"863"计划基金资助项目"面向三网融合的统一安全管控网络"(2011AA01A103)

摘　　要：在动态社会网络中,诸如垃圾邮件之类的噪声会影响网络的稳定性,导致其社团结构难以被准确发现。针对该问题,提出一种采用增量结构的社团发现算法。利用相对熵处理噪声,通过改进的增量算法发现社团结构。实验结果表明,该算法针对不同动态社会网络的发现性能均优于传统动态社团发现算法,其模块度可达到0.8左右,互信息值变化也较平稳,可有效避免噪声对算法性能的影响。The exist noises like junk mails in dynamic social network which affect the stability of the dynamic social network. The existed dynamic community detection algorithms cannot identify this kind of cormnunity structure correctly. Aiming at this problem, an algorithm called preFilter is proposed to solve the problems that the community structure cannot be identified correctly with the noise in the dynamic social network. It uses the relative entropy to filtering the noise in dynamic social network, then an improved incremental algorithm is proposed to identify community structure in the dynamic social network. Experimental results show that preFilter can reach a better performance than other dynamic algorithms, and get a stable NMI value and the modularity Q value which reaches about 0.8. This algorithm can avoid the influence of the noise effectively and performs effectively and accurately in identifying community structures in dynamic social networks.

关 键 词：动态社会网络 社团结构 稳定性 噪声滤除 相对熵 增量算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]