基于张量建模和进化K均值聚类的社区检测方法

陈吉成，陈鸿昶

（信息工程大学信息技术研究所，郑州 450002）

0 引言

社区检测（Community Detection，CD）［1］是分析复杂网络的重要工具，其目的是发现强凝聚性群体，此类群体中成员彼此之间的联系比网络中其他参与者的联系更加紧密，由此提取出的社区具有重要统计价值，应用范围包括语义网本体构建［2］、标签系统中的话题检测［3］、个性化搜索和推荐［4］等。

异构网络中的社区检测与传统社区检测方法稍有不同。传统社区检测方法大多仅考虑一种关系，而多关系网络中的CD 则需要对不同关系上的交互进行整合，并基于不同参与者之间的不同关系，发现共同的底层隐藏社区结构。目前这方面的研究已经有一些研究成果。文献［5］中针对一维网络的传统CD方法的统一定义，提出了一种基于上下文信息的社区检测（Contextual Information-based Community Detection，CICD）方法，并基于此，尝试将单关系网络中的CD 方法扩展到多关系网络；但该方法假定不同关系彼此独立，且忽视了关系和参与者的双向影响。文献［6］将CD问题建模为一个单目标优化问题，提出了一种基于Memetic 的方法，通过优化模糊度评价指标检测复杂网络中的重叠社区结构，并使用“一致续存”度量来修改给定的非重叠社区结构。与之类似，文献［7］中提出了一种改进的蚁群算法重叠社区发现方法，采用局部扩展的社区识别方法。文献［8］方法根据关系分配不同权重，反映出网络中每种关系的不同重要程度。此外，根据关系的概率性权重，将多关系网络转换为单关系网络，应用CD方法，以揭示参与者的社区隶属度。也有研究者提出了局部谱聚类（Local Spectral Clustering，LSC）［9］和基于聚类融合［10］的方法。聚类融合或共识聚类方法主要应用于单关系网络，其在网络不同视图上应用聚类方法得到多个聚类结果，并在此基础上找到共享的共识社区结构。

由于矩阵和张量分解已成为复杂网络分析的重要工具，因此这方面也有很多应用。如：文献［11］中提出了多张量分解方法，从表示多关系数据的超图中提取社区，合并来自多个图的信息。文献［12］中提出了基于平行因子（PARAllel FACtors，PARAFAC）张量分解的多图聚类方法，利用系数隐性因子来确定实体的社区软隶属度。文献［13］中提出了基于特征和关系信息的所有相关矩阵的联合分解的谱框架，以揭示不同类型对象之间的隐藏社区结构。

针对包含同类实体之间异构交互的多关系网络，为进行多关系网络建模，本文使用了三阶邻接张量，张量的每个切片表示与参与者之间一种类型的关系相对应的邻接矩阵。应用张量分解作为关系学习工具，可以揭示参与者的唯一隐性表征。本文的主要工作在于：1）提出了用于多关系网络表征的基于张量的模型；2）开发了使用非负张量分解和基于遗传算法（Genetic Algorithm，GA）的K均值的社区检测框架。实验结果表明所提方法具有较好的性能。

1 多关系网络中的社区检测

本文多关系网络社区检测的流程如图1 所示，利用RESCAL 张量分解和GA-K均值聚类在多关系网络中进行社区检测。为了在学习方法中考虑到数据的关系特性，本文使用张量对多关系网络进行建模。下面对图1 各个重要环节进行介绍。

图1 本文方法的流程Fig.1 Flow chart of proposed method

1.1 多关系网络建模

一个张量可被定义为一个多模数组或一个多维矩阵。一个张量的维数（变量）称为阶、向或模。向量是由一个下标标识的单向张量；矩阵则是具有二维（行和列）的双向张量。同理，还有更高阶的张量。张量纤维是张量的一维片段，类似于矩阵的行或列。张量切片是张量的二维截面（片段），类似于矩阵。本文使用下标小写字母表示张量或矩阵的一个元素（例如xijk为三阶张量X的ijk元素），A•B和表示逐元素矩阵乘法或除法。

