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

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

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

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

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

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

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

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

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

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

1 引言

社团结构是很多复杂网络拥有的显著的结构特征，表现为网络中的顶点能够被划分成不同的组，同一组内的顶点之间联系十分紧密，不同组的顶点之间的联系较为稀疏，其中每一个组即为一个社团。复杂网络中的社团往往对应于由具有相似特性的顶点组成的功能模块，如社会关系网络[1-2]中的社团往往对应于拥有相同兴趣或是相同职业的一组人，蛋白质相互作用网络[3-4]中的社团可能是一组具有特定功能或特性的蛋白质分子。因此提取复杂网络的社团结构，对于研究网络的结构，确定网络的功能，理解结构与功能之间的对应关系而言，提供了一种有效的研究手段和方法。

自从Newman等人提出GN（Grivan-Newman）算法[5]以来，社团检测方面的研究引起了研究人员的普遍关注，已经提出了大量的社团检测算法，其中包括谱分析方法[6-12]、模块度优化方法[13-16]等。谱分析方法由于拥有严谨的数学公式推导过程作为其理论基础而得到广泛的应用；而模块度优化方法以模块度指导社团划分的方向，如Newman等人提出的FastQ算法[14]，通过不断合并使得模块度增量最大的两个子图，获得模块度最大的社团结构；Barder等人[13]将模块度优化的方法应用到LPA（label-propagation algorithm）当中，让每个顶点选取能够获得最大模块度的标签，控制标签传播的方向。

一般情况下，谱分析方法使用诸如邻接矩阵、拉普拉斯矩阵等与网络关联的矩阵的特征值、特征向量对网络进行划分，得到社团结构。例如，Cheng等人[12]利用与随机游走对应的拉普拉斯矩阵揭示网络中存在的社团结构。Lange等人[9]利用归一化的拉普拉斯矩阵的特征谱提取生物神经网络中的社团结构。谱二分法是谱分析方法的一种特殊情况，这一类方法利用相关矩阵的一个或少数几个特征向量对网络进行划分，每次将原网络划分为两个子网络。例如，Pothen等人[10]利用拉普拉斯矩阵的最小非零特征值对应的特征向量，以其元素的中位数为划分界线，将对应的顶点分别划分到两个社团之中。Newman[6,11]基于归一化拉普拉斯矩阵，给出了解决随机块模型、图的最小割剖分和社团检测三种问题的谱二分法。在Pothen的谱二分法的基础上，Donetti等人[7]利用一个维度可调的特征向量空间，寻找能够使得模块度达到最大的社团结构。而Newman等人[8,17]利用基于模块度矩阵的谱二分法将网络递归地进行分裂，得到社团结构。

然而，传统的谱二分方法通常是按照某一特定的特征向量中元素的分布情况，通过对网络进行持续分裂，从而提取网络的社团结构，但这种方法无法保证每一次分裂一定是最优的。此外，文献[11]中的例子表明，不同的网络可能需要使用不同的特征向量进行分裂，才能得到最佳的社团结构。因此，本文结合模块度优化的思想，提出了一种基于最优特征向量的谱二分社团检测方法。本文方法利用网络转移矩阵的特征向量对网络/子网络进行持续分裂，但分裂过程并不是固定使用单一的特征向量。相反，每一次分裂使用的是能使得模块度增量最大的一个特征向量。在此基础上，为了充分利用网络的拓扑信息，利用相邻顶点之间的公共邻居信息为这两个顶点之间的边计算权值，将原网络转换为带权网络，并利用转换后带权网络转移矩阵的特征向量，使用同样的谱二分法对网络进行分裂，从而提取社团结构。

为了验证本文提出的社团检测方法，在7个实际网络上进行了实验，并与一些已有的社团检测算法进行了比较。实验结果证实，本文方法能够有效地从网络中提取高质量的社团结构。

2 方法描述

