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

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

针对传统的谱分解存在网络平分或者递归平分问题,本文提出一种基于点的改进的分步骤的复杂网络谱分解的多社区算法(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.