一种基于增量式谱聚类的动态社区自适应发现算法  

An Adaptive Dynamic Community Detection Algorithm Based on Incremental Spectral Clustering

作　　者：蒋盛益[1,2] 杨博泓 王连喜[3,2] 

机构地区：[1]广东外语外贸大学思科信息学院,广州510006 [2]语言工程与计算广东省社会科学重点实验室,广州510006 [3]广东外语外贸大学图书馆,广州510420

出　　处：《自动化学报》2015年第12期2017-2025,共9页Acta Automatica Sinica

基　　金：国家自然科学基金(61572145);教育部人文社会科学研究青年项目(14YJC870021);广东省科技计划项目(2014A040401083;2015A030401093);广东省普通高校科技创新项目(2012KJCX0049);广东外语外贸大学研究生科研创新项目(15GWCXXM-40);广东大学生科技创新培育专项资金(308-GK151018)资助~~

摘　　要：针对当前复杂网络动态社区发现的热点问题,提出一种面向静态网络社区发现的链接相关线性谱聚类算法,并在此基础上提出一种基于增量式谱聚类的动态社区自适应发现算法.动态社区发现算法引入归一化图形拉普拉斯矩阵呈现复杂网络节点之间的关系,采用拉普拉斯本征映射将节点投影到k维欧式空间.为解决离群节点影响谱聚类的效果和启发式确定复杂网络社区数量的问题,利用提出的链接相关线性谱聚类算法发现初始时间片的社区结构,使发现社区的过程能够以较低的时间开销自适应地挖掘复杂网络社区结构.此后,对于后续相邻的时间片,提出的增量式谱聚类算法以前一时间片聚类获得的社区特征为基础,通过调整链接相关线性谱聚类算法实现对后一时间片的增量聚类,以达到自适应地发现复杂网络动态社区的目的.在多个数据集的实验表明,提出的链接相关线性谱聚类算法能够有效地检测出复杂网络中的社区结构以及基于增量式谱聚类的动态社区自适应发现算法能够有效地挖掘网络中动态社区的演化过程.To tackle the hot issue of dynamic community detection in complex networks, this paper proposes an adaptive dynamic community detection algorithm based on the spectral clustering algorithm of linear link-related approach for static community detection and the incremental spectral clustering. The dynamic community detection algorithm uses the normalized Laplacian matrix to present the relationships of the complex network nodes, and then uses the Laplacian eigen map to map the node into the k-dimensional Euclidean space. In order to solve the problems of the outliers to nodes and the heuristics to identify the number of communities, this paper applies the spectral clustering algorithm of linear link-related approach to detect the community structure of the initial time slice, which makes the process of the complex community detection in an adaptive and computationally inexpensive way. For the subsequent adjacent time slices, the incremental spectral clustering algorithm of this paper aims to detect the dynamic community of complex network adaptively by clustering results for the next time slice based on the foundation of community characteristics of the previous time slice, and adjusting the spectral clustering algorithm of linear link-related approach. Experimental results on a series of datasets show that the spectral clustering algorithm of linear link-related approach can detect the community structure in the complex networks effectively and that the adaptive dynamic community detection algorithm based on incremental spectral clustering can also mine the evolution of dynamic communities effectively.

关 键 词：谱聚类 拉普拉斯矩阵 拉普拉斯本征分析 增量聚类 社区检测 动态社区 

分 类 号：O157.5[理学—数学]