一种面向复杂网络的快速模块结构识别算法

隋超，李文刚，白亮

（1.山西省农业科学院（山西农业大学）畜牧兽医研究所，山西 太原 030032；2.山西大学 智能信息处理研究所，山西 太原 030006）

0 引言

模块结构是复杂网络的一个普遍存在且重要性质，也被称为“社区结构”[1-2]。直观理解，在网络中一个模块（簇）由一组结点的连接群构成，这些结点相互联系非常紧密但与网络中其他密集群的结点连接稀疏。识别其模块结构已成为一种探索和理解网络如何工作的重要任务之一[3]。

由于在众多复杂系统中数据以网络形式存在[4]，如生物中的蛋白质互作用网络、基因调控网络、代谢网络等，越来越多学者关注于复杂网络的模块结构分析。为了解决该问题，各种各样的识别方法已经发展，包括潜在空间模型[5-7]、块模型近似[8]、标签传播模型[9]、模块最大化[10-11]、信息论模型[12]和重叠社区识别[13-14]等。根据不同的用户需求，这些模型有着不同的社区定义或识别标准，已被成功地应用到了不同的领域。潜在空间模型主要将网络中结点映射到低维欧式空间，这样基于网络连接性的结点之间接近度被保持在新的空间，然后通过利用传统聚类算法在低维空间中完成结点划分。块模型近似是将模块划分问题看作一个矩阵分块问题，即通过隶属关系对结点进行重新排序并利用块结构近似给定的网络。标签传播模型主要使用每个结点的邻近点信息来决定该结点的标签，不需要任何社区结构的先验知识。模块最大化模型针对模块识别问题构建了模块最大化优化模型，并利用层次聚类策略实现网络划分，该操作是非常耗时的。Blondel等人[11]将模块最大化算法和标签传播算法进行了融合，提出一种快速展开算法。相比其他算法，该算法对大型网络有更好的适应性。信息理论模型是将模块结构识别问题转化为一个信息编码问题，通过随机漫步方法去解决该优化问题。上面提到的模型已经成功地应用到了不同的领域。然而，现有大部分识别算法是基于特征提取和层次聚类策略完成结构识别的。这些操作的计算成本高昂，限制了它们在处理大规模网络上的效率[15]。

众所周知，聚类分析是网络模块结构识别的重要工具之一。在聚类分析中k中心类型算法（如密度峰值[16]和k均值算法[17]）是一类高效聚类算法，它们通过数据点到类中心的相似性快速实现数据的划分。然而，它们主要处理的是特征数据集，无法在一个没有特征空间信息的网络找到类的中心。目前，已有的模块识别算法通过特征映射将网络转换为一个特征数据集并利用k中心类型算法将这些数据集聚类。然而，特征提取可能导致信息丢失和高转换成本。因此，如何直接将k中心类型算法处理原始网络数据是一个非常重要的研究问题。为此，本文将融合和扩展密度峰值和k均值算法，提出一种适合于网络数据的模块结构识别算法。在该算法中，针对网络的特性，定义了结点的局部密度、分离度、相似性度量和类的表示等。基于它们，给出了类中心的选择机制和网络划分的迭代优化策略。通过比较实验分析展示了新算法的模块结构识别精度和速度。

1 基本概念

1.1 密度峰值聚类算法

令X为n×m的数据矩阵，xi为X的第i行，表示第i个数据点，k为聚类个数。密度峰值算法[14]对类的基本假设是类中心周围的数据点的局部密度低于类中心的局部密度，并且类中心与比其局部密度更高的点之间的距离相对较大。数据点的局部密度被定义为式（1）[16]

其中d(xi，xj)=||xi-xj||2为欧式距离，ε是距离阈值，χ(y)是一个指标函数，如果y＞0，χ(y)=1，否则为0。局部密度被用于反映数据点周围邻近点的数量。

数据点的分离度被定义为式（2）[16]

分离度表示比该点局部密度大的所有点的最小距离。如果这个点已经是局部密度最大的点，那么δ(xi)赋值为所有点到它的最大距离。对于一个点来说，其分离度值越小，越有可能被分配给其离其最近的高密度点所属的类。该算法选择k个ρ(xi)δ(xi)最高值的点作为类中心，将剩余点分配到其最近高密度的点所形成的类中。具体的聚类过程见文献[16]。该算法的时间复杂度是O(n2m)。

1.2 k均值聚类算法

k均值算法[17]的聚类准则为

其中U为一个n×k的划分矩阵，uil是u的第i行第l列的元素，表示数据点xi是否隶属于第l类，Z为一个k×m的类表示矩阵，zl是z的第l行，是一个m维向量为第l类的类中心，d(xi，Cl)=||xi-zl||2是欧式距离，它通过度量xi和zl之间的距离来反映它与类的相异性。

k均值聚类算法通过迭代优化方法去最小化聚类准则F，它被形式化地描述如下[17]：

步骤1：随机或基于某种规则从数据中选择k个数据点作为初始类中心；

步骤2：计算划分矩阵U如下，否则u=0il；

步骤3：计算类表示矩阵Z如下：

步骤4：重复上述Step2和Step3过程，直到聚类准则F不再发生变化为止。

k均值聚类算法的时间复杂度为O(knmt)，其中t为最大迭代次数。可以看到其相对于n来说都是线性的，适合于处理大规模数据。

2 新的模块结构识别算法

2.1 基本定义

经典的密度峰值和k均值算法仅能处理特征数据，无法操作网络数据。为了解决该问题，本文将对它们进行扩展，定义适合于网络数据的局部密度、分离度、相似测度和类的表示等。令G=＜V，W＞为一个网络，V为网络的顶点集合，vi为网络中的第i结点，W为n×n的邻接矩阵，wij=1表示第i和j结点中存在边，Ni={vj∈V|wij=1}为第i结点的邻域，|Ni|为它的度。

定义1对于任意vi∈V，它的局部密度被定义为

是两个结点的相似性度量，即共有邻居数。该定义仅使用结点的邻居中比其度小的结点与其相似性总和来反映它的局部密度。它的邻居与它越相似，它的局部密度越大。不使用比其度大的结点可以避免它们对该结点局部密度估计的干扰。

定义2对于任意vi∈V，它的分离度被定义为

其中，η为调节参数，用于避免分母为0，默认设置为0.01。该定义选择比该结点密度大且最相似的结点的相似性倒数来度量其分离性。

基于定义1和2，基于密度峰值算法，本文选择k个ρ(vi)δ(vi)最高值的点作为类中心，并将剩余结点分配到其最近高密度的点所在类中。

定义3令Q为k×n的类表示矩阵，ql是Q中的第l行用于表示第l类，Cl为第l类。Q被定义如下

qli表示第i结点对第l类的代表程度。根据定义，可以看到本文使用所有结点共同表示一个类，每个结点对该类的表示程度与其邻居在该类出现的频率相关。频率越大，它对该类的代表能力越强。值得注意的是Q应该是一个稀疏矩阵，大部分结点的qli值应该为0，仅有与Cl有交集的结点才可能对该类有代表性。

定义4给定Q，结点与类之间的相似测度被定义如下

根据该相似测度定义，第i结点与第l类的相似性取决于它的邻居对第l类的代表程度总和。它的邻居对该类代表性越强，它能可能归属于该类。

定义5k均值算法的聚类准则被重新定义如下

根据聚类准则P的定义，可得

根据该等式可知，聚类准则P等同于每一个类内所有结点的平局相似性总和。它能够实现类内相似性最大化。

2.2 算法的基本步骤

基于已给定的定义1-5，融合密度峰值和k均值聚类算法，提出一种新的快速模块结构识别算法，被称之为DP+KM。它被形式化描述如下：

步骤1：基于公式（4），（5）和（6），计算每个结点的局部密度和分离度；

步骤2：选择k个ρ(vi)δ(vi)最高值的点作为类中心，并将剩余结点分配到其最近高密度的点所在类中，获得初始划分矩阵U；

步骤3：给定U，基于公式（7），计算类表示矩阵Q；

步骤4：给定Q，计算划分矩阵U如下：uil=1，否则u=0il；

步骤5：重复上述步骤3和步骤4过程，直到聚类准则P不再发生变化为止。

DP+KM算法计算成本分为两个部分：使用密度峰值算法计算初始划分矩阵U和利用k均值获得最终划分结果。第一阶段的平均计算时间复杂度为O(np2)，其中为结点的平均度值。第二阶段的平均计算时间复杂度为O(npkt)，其中t为最大迭代次数。因此，DP+KM算法的总时间复杂度为O(np2+npkt)。新算法对密度峰值和k均值聚类算法进行了融合和扩展，既解决了它们不能处理网络数据的缺陷，也融合了它们各自的优点。如新算法利用密度峰值算法克服了k均值算法结果依赖于初始类中心的选择问题，也通过k均值算法的迭代优化克服了密度峰值算法的划分结果无法调节的问题。

3 实验分析

3.1 算法精度分析

为了测试算法的精度，将新算法与已有的经典模块结构识别算法进行了比较，其中包括快速模块最大化（FMM）[10]，快速展开（FUC）[11]，正规化谱聚类（NSC）[7]，标签传播算法（LPA）[9]等4种算法作为实验对比算法进行测试。测试所需的网络数据集来自 KONECT 网站 http：//konect.uni-koblenz.de/networks，其详细描述见表1。

表1 测试算法精度所需的网络数据描述Table 1 Data description for testing the effectiveness of algorithms

在这次试验中本文使用了兰德里指标Adjusted Rand Index（ARI）对模块结构识别算法的精度进行评估，当识别结果越接近真实分类时，ARI值越大。兰德里指标被定义如下

其中nij表示第i类与真实的第j类的共同结点数，bi表示第i类拥有的结点数，dj表示真实的第j类拥有的结点数，n表示网络中结点数。

表2展示了不同算法的模块结构识别精度。根据ARI值，人们可以看到在Grass-feeding web、Terrorists cell和Word adjacencies数据集上，除了新算法以外，其他算法的精度都非常低，主要原因是其网络的模块分布不够清晰所致。相比其他算法，新算法能够通过扩展的密度峰值方法获得较为可靠的模块中心，从而提高了模块识别的精度。在Football、Political books和 Political blogs数据集上，比较的算法都能够较为精准地识别其中的模块。然而，相比其他算法，新算法的表现是更优的。这些实验结果表明：相比FMM、FUN、NSC和LPA算法，新算法能够更加精准地发现网络的模块结构。

表2 算法性能比较Table 2 Comparison among different algorithms

3.2 算法速度分析

进一步比较了FMM、FUC、NSC、LPA和DP+KM算法的运行速度。测试所需的网络数据集也来自KONECT网站，其详细情况见表3。表3中的数据不同于表1，其数据缺乏预先给定的模块标签标注，它们无法用于测试算法的精度。因此，本文仅将它们用于算法运行速度测试。

表3 测试算法速度所需的网络数据描述Table 3 Data description for testing the efficiency of algorithms

表4展示了不同算法在给定网络中的运行时间。应注意到如果数据集的规模很大，一些算法不能在可接受的时间内获得聚类结果。因此，在该实验中，如果一个算法的执行时间大于10 h，就使其终止并设置运行时间为‘NA’，表示运行时间是未知的。根据表4可以看出LPA算法的运行速度是快于FMM，FUC和NSC。主要原因是LPA算法拥有接近线性的时间复杂度。进一步，通过表4也能看到新算法的运行速度是快于LPA算法的。根据该实验分析可得出：相比其他算法，新算法更适合处理大规模网络数据。

表4 不同算法的运行时间（秒）比较Table 4 Running time（seconds）of different algorithms

4 结论

本文提出了一种新的面向复杂网络的模块结构识别算法。该算法是对密度峰值和k均值聚类算法的扩展和融合，定义了适合于网络数据的局部密度、分离度、相似性度量、类的表示以及聚类准则等。最后，将新算法与已有的模块结构识别算法在若干个实际网络数据集中进行了比较分析。实验结果表明了新提出的算法更加适合于处理大网络。在未来工作中，将针对复杂网络中存在的大量重叠模块识别问题，对新算法进行扩展，提出适合快速解决该问题的识别算法，进一步提高其对数据复杂性的适应度。