本文使用的原始网络都是无权无向图，记为G(V,E)，其中V和E分别是网络的顶点和边的集合，记n=|V|，m=|E|。

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

本文提出的谱二分社团检测方法以模块度最大化为目标。模块度的计算公式为：

其中，di、dj分别为顶点i、j相连的边的数目；当顶点i和j之间有边相连时，Aij=1，否则，Aij=0；δ(x,y)=1当且仅当x=y，否则δ(x,y)=0；ci、cj分别是顶点i和顶点j所属社团的编号。二分法每次将网络分裂为两个子网络，可定义一个向量x记录每个顶点属于哪个子网络，其元素为：

因此，本文方法的目标就是在每次分裂的时候确定每个顶点的归属，使得模块度Q值最大化。以此为出发点，Newman在文献[11]中推导得出：

其中λ为广义特征方程（3）的特征值：

其中A为网络的邻接矩阵，其元素为Aij；D为对角矩阵，其元素；s为λ对应的特征向量。当网络连通时，矩阵D可逆，式（3）变形为：

其中D-1A即为网络的转移矩阵，记作T，即：

亦即，λ为特征方程（5）的最大的特征值时，模块度Q取得最大值。然而，文献[11]的推导过程指出，λ不能取特征方程（5）的最大特征值，因为s=(1,1,…,1)必然是特征方程（5）的一个特征向量，根据Perron-Frobenius定理，该特征向量对应的特征值必然为该特征方程最大的特征值，然而该特征向量无法满足推导过程的一个约束条件。因此，只能退而求其次，选取特征方程（5）次大的特征值作为λ的值，其对应的特征向量s即为解向量x。然而，s中元素值为任意实数，x中元素值为±1。可以简单地将s中的元素向距其最近的+1或者-1靠近，等价于按照s中元素的符号将网络分裂为两个子网络。

然而，从模块度最大化的角度出发考虑，上述分裂过程并不能保证分裂后子网络对应的模块度一定是最大的，即不能保证得到的社团结构是最优的。文献[11]在人工合成网络、海豚社交网络、美国政治书籍网络和美国政治博客网络上的研究结果表明，不同的网络可能需要使用不同的特征向量进行分裂，才能得到最佳的社团结构。因此，本文在分裂过程中并未固定使用某一个特征向量对网络进行分裂，而是依次尝试转移矩阵除最大特征值之外的每一个特征值对应的特征向量，按其元素的符号将网络分别进行分裂，并计算分裂后模块度增量，选择模块度增量最大的一个分裂作为当前网络/子网络分裂的结果。亦即，从模块度最大化的角度而言，每次利用最优的特征向量将网络二分为两个子网络。

对于给定的网络，首先按照上述方法对其进行第一次分裂，得到两个子网络，每个子网络对应于一个社团；随后，对得到的两个子网络分别进行进一步的分裂；重复这一过程，直到对网络/子网络的分裂达到适当的程度，停止分裂过程。由于该方法的目标是使模块度最大化，若某个子网络的分裂不能得到更大的模块度，则停止对该子网络的分裂。本文将该方法称为BSOE（bisection spectral method based on the optimal eigenvectors），其具体步骤如算法1中伪代码所示。

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

其中，C是社团的集合，初始情况下，网络中所有顶点构成一个社团；接着对C中的每一个社团Ci调用函数spectra_split()分裂得到两个社团，如果该分裂能够使得模块度值增大，则接受该次分裂，将社团并入C中，并从C中移除Ci，否则丢弃该次分裂。函数spectra_split()实现基于最优特征向量的谱二分算法：对于社团Ci，首先构造其对应的子网络，获取其邻接矩阵、对角矩阵，计算得到转移矩阵，接着对转移矩阵进行特征值分解得到全部特征值和对应的特征向量，然后利用除最大特征值对应的特征向量以外的每一特征向量分别将该子网络二分为两个子网络，从中选出能使得模块度增量最大的两个子网络作为Ci分裂的结果，并将其和最大的模块度增量一起返回。