采用三阶张量X，将实体间的二元关系建模为一个张量。该三阶张量中，两个模由域的实体构成，第三个模则保持着关系。张量的每个frontal 切片表示与多关系网络的一种关系相对应的邻接矩阵。给定一个多关系网络MNet={Ai|1≤i≤m}，其中包含以m种类型的关系{R1，R2，…，Rm}彼此关联的n个实体的集合{E1，E2，…，En}，则创建出一个大小为n×n×m的三阶张量，其中每个frontal 切片i对应于关系的邻接矩阵Ai。张量条目xijk=1表示第i个实体与第j个实体以第k种关系彼此关联。而对于不存在关系和未知关系，该条目被设为0。表征为三阶张量的多关系网络如图2所示。其中，E1，E2，…，En表示实体，R1，R2，…，Rm表示关系。

图2 多关系数据的张量模型Fig.2 Tensor model of multiple relational data

1.2 利用张量分解揭示隐性特征

将多关系网络建模为张量是非负的，当且仅当在因子分解上施加了非负约束时，相应的隐性分量才具有物理意义。因此，应采用非负的稀疏因子分解。本文提出的方法中应用了RESCAL分解［14］，与其他非负张量分解（Non-negative Tensor Factorization，NTF）方法相比，RESCAL 分解能够捕捉学习过程中的全局相依性，支持不受知识库大小影响的快速查询访问。RESCAL 中，实体通过隐性空间唯一表示。而在其他张量分解方法中，例如CP 和Tucker［15］，则根据实体是构成关系中的主体还是对象，存在两种不同的实体隐性表征。RESCAL 分解方法具有高度扩展性，可有效应用到大规模关系数据上。

1.3 RESCAL分解

RESCAL 是关系学习的隐性因子模型，它将邻接矩阵X∈Rn×n×m分解为一个单因子矩阵F∈Rn×r和一个核心张量R∈Rr×r×m：

式中：r为用户给定的分解的秩；×1和×2分别表示模1和模2的积；E为近似相关误差矩阵。式（1）的展开形式等价为式（2）：

式中：Rk和Xk分别表示R和X的第k个frontal切片，k取小于等于m的正整数。式（1）～（2）中，X的每个元素xijk近似为Rk fj，其中fi，fj∈Rr为F的第i行和第j行。RESCAL 分解如图3 所示。图3 中，灰色单元表示条目xijk，第i个和第j个纤维对应于第i个和第j个实体的隐性因子。

图3 RESCAL分解示意图Fig.3 Schematic diagram of RESCAL decomposition

该模型中，F的行fi对应第i个实体的隐性表征，张量R的frontal 切片Rk则对第k种关系的隐性变量的交互进行建模。由此，F是包含实体隐性表征的矩阵，R为隐性分量与谓词的交互。

1.4 RESCAL分解计算

为执行RESCAL分解，需要求解以下优化问题：

假定因子分解的秩值r和正则化参数(λF≥0，λR≥0)为已知。利用任何随机矩阵对F和Rk进行初始化，或从)的特征分解中对F进行初始化。为计算因子矩阵和核心张量的非负更新，该方法利用式（4）～（5）对F和所有Rk（张量R的第k个切片，最大切片数目为kmax）进行交替更新，直至式（3）中目标函数的相对变化收敛至一些较小阈值或达到最大迭代次数。

在该步骤中，使用RESCAL 分解对表示多关系网络的张量进行因子分解。该步骤的结果为矩阵F∈Rn×r，其中，n为总条目数，r为因子分解的秩。由于F中包含低维嵌入实体的唯一性表征，可应用聚类方法对F实施聚类以发现不同的社区。

1.5 使用GA-K均值算法进行社区检测

聚类技术是识别实体集合中内在组织的非监督式技术。K均值算法是广泛使用的聚类技术，但其存在两个缺陷：1）陷入局部最优；2）结果的准确度取决于初始聚类中心。

