一种基于点的多社区谱分解方法  

A Node-Based Spectral Decomposition Algorithm for Multi-Communities Detection

作　　者：王莉[1] 苏卫华[1] 余雪丽[1] 

机构地区：[1]太原理工大学计算机与软件学院,山西太原030024

出　　处：《计算机工程与科学》2009年第9期8-10,35,共4页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(60472093);山西省自然科学基金资助项目(2006021015);山西省教育厅高校科技开发资助项目(2007111)

摘　　要：针对传统的谱分解存在网络平分或者递归平分问题,本文提出一种基于点的改进的分步骤的复杂网络谱分解的多社区算法(NSDA)。该算法首先对复杂网络中度为1、2的结点和局部具有特殊聚集结构的结点进行预处理,让其和相应的点集构成子社区;接着,利用基于点的谱分解的次小、第三小、第四小的特征值对应的特征向量进行多社区的发现,得到隐含社区的核心点集;最后,以核心点集为中心,利用广度优先算法,依据点或子社区的局部最佳特征,确定相应的社区成员,从而构造出多个社区。实验表明,该算法通过分步预处理,加快了社区划分速度,减少了干扰结点,提高了谱分解的合理性。The traditional spectral decomposition algorithm always only divides one network into two parts. This paper presents a node-based spectral decomposition algorithm（NSDA）for multi-communities detection. There are three steps in NSDA： First, these nodes whose degree is 1 or 2 and some special local gathered structures are pre-proeessed. And some sub-communities are then constituted. Furthermore, we utilize the eigenvectors that are corresponding to the second smallest, third smallest, fourth smallest eigenvalues to get the numbers of communities and the core of the community set. Finally, based on the core node set and the feature of ＂local optimal＂, we get the members of communities by using a breathfirst algorithm. Experiments show that the NSDA algorithm, through the step-by-step pre-treatment, not only reduces noise to improve the performance of dividing communities, but also increases the feasibility of the detected communities.

关 键 词：局部聚集结构 核心点集 局部最佳 谱分解 社区 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]