其中函数delta_Q()负责计算每一分裂带来的模块度增量，FastQ算法中提出了将两个社团合并为Ci时模块度增量的快速计算公式：，其中ei1,i2是社团之间的边在网络所有边中所占的比例，而则是分别与社团中顶点相连的边在网络所有边中所占的比例。函数delta_Q()需要计算将Ci分裂为带来的模块度增量，与合并时的情况正好相反，分裂带来的模块度增量为：

同样可以快速地进行计算。

2.2 带权的最优特征向量谱二分社团检测方法

算法1给出的基于最优特征向量的谱二分社团检测方法基于无权无向图的转移矩阵，而转移矩阵从网络的邻接矩阵演化得到。网络的邻接矩阵体现了与每个顶点相连的边的信息，然而只依据顶点自身的这些拓扑信息无法简单地判定该顶点的社团归属。相反，顶点之间的公共邻居信息有助于确定两个顶点之间的社团归属关系，通常而言，两个顶点的公共邻居越多，这两个顶点越有可能同属于一个社团。图1给出了一个简单的示例网络，其中边(a,d)连接了两个社团，是社团之间的边。可以看出，该边连接的两个顶点的公共邻居要明显少于社团内部边连接的顶点。因此，顶点之间的公共邻居信息可用以衡量连接两个顶点的边在社团划分中的作用。

Fig.1 Example of community structure,the edge(a,d)connects two communities图1 社团示例，边(a,d)连接两个社团

如果能将顶点的公共邻居信息直接集成到网络的邻接矩阵中，再应用前面提出的谱二分方法检测社团结构，能够提高社团结构的质量。考虑邻接矩阵的实际含义，将顶点的公共邻居信息集成到网络的邻接矩阵中，相当于将原始网络转换为带权网络。本文采用与顶点u和v的公共邻居信息计算边(u,v)的权值w(u,v)，计算公式为：

其中，N(u)和N(v)分别是顶点u和v的邻居顶点集合。

经过转换得到带权网络后，再利用算法1从带权网络中提取社团结构。不过由于网络的边带有权值，应对算法1进行适应性改造：邻接矩阵A的元素值不再只是0或1，而是对应边的权值，即Aij=w(i,j)，对角矩阵D的元素。此外，模块度的计算也需要变更为带权网络的模块度，式（1）中m的含义应变为网络中所有边的权值之和，di和dj应为分别与顶点i和顶点j关联的边的权值之和；式（6）中应变为社团之间的边的权值之和在网络所有边的总权值中所占的比例，而应为分别与社团中顶点相连的边的权值之和在所有边的总权值中所占的比例。

如此一来，社团检测过程中计算的模块度是转换后带权网络的模块度，并不是基于原始网络的真实模块度，因此，在社团检测过程中，可能会出现过度分裂的情况，即有一些子网络会被分裂为特别小的子网络，这些特别小的子网络无法被当作可接受的社团。因此，本文在谱二分方法分裂得到的子网络基础上，检查每个子网络的规模，将一些小的子网络合并为较大的子网络，得到最终的社团结构。与BSOE方法相区别，本文将该方法称为WBSOE（weighted bisection spectral method based on the optimal eigenvectors），算法2中伪代码给出了其大体框架。

算法2带权的最优特征向量谱二分社团检测方法

该方法大体上包含3个步骤：第一步调用Weight()函数将原始网络转换为带权网络；第二步调用改造后的BSOE方法将带权网络分裂为一系列子网络；第三步调用Merge()函数将其中一些小的子网络进行合并，得到最终的社团结构。该框架中Weight()函数和Merge()函数的逻辑分别如算法3、算法4中伪代码所示。

算法3无权网络向带权网络转换：Weight()函数

算法4合并较小的子网络：Merge(C,G′)函数