遗传算法是为寻找全局最优解而设计的随机搜索技术［16］。提出的方法中，应用遗传算法作为优化工具，以得到用于K均值聚类算法的最优初始种子。对因子分解的结果（隐性因子矩阵F）应用GA-K均值算法［17］，以得到期望的社区。采用基于GA 方法的原因是该方法在问题空间中执行全局搜索，且便于混杂和扩展，以适应多种问题结构。

GA-K均值聚类算法包含以下三个步骤：

步骤1 随机生成染色体的初始种群。每个染色体包含K个初始种子，其中K为要形成的聚类数。

步骤2 对每个染色体进行解码，得到初始种子。利用这些初始种子，执行K均值聚类。其后，计算出适应度函数值。

步骤3 在当前种群上执行遗传操作，以生成新一代种群。迭代该过程，直至满足停止标准。提出的方法中，若适应度在连续5次迭代中未得到改善，则终止算法。

1.6 遗传表征和种群初始化

染色体的长度取决于因子分解的秩和要形成的聚类数。若因子分解的秩为r，聚类数为K，则每个染色体的长度为K×r。矩阵F的每行fi均唯一地表征第i个实体。染色体包含矩阵F的随机选定的K行。图4（a）给出了K=5、r=3的一个染色体，初始种群为随机生成。

1.7 适应度函数的计算

对于种群中的每个染色体，必须测量该染色体的质量，也就是测量该染色体所表征的可能解的适应度。此处使用的适应度函数为聚类间散布矩阵与聚类内散布矩阵的迹比。由此，本文要求解的优化问题为该函数的最大化，即创建出能够最大化类内相似度和最小化类间相似度的聚类。对于第k个聚类，散布矩阵Sk定义为：

式中：μk为属于第k个聚类Ck的数据点的平均向量。类内散布矩阵SW表示所有聚类的散度之和，其计算式为：

类间散布矩阵SB计算式为：

式中：Nk为属于第k个聚类的数据点数量；μk为第k个聚类的平均向量。混合参数向量μ可计算为：

其中，混合参数向量µ表示社区间和社区内的边的比率，µ的元素数值越低，表示社区质量越高。将类间散布矩阵和类内散布矩阵的迹比取作适应度函数。目标是最大化以下比率fobj：

式中：Tr（）表示求迹运算符。

1.8 新种群的生成

确定了问题编码的染色体，并选择合适的适应度函数后，可以应用各种遗传算子（例如选择、交叉、变异）开始解的进化。使用这些算子，迭代生成新代的解，直至达到收敛标准。下面将讨论研究中使用的选择、交叉和变异算子。

1）选择算子。该算子从种群中选择要应用遗传交叉的染色体。本文使用的选择方法为轮盘赌选择法。该方法也称为适应度比例选择，根据染色体的适应度数值来选择染色体。

2）交叉算子。选择后，在染色体上应用交叉算子以得到更好的后代。本文研究中使用了均匀交叉算子和改进的全算术算子。

在均匀交叉中，取两个父染色体P1 和P2，并随机生成一个二进制mask。取mask 中为1 的第一个父染色体的聚类中心和mask 为0 的第二个父染色体的聚类中心，填充第一个子染色体的聚类中心；取mask 中为0 的第一个父染色体的聚类中心与mask 为1 的第二个父染色体的聚类中心，填充第二个子染色体的聚类中心。图4（b）展示了对两个以mask 编码的父染色体应用均匀交叉算子，生成两个子染色体的样例。

算术算子线性地合并两个父染色体，根据以下计算式生成新染色体：

式中，a为随机选定的加权因子。本文对算术交叉算子进行了调整，以适应本文的问题定义。在改进全算术算子中，使用一个mask 以选择要应用算术算子的染色体聚类中心。图4（c）给出了a=0.7时的改进全算术算子的样例。

