基于核心图增量聚类的复杂网络划分算法  

Complex Network Community Detection Based on Core Graph Incremental Clustering

作　　者：张新猛[1] 蒋盛益[1] 

机构地区：[1]广东外语外贸大学思科信息学院,广州510006

出　　处：《自动化学报》2013年第7期1117-1125,共9页Acta Automatica Sinica

基　　金：国家自然科学基金(61070061);教育部人文社会科学研究青年基金项目(11YJCZH086;12YJCZH281;13YJCZH258)资助(61070061)~~

摘　　要：借鉴基于聚类的无监督入侵检测算法(Clustering-based method for the unsupervised intrusion detection,CBUID)聚类原理,提出一种基于核心图增量聚类的社区划分算法(Clustering-based method for community detection,CBCD).本文提出一种社区摘要构建方法,给出节点与社区相似度的计算公式.首先,对由少量高度数节点组成的核心网络采用现有算法进行核心社区划分,然后,采用增量方式依据节点与社区相似度,将剩余节点划分到核心社区中.算法复杂度主要依赖于网络规模、边的数量及划分的社区个数,具有线性复杂度.通过在几个典型真实网络数据集上测试,所提算法能够有效地进行社区划分.This paper references the principle of clustering in clustering-based method for the unsupervised intrusion detection algorithm（CBUID）,and proposes a clustering-based method for community detection（CBCD）.We propose a method of community summary building,and give the formula of the similarity between node and community.First,it detects communities on the core network composed of a small amount of high-degree core nodes,then partitions the remaining nodes into core community according to the similarity between the node and community incrementally.Its running time mainly depends on the network size,the number of edges and the number of communities,and our algorithm has essentially a linear time complexity.Applications on several common real networks demonstrate that this method is very effective at community detection of networks.

关 键 词：复杂网络 社区摘要 相似度 社区发现 

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