算法3非常简单，只需要按照式（7）计算网络中每条边的权值即可。算法4中，将原始网络的平均度(davg)和输入的参数t中的较小值设为阈值，当社团中包含的顶点数目小于该阈值时，表明该社团规模过小，应被并入其他社团中。参数t与davg一起作用，控制社团的最小规模。在大多数稀疏网络上，平均度较小，起作用的是参数davg，在一些比较稠密的网络上，davg的值较大，如果仍将规模小于davg的社团合并到其他社团，则有可能导致社团检测精度的损失。因此，需要使用参数t进行调节。参数t的设置应选择一个与大多数稀疏网络的平均度接近的值，建议选择区间[5,9]内的正数。参考“六度分割理论”，本文的实验中统一设置t的值为经验值6。接着，算法4计算规模过小的社团与其他社团之间的相似性，并将该社团并入与其相似性最大的那个社团。该算法中，用位于社团Ci和社团Cj之间边所带的权值计算Ci和Cj之间的相似性，即：

3 实验

本文在7个实际网络数据集上进行了实验，对BSOE方法和WBSOE方法进行验证，使用模块度来衡量算法得到的社团结构的质量，并将BSOE方法、WBSOE方法的结果与5个已有的社团检测算法进行比较，下面给出实验过程及实验结果。

3.1 实验设置

本文使用的7个数据集分别是空手道俱乐部网络[18]、Risk 游戏地图网络[19]、海豚社交网络[20]、科学家合作网络[21-22]、2000年赛季美国大学生足球联赛网络[19]、metabolic网络[4]和 email网络[23]，各网络数据集的统计信息如表1所示。这7个网络均是被广泛认可的基准测试数据集，其中前5个网络的实际社团结构已知，能够较好地体现社团检测算法的有效性和准确性。

Table 1 Parameters of real-world datasets表1 真实网络数据集参数

同时，本文将BSOE方法、WBSOE方法的结果与相关5个算法的结果进行了比较，这5个算法分别是谱聚类[24]（spectral clustering）、Newman2006[8,17]、FastQ[14]、LPAm（label propagation algorithm under modularity constraint）[13]和 DD（dynamic distance）[25]算法。谱聚类算法和Newman2006算法都是谱分析方法，其中Newman2006算法是一种典型的谱二分算法；FastQ和LPAm这两个算法均使用模块度最优策略指导社团检测过程；DD算法是一种基于顶点间动态距离的社团检测算法。

为了衡量各算法从网络中提取的社团结构的质量，采用模块度标准作为首要度量标准，为每个结果计算模块度值，模块度的值越大，表明社团内部顶点间联系越紧密，社团结构质量越好。另外，由于前5个网络数据集的标准社团结构是已知的，使用NMI（normalized mutual information）[26]作为一个辅助的衡量标准，度量各算法在网络上得到的社团结构与其标准社团结构的相近程度。NMI取值范围为[0,1]，其值越接近1，表明算法得到的社团结构与网络的标准社团结构越接近。由于模块度是一个内部评价标准，它的计算与网络的标准社团结构之间不存在任何联系，很多情况下，NMI的值与模块度的值并不一致，它们从两方面分别对算法提取得到的社团结构的质量进行衡量。

3.2 实验结果

表2和表3分别记录了本文算法和5个对比算法检测得到的社团结构的模块度和NMI值。由于metabolic网络和email网络的标准社团结构未知，无法使用NMI对各算法的结果进行度量，故表3没有列出这两个数据集的结果。其中，由于谱聚类方法和LPAm算法的结果具有不确定性，本文实验中将其分别在每个网络上各运行20次，选取出现最为频繁的结果作为该算法的最终结果。

在所使用的7个实际网络中，本文WBSOE方法和BOSE方法能够在其中的5个网络上得到模块度值最好的社团结构，在科学家合作网络和足球网络上也取得了次好的结果；用NMI进行衡量，WBSOE方法同样能够在2个网络上取得最好结果，在其他网络上也能取得比较靠前的成绩。这证明WBSOE方法能够有效地从网络中提取出社团结构，并且社团结构的质量也能够得到保证。相反，除了FastQ算法外的其他4种算法在不同的网络上得到的社团结构的质量存在较大的波动。

Table 2 Modularity of different algorithms on world datasets表2 各算法在真实网络数据集上的结果的模块度值

Table 3 NMI of different algorithms on world datasets表3 各算法在真实网络数据集上的结果的NMI值

对于足球网络，BSOE算法和WBSOE算法在模块度和NMI上并没有取得最好的结果。这是因为足球网络中存在一个由4个顶点组成的社团，BSOE算法和WBSOE算法都会将这个社团合并到其他的社团中去，故这两个算法在足球网络上难以取得超过DD算法的社团结构。即便如此，WBSOE算法也在足球网络上取得了次优的模块度，NMI值也仅次于LPAm算法和DD算法。

对于作为WBSOE算法基础的BSOE算法，在各网络上取得的社团结构的质量，无论是模块度值还是NMI值大部分都逊色于WBSOE算法。即使如此，在所有7种算法中，BSOE算法仍然排在比较靠前的位置，表明该算法也具有较好的效果，也证明了WBSOE算法对BSOE算法的改进是有效的，能够显著提高社团检测的质量。

为了进一步比较BSOE算法和WBSOE算法，着重分析这两种算法在空手道俱乐部网络和Risk游戏地图网络上的结果，并将其提取的社团结构与网络的标准社团结构进行对比。图2和图3分别给出了BSOE方法和WBSOE方法在这两个网络上的检测结果，图中用同一种形状和颜色画出的顶点构成一个社团。

在图2中，BSOE算法和WBSOE算法均将空手道俱乐部网络划分为4个不同的社团，社团数目均大于网络的实际社团数目。但是，从表2中的模块度值可以得知，图2（b）和图2（c）中的社团结构拥有比图2（a）中实际社团结构更高的模块度值，表明这两种方法在该网络上检测出的社团结构具有更高的质量。对比图2（b）与图2（c）中社团结构可以看出，二者中仅有1个顶点的社团归属不同，导致了两者模块度值和NMI值的差距。但这一结果表明WBSOE算法在细节处理上更优于BSOE算法。

Fig.2 Zachary's karate club图2 空手道俱乐部网络

Fig.3 Risk map network图3 Risk游戏地图网络

图3展示的是BSOE方法和WBSOE方法在Risk游戏地图网络上的检测结果。结合表2中的模块度和NMI值可知，图3（b）中社团结构与图3（a）中社团结构存在较大差距，但二者具有相同的模块度值。显然，图3（b）中对于顶点“10”和顶点“29”的划分存在较为明显的错误，而这些错误在图3（c）中得到了修正，再次证明WBSOE算法对BSOE算法的改进是有效的。图3（c）中顶点“26”的社团归属与实际社团结构中的差异，主要是由于该顶点关联了6条边，分别与3个社团相连，每个社团都有两条边与之相连。如果不考虑该顶点在Risk游戏中代表的物理含义，只考虑其拓扑结构的话，将其划分到与之相连的任何一个社团，均是合理的。将图3（c）中社团结构与图3（b）中社团结构的模块度进行对比，可以得知WBSOE方法获得的社团结构具有更高的质量。

综上所述，上述实验证实了本文方法能够有效地从网络中提取出高质量的社团结构，尤其是WBSOE算法，在所有5个网络数据集上均能取得最优或次优的成绩，证明该算法具有较强的可靠性和稳定性，能够适应大多数结构的网络。另外，WBSOE算法与BSOE算法的实验结果的对比，可以证实WBSOE算法对于BSOE算法的改进是十分有效的，能够明显地提高社团检测的质量以及社团结构的合理性。

4 结论

本文基于谱二分法，提出了一种能够寻找最优的特征向量，并利用该向量对网络进行分裂的社团检测算法。同时，针对无权网络上的谱二分法存在的问题，利用顶点之间的公共邻居信息，将无权网络转换为带权网络，并将基于最优特征向量的谱二分社团检测方法进行了适应性改造，使其能够充分利用网络的拓扑信息进行社团检测，提高社团质量。

本文还在7个实际网络数据集上进行了实验，以验证提出的两个方法的有效性，并将检测结果与另外5个相关算法的结果进行了比较。实验结果证实，本文算法能够有效地从网络中提取出高质量的社团结构。

[1]Mcauley J,Leskovec J.Discovering social circles in ego networks[J].ACM Transactions on Knowledge Discovery from Data,2014,8(1):4.

[2]Mcauley J,Leskovec J.Learning to discover social circles in ego networks[C]//Proceedings of the Advances in Neural Information Processing Systems 25,Lake Tahoe,USA,Dec 3-6,2012.Red Hook,USA:CurranAssociates,2012:539-547.

[3]Lewis A C,Jones N S,Porter M A,et al.The function of communities in protein interaction networks at multiple scales[J].BMC Systems Biology,2010,4(1):100.

[4]Jeong H,Tombor B,Albert R,et al.The large-scale organization of metabolic networks[J].Nature,2000,407(6804):651-654.

[5]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.

[6]Newman M E J.Community detection and graph partitioning[J].Europhysics Letters,2013,103(2):28003.

[7]Donetti L,Muñoz M A.Detecting network communities:a new systematic and efficient algorithm[J].Journal of Statistical Mechanics:Theory and Experiment,2004,2004(10):10012.

[8]Newman M E J.Finding community structure in networks using the eigenvectors of matrices[J].Physical Review E,2006,74(3):036104.

[9]Lange S C D,Reus M A D,Heuvel M P V D.The Laplacian spectrum of neural networks[J].Frontiers in Computational Neuroscience,2014,7(7):189.

[10]Pothen A,Simon H D,Liou K P.Partitioning sparse matrices with eigenvectors of graphs[J].SIAM Journal on Matrix Analysis&Applications,1990,11(3):430-452.

[11]Newman M E J.Spectral methods for community detection and graph partitioning[J].Physical Review E,2013,88(4):042822.

[12]Cheng Xueqi,Shen Huawei.Uncovering the community structure associated with the diffusion dynamics on networks[J].Journal of Statistical Mechanics:Theory and Experiment,2010(4):147-167.

[13]Barber M J,Clark J W.Detecting network communities by propagating labels under constraints[J].Physical Review E,2009,80(2):026129.

[14]Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):066133.

[15]Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008(10):155-168.

[16]Sun Penggang,Gao L.A framework of mapping undirected to directed graphs for community detection[J].Information Sciences,2015,298:330-343.

[17]Newman M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences,2006,103(23):8577-8582.

[18]Zachary W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(4):452-473.

[19]Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.

[20]Lusseau D,Newman M E J.Identifying the role that animals play in their social networks[J].Proceedings of the Royal Society of London B:Biological Sciences,2004,271(S6):477-481.

[21]Newman M E J.Scientific collaboration networks I Network construction and fundamental results[J].Physical Review E,2001,64(1):016131.

[22]Newman M E J.Scientific collaboration networks II Shortest paths,weighted networks,and centrality[J].Physical Review E,2001,64(1):016132.

[23]Guimerà R,Danon L,Díaz-Guilera A,et al.Self-similar community structure in a network of human interactions[J].Physical Review E,2003,68(6):065103.

[24]Ng A Y,Jordan M I,Weiss Y.On spectral clustering:analysis and an algorithm[C]//Proceedings of the Advances in Neural Information Processing Systems 14,Vancouver,Canada,Dec 3-8,2001.Cambridge,USA:MIT Press,2002,2:849-856.