3）变异算子。变异算子在种群中引入多样性，确保利用整个搜索空间。交叉算子在两个父染色体上操作，变异算子则通过改变一个或少数几个性状，对染色体进行局部修改。本文使用的实值均匀变异算子是针对本文应用而设计的，因为在RESCAL 分解后获得隐形分量矩阵，其元素都是实数值，实值均匀变异算子是按实数值变异，再对标记的离散量进行四舍五入，均匀变异以较小的均等概率替换原有基因，波动较小，在聚类中心的下限和上限范围之间选择任意随机值。在染色体的该聚类中心内，将基因数值替换为选择的随机值。变异操作如图4所示。

图4 染色体表征与遗传算子Fig.4 Chromosome representation and genetic operator

所提出的多关系网络中的社区发现方法主要步骤如下：

步骤1 给定一个包含n个实体以及实体间m类关系的多关系网络，创建一个大小为n×n×m的三阶张量。

步骤2 在构建的张量上应用RESCAL 张量分解，其中r为因子分解的秩。该步骤得到的结果为包含实体的唯一性表征的因子矩阵F∈Rn×r。

步骤3 对因子矩阵F应用GA-K均值算法，以得到形成社区所需的实体聚类。

2 实验与结果分析

本文GA-K均值的性能通常依赖于参数的数值选择。该启发式有5 个主要参数，即：交叉率Pc、变异率Pm、种群规模、代数，以及实验次数。这些参数随不同类型的数据集而变化。本文实验中启发式参数如下：种群规模为100；交叉率Pc为0.8；变异率Pm为0.1。混合参数μ取0.3（向量元素均取0.3）。实验中采用了精英方法，确保将前代中得到的适应度最高的染色体保留到后代。适应度在连续5 代中未得到改进时，算法终止。为确定合适的隐性分量数量，利用不同数值的r执行因子分解，并将正规化参数λA和λR值设为10。

2.1 评价指标

本文采用纯度、重叠归一化互信息（Overlapping Normalized Mutual Information，ONMI）和F 得分作为评价度量。假定网络的人工标注真实社区结构表示为C={C1，C2，…，CK}，方法实现的社区结构表示为C′={C′1，C′2，…，C′K}。使用的三个评价度量定义如下：

1）纯度：其为外部评价度量，测量一个聚类中包含的数据样本属于单个类别的程度［18］。纯度为1 表示完美聚类解，其中聚类仅包含单个类别的实体。因此，纯度值越大，聚类解越好。纯度计算式为：

式中：n为实体总数；|Cj∩C′k|表示Cj与C′k之间的交互。

2）重叠归一化互信息的具体定义可以参考文献［19］，ONMI越高，社区划分越接近真实情况。

3）F得分：该评价度量以网络真实社区结构C与方法实现的网络社区结构C′中对象对的公共分类成员为基础。设T表示C中属于同一分类的对象对的集合，S表示在C′中被分配到同一个聚类的对象对的集合，则F得分（F-score）计算式为：

F 得分的数值在0 和1 之间，数值越高，表明社区划分越接近真实。

2.2 数据集

为进行实验分析，本文使用了一个人工合成数据集和两个公开的数据集。

1）合成数据集：本文生成了包含三个聚类的合成网络，这三个聚类分别包含100、150 和250 个成员。利用较低帧率（Lower Frame Rate，LFR）基准模型［20］来生成合成网络及社区，如图5 所示，从聚类1 到聚类2，从聚类2 到聚类3，再从聚类3 到聚类1，网络中包含500 个成员，在聚类间和聚类的内部含有很多交叉关系。对于网络的每个关系，按照伯努利分布和特定交互概率，在成员之间生成一条链路。此外，由于生成的合成数据集是定向的，很多常见的基线社区检测方法更适用于非定向网络，因此，将多关系网络中的每个非对称关系转换为对称关系。

图5 合成网络及社区Fig.5 Synthetic network and communities

2）公开的现实数据集的网络介绍如表1 所示，包括Coauthorship 数据集和Twitter 数据集，且均为先验可用。Coauthorship 数据集的顶点为作者，边为合作，共计24 个研究领域，每篇文章被标注了一个或多个研究领域。通过发表途径（会议/杂志）对（重叠）真实社区进行标记。该网络中包含103677 个顶点，352183 条边和1705 个社区。Twitter 数据集包含社交网站Twitter中不同用户之间的交互。文献［21］创建了5 个不同子数据集，每个子数据集中，考虑三种关系：提及，关注，以及转发。这三种关系均被考虑为二元关系。对于每个关系（提及、关注和转发），从节点i到节点j的定向边分别表示用户i在其推文中至少有一次提及、关注或转发了用户j。

表1 网络介绍Tab.1 Introduction of networks

2.3 结果统计分析

本文实验数据集采用合成数据集、公开的Coauthorship数据集和Twitter数据集，并与三个优秀社区检测方法进行比较，这三个方法分别是：文献［5］提出的CICD 方法；文献［6］提出的Memetic 方法，该方法将检测问题解释为一种单目标的优化问题；文献［9］提出的LSC 检测方法，该方法是一种图论方法。与文献［9］类似，文献［22］也是一种局部谱聚类社区检测方法，该方法的特点是增加了社区节点属性和距离度量，从而减少了对所选CD性能的依赖，但对于本文统计性指标没有本质提升。因此，文献［9］和文献［22］作为一类方法进行比较。实验通过2.1 节中的三个评价指标进行比较。不同方法在纯度、ONMI 和F 值方面的性能比较如表2～4 所示。由表2～4 可知，本文方法的纯度最少提高了5 个百分点，重叠归一化互信息（ONMI）最少提高了2 个百分点，F 得分最少提高了3 个百分点，其性能明显优于CICD［5］、Memetic［6］和LSC［9］。Memetic［6］和CICD［5］的最终结果取决于单个检测方法的性能。其中，Memetic方法在发现某个非重叠社区结构后，重叠属性通过后续处理可被发现，因此，这类方法最终的结果质量很大程度上取决于初始的非重叠社区结构。LSC 通过未标签的数据分析来获取更多其他数据的潜在分布情况，而类似的数据结构必须具有相同的标签，LSC 是一种图论方法，其对检测方法的选择具有一定依赖性，最终的结果质量取决于在异构网络上使用的CD 的性能。本文利用网络参与者之间隐藏的隐性关系信息进行社区发现，提出了基于链路的聚类框架，揭示参与者交互中所共享的社区结构，使用张量分解作为关系学习工具，在学习过程纳入关系信息，应用GA-K均值算法进行社区发现。因此，所提方法的性能不取决于任何一个CD，能够从多个非重叠社区结构中有效地学习社区属性，其性能更优。此外，多关系方法的性能优于在网络的每种关系上进行聚类的性能，在社区检测过程中引入多种关系，有助于揭示共享社区模式。

表2 不同数据集上不同方法的纯度性能Tab.2 Purity performance of different methods on different datasets

表3 不同数据集上不同方法的ONMI性能Tab.3 ONMI performance of different methods on different datasets

表4 不同数据集上不同方法的F得分Tab.4 F-score measurement of different methods on different datasets

为了对得出的结果进行统计学分析，本文考虑了假设检验的应用。为此，应用Friedman检验［23］，比较不同方法在合成数据集和Twitter数据集上的性能的统计差异。Friedman检验是一种非参数统计检验技术，因此，它不需要对数据的底层分布作任何假设；此外，利用Friedman 检验，可基于计算出的秩次，根据方法的相对性能进行排序。

该检验中，零假设表明所有方法在性能方面明显等效。为得到Friedman 统计量，本文使用了排序方法。设N为实验数据集数量，t为要比较的方法数。对于每个数据集，向t个方法中的每个方法分配从1（最佳结果）到t（最差结果）的秩次。取所有数据集上的平均秩次，计算出每个方法的最终秩次。结果的显著性取决于得到的统计量p值。若p值小于0.05（显著水平α=0.05），则拒绝零假设，可假定比较方法之间存在显著性差异。为进一步分析，选择秩次最优的方法作为控制方法，并应用一组析因分析程序，以执行其他方法与控制方法的逐对比较。实验中，针对每个评价度量（即纯度、ONMI 和F得分）执行了Friedman检验。不同方法的平均秩次如表5所示。从表5 中可以发现，不同方法的p值均非常低（纯度的1.58E-6<0.05，F得分的6.40E-6<0.05，ONMI 的4.04E-8<0.05）。因此，假设不成立，并可认为所有方法的性能中存在显著差异。本文方法秩次最低，因此可被选为控制方法。

表5 不同方法的平均秩次Tab.5 Mean ranks of different methods

2.4 计算参数分析与收敛性

涉入度函数可以评估这个顶点多大程度上属于这个社区，涉入程度有两个重要方面可以体现，即：接近中心度和一致存续性［24］。其中：接近中心度可以度量某个顶点与社区其他顶点的相似度；一致存续性可以度量顶点在其社区中的存续性。这里主要讨论混合参数µ的选择，µ表示社区间和社区内的边的比率，µ数值越低，表示社区质量越高。µ与OMNI的关系如图6 所示。可以看出，随着混合参数μ的增加，涉入度函数的ONMI 值逐渐变低，即：混合参数μ的逐渐增加使得社区划分质量逐渐降低，但依然保持较高的水平，最低为0.75。本文使用两种不同涉入度函数度量，其中一致续存性评价顶点在社区的存在延续性接近中心度评价顶点与社区其他顶点的相似度，从结果来看，两种函数度量均能准确显示ONMI 的变化趋势，且保持了较高的社区划分质量，因此，两种涉入度函数均取得了良好性能。

图6 混合参数与ONMI的关系Fig.6 Relationship between hybrid parameter and ONMI

为消除随机误差的影响，本文在每个数据集上使用不同的解，因此，单次运行方法无法证明方法的有效性或效率。为了展示遗传算法后续各代的适应度变化，本文在数据集上运行10次算法，并绘制适应图如图7所示。其中，图7（a）给出了不同运行下，不同代的种群最优适应度的进化情况；图7（b）给出了不同运行下，不同代的种群平均适应度的变化情况。由图7 可知，平均适应度得分遵循相似模式。但从图7（a）中发现，近严格递减的平均标准误差，即每代的最佳适应度数值范围会在下一代缩减。图7（b）展示了各代在进化时间线上的均值，初始少数几轮的标准误差较小，算法本质上具有探索性，对搜索空间中各种不同的候选解进行探索；因此，曲线在开始时逐渐上升，其后开始收敛，但并非严格一致。这意味着算法在探索搜索空间时，也同时在探索最优解并收敛。

图7 10次实验的100代适应度Fig.7 100 generation fitness in 10 experiments

2.5 运行效率

对于每个数据集，不同方法所需的运行时间如表6 所示。本文方法包括两个计算步骤：1）在数据的张量表征上执行张量分解；2）对因子分解步骤的结果应用GA-K均值。针对分解步骤，所提方法耗时属于中等，时间复杂度主要由基于GA 的K均值算法决定。Memetric 方法的计算时间较长，其收敛时间大于RESCAL分解。LSC的运行时间大于K均值，因为谱聚类的计算量大于K均值聚类。K均值和LSC 的计算时间明显少于其他方法，这是因为聚类算法的复杂度普遍较低。虽然本文方法的时间复杂度属于中等，但社区检测性能优于其他方法。

表6 不同方法在不同数据集上的运行时间 单位：sTab.6 Running times of different methods on different datasets unit：s

3 结语

本文利用网络参与者之间隐藏的隐性关系信息进行社区发现，提出了基于链路的聚类框架，揭示了参与者交互中所共享的社区结构。该方法利用三阶张量对多关系网络进行建模，并使用张量分解作为关系学习工具，在学习过程纳入关系信息，应用GA-K均值算法进行社区发现。在合成和真实数据集上进行大量实验，实验结果验证了所提方法的有效性和高效率。

接下来，我们将进一步分析社区的动态性和时态性。此外，结合软聚类方法和其他聚类标准，利用不同长度的染色体表征对本文方法进行扩展，以确定网络中社区的最优数量。由于GA 方法耗时较久，以后还可尝试通过并行版本的算法来提高运行速度。