计算机工程 ›› 2019, Vol. 45 ›› Issue (10): 227-233.doi: 10.19678/j.issn.1000-3428.0052570

• 人工智能及识别技术 • 上一篇    下一篇

基于聚类质量的半监督INMF动态社区检测算法

陈吉成, 陈鸿昶, 于洪涛   

  1. 国家数字交换系统工程技术研究中心, 郑州 450002
  • 收稿日期:2018-09-05 修回日期:2018-10-23 出版日期:2019-10-15 发布日期:2018-11-01
  • 作者简介:陈吉成(1984-),男,博士研究生,主研方向为社交网络挖掘、通信与信息系统;陈鸿昶、于洪涛,教授。
  • 基金项目:
    国家自然科学基金创新研究群体项目(61521003)。

Semi-Supervised INMF Algorithm for Dynamic Community Detection Based on Clustering Quality

CHEN Jicheng, CHEN Hongchang, YU Hongtao   

  1. China National Digital Switching System Engineering and Technological R & D Center, Zhengzhou 450002, China
  • Received:2018-09-05 Revised:2018-10-23 Online:2019-10-15 Published:2018-11-01

摘要: 为实现复杂网络的快速分析,提出一种基于聚类质量的改进非负矩阵分解(INMF)算法,将其用于动态社区检测。从理论分析角度证明了演化谱聚类、INMF和模块密度优化之间的等价性,并基于该等价性,在不增加时间复杂度的前提下,通过在INMF中加入先验信息给出一种半监督INMF算法。在人工构造和真实世界的动态网络上的实验结果表明,与QCA、MIEN算法相比,该算法的社区检测质量和社区检测效率更优。

关键词: 聚类质量, 半监督, 非负矩阵分解, 动态社区检测, 图模型

Abstract: In order to realize the rapid analysis of complex networks,an Improved Non-Negative Matrix Factorization(INMF) algorithm based on Clustering Quality(CQ) is proposed,and applied to dynamic community detection.From the perspective of theoretical analysis,the equivalence between evolutionary spectral clustering,INMF and module density optimization is proved.Based on the equivalence,a semi-supervised INMF algorithm is given by adding a priori information to INMF without increasing the time complexity.Experimental results on artificial networks and real-world dynamic networks show that the algorithm has better community detection quality and community detection efficiency compared with QCA and MIEN algorithms.

Key words: Clustering Quality(CQ), semi-supervised, non-negative matrix factorization, dynamic community detection, graph model

中图分类号: