周 旸，陈晓云+，程建军,2，刘 伟，苗海飞

1.兰州大学 信息科学与工程学院，兰州 730000

2.甘肃省资源环境科学数据工程技术研究中心，兰州 730000

基于最优特征向量的谱二分社团检测方法*

周 旸1，陈晓云1+，程建军1,2，刘 伟1，苗海飞1

1.兰州大学 信息科学与工程学院，兰州 730000

2.甘肃省资源环境科学数据工程技术研究中心，兰州 730000

针对传统谱二分社团检测算法一般只使用某一特定的特征向量对网络进行划分，并不能保证能够得到最佳的社团结构这一缺陷，提出了一种使用最优特征向量的谱二分社团检测方法。该方法利用网络/子网络转移矩阵的特征向量持续将网络分裂为若干个子网络，分裂过程并不固定使用单一的、特定的特征向量，每次分裂使用的是能使得模块度增量最大的一个特征向量。此外，为了充分利用网络的拓扑信息，还利用网络中每条边所关联的两个顶点拥有的共同邻居的信息，将原始网络转换为带权的网络，并基于此带权网络的转移矩阵，使用最优特征向量持续将其划分为若干个子网络，得到其社团结构。为了验证这两种方法的有效性，在7个实际网络上进行了实验。实验结果证实，该方法能够有效地从网络中提取高质量的社团结构。

社团检测；谱二分法；特征值；特征向量；模块度

1 引言

社团结构是很多复杂网络拥有的显著的结构特征，表现为网络中的顶点能够被划分成不同的组，同一组内的顶点之间联系十分紧密，不同组的顶点之间的联系较为稀疏，其中每一个组即为一个社团。……