[25]Shao Junming,Han Zhichao,Yang Qinli,et al.Community detection based on distance dynamics[C]//Proceedings of the 21st International Conference on Knowledge Discovery and Data Mining,Sydney,Australia,Aug 10-13,2015.New York:ACM,2015:1075-1084.

[26]Fred A L N,Jain A K.Robust data clustering[C]//Proceedings of the 2003 International Conference on Computer Vision and Pattern Recognition,Madison,USA,Jun 18-20,2003.Piscataway,USA:IEEE,2003,2:128-133.

Bisection Spectral Community-Detection Methods Using Optimal Eigenvectors*

ZHOU Yang1,CHEN Xiaoyun1+,CHENG Jianjun1,2,LIU Wei1,MIAO Haifei1

1.School of Information Science and Engineering,Lanzhou University,Lanzhou 730000,China
2.Gansu Resources and Environmental Science Data Engineering Technology Research Center,Lanzhou 730000,China

2016-09,Accepted 2016-11.

In general,the bisection spectral method always uses only one certain eigenvalue and its corresponding eigenvector to extract communities,which does not guarantee to obtain the best community structures.To solve this problem,this paper proposes a bisection spectral method based on the optimal eigenvectors,which utilizes the eigenvectors of transition matrices to partition the network/subnetwork into communities repeatedly,and the eigenvector used in each partition is the one whose bisection can lead to the largest modularity increment.Besides this,in order to encode the topological information into the proposed method,this paper also converts the original networks into weighted ones by utilizing the information of common neighbors of the two end vertices associated with each edge.Based on the transition matrix of the converted network,this paper applies the same bisection spectral method to extract communities.The experiments on 7 real-world networks are performed,and the experimental results show that the proposed method can extract the high-quality community structures from networks effectively.

community detection;bisection spectral method;eigenvalues;eigenvector;modularity

+Corresponding author:E-mail:chenxy@lzu.edu.cn

10.3778/j.issn.1673-9418.1609011

*The Open Fund of Gansu Resources and Environmental Science Data Engineering Technology Research Center in 2015(2015年甘肃省资源环境科学数据工程技术研究中心开放基金).

CNKI网络优先出版:2016-11-07,http://www.cnki.net/kcms/detail/11.5602.TP.20161107.1703.004.html

ZHOU Yang,CHEN Xiaoyun,CHENG Jianjun,et al.Bisection spectral community-detection methods using optimal eigenvectors.Journal of Frontiers of Computer Science and Technology,2017,11(12)：1897-1906.

A

TP181

ZHOU Yang was born in 1991.He is an M.S.candidate at School of Information Science and Engineering,Lanzhou University.His research interests include community detection and complex network analysis,etc.

周旸（1991—），男，江苏溧水人，兰州大学信息科学与工程学院硕士研究生，主要研究领域为社团检测，复杂网络分析等。

CHEN Xiaoyun is a professor at School of Information Science and Engineering,Lanzhou University,and the member of CCF.Her research interests include database,data mining and high performance computing,etc.

陈晓云，女，兰州大学信息科学与工程学院教授，CCF会员，主要研究领域为数据库，数据挖掘，高性能计算等。

CHENG Jianjun is a teacher at School of Information Science and Engineering,Lanzhou University.His research interests include data mining and complex network analysis,etc.

程建军，男，甘肃甘谷人，博士，兰州大学信息科学与工程学院教师，主要研究领域为数据挖掘，复杂网络分析等。

LIU Wei is an M.S.candidate at School of Information Science and Engineering,Lanzhou University.His research interests include data mining and complex network analysis,etc.

刘伟，男，湖北公安人，兰州大学信息科学与工程学院硕士研究生，主要研究领域为数据挖掘，复杂网络分析等。

MIAO Haifei is an M.S.candidate at School of Information Science and Engineering,Lanzhou University.His research interests include data mining and complex network analysis,etc.

苗海飞，男，山西山阴人，兰州大学信息科学与工程学院硕士研究生，主要研究领域为数据挖掘，复杂网络分析等。