第13卷第6期 智能系统学报 Vol.13 No.6 2018年12月 CAAI Transactions on Intelligent Systems Dec.2018 D0:10.11992/tis.201806011 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180716.1159.010html 基于加权聚类集成的标签传播算法 张美琴，白亮2，王俊斌 (1,山西大学计算机与信息技术学院，山西太原030006；2.山西大学计算智能与中文信息处理教育部重点实 验室，山西太原030006) 摘要：标签传播算法(LPA)是一种高效地处理大规模网络的社区发现算法，由于其近乎线性的时间复杂度而 受到广泛关注。然而，该算法每个节点的标签依赖于其邻居节点，其迭代速度和聚类有效性对标签信息的更新 顺序非常敏感，影响了社区发现结果的准确性和稳定性。基于该问题，提出了一种基于加权聚类集成的标签传 播算法。该算法利用多次标签传播算法的结果作为基聚类集，并用模块度评估每个基聚类的重要性，使其作为 节点相似性度量的权值形成加权相似性矩阵，最后通过层次聚类得出最终的社区划分结果。在实验分析中，该 算法和其他5个具有代表性的标签传播算法的改进算法在真实数据集上进行了比较，展示了新算法能有效地 提高标签传播算法的社区发现精度。 关键词：数据挖掘：网络数据；社区发现：标签传播算法：聚类集成；基聚类：模块度；加权度量 中图分类号：TP391文献标志码：A文章编号：1673-4785(2018)06-0994-05 中文引用格式：张美琴，白亮，王俊斌.基于加权聚类集成的标签传播算法J.智能系统学报，2018,13(6)：994-998. 英文引用格式：ZHANG Meigin,BAI Liang,WANG Junbin.Label propagation algorithm based on weighted clustering ensemble[JCAAI transactions on intelligent systems,2018,13(6):994-998. Label propagation algorithm based on weighted clustering ensemble ZHANG Meiqin',BAI Liang',WANG Junbin (1.College of Computer Science and Technology,Shanxi University,Taiyuan 030006,China;2.Key Laboratory of Symbol Compu- tation and Knowledge Engineering (Shanxi University),Ministry of Education,Taiyuan 030006,China) Abstract:Label propagation algorithm(LPA)is one of the high-efficiency community detection algorithms for pro- cessing large-scale network data.It has attracted much attention because of its nearly linear time complexity with the number of nodes.However,in the algorithm,the label of each node depends on the labels of its neighbor nodes,which makes the iteration speed and clustering performance of the algorithm very sensitive to the order of label information update;this influences the accuracy and stability of the community detection result.To solve this problem,a new LPA is proposed based on weighted clustering ensemble.The new algorithm runs the LPAs many times to obtain several parti- tion results,which can be regarded as a base clustering set.Furthermore,the modularity measure is used to evaluate the importance of each clustering.Based on the evaluation results,a weighted similarity measure is defined between nodes to obtain a weighted similarity matrix of pairwise nodes.Finally,hierarchical clustering on the similarity matrix is used to obtain a final community division result.In the experimental analysis,the new algorithm is compared with several other improved LPAs on five real representative network datasets.The experimental results show that the new al- gorithm is more effective for improving the community detection accuracy. Keywords:data mining;network data;community detection;label propagation algorithm;clustering ensemble;base clustering;modularity measure;weighted measure 收稿日期：2018-06-04.网络出版日期：2018-07-17. 现实世界中存在各种各样的复杂系统，网络 基金项目：国家自然科学基金项目(61773247). 通信作者：张美琴.E-mail:landian.zhang@qq,com. 则是这些系统的普遍存在形式，如人际关系网
DOI: 10.11992/tis.201806011 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180716.1159.010.html 基于加权聚类集成的标签传播算法 张美琴1 ，白亮2 ，王俊斌1 （1. 山西大学 计算机与信息技术学院，山西 太原 030006; 2. 山西大学 计算智能与中文信息处理教育部重点实 验室，山西 太原 030006） 摘 要：标签传播算法 (LPA) 是一种高效地处理大规模网络的社区发现算法，由于其近乎线性的时间复杂度而 受到广泛关注。然而，该算法每个节点的标签依赖于其邻居节点，其迭代速度和聚类有效性对标签信息的更新 顺序非常敏感，影响了社区发现结果的准确性和稳定性。基于该问题，提出了一种基于加权聚类集成的标签传 播算法。该算法利用多次标签传播算法的结果作为基聚类集，并用模块度评估每个基聚类的重要性，使其作为 节点相似性度量的权值形成加权相似性矩阵，最后通过层次聚类得出最终的社区划分结果。在实验分析中，该 算法和其他 5 个具有代表性的标签传播算法的改进算法在真实数据集上进行了比较，展示了新算法能有效地 提高标签传播算法的社区发现精度。 关键词：数据挖掘；网络数据；社区发现；标签传播算法；聚类集成；基聚类；模块度；加权度量 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2018)06−0994−05 中文引用格式：张美琴, 白亮, 王俊斌. 基于加权聚类集成的标签传播算法[J]. 智能系统学报, 2018, 13(6): 994–998. 英文引用格式：ZHANG Meiqin, BAI Liang, WANG Junbin. Label propagation algorithm based on weighted clustering ensemble[J]. CAAI transactions on intelligent systems, 2018, 13(6): 994–998. Label propagation algorithm based on weighted clustering ensemble ZHANG Meiqin1 ，BAI Liang2 ，WANG Junbin1 (1. College of Computer Science and Technology, Shanxi University, Taiyuan 030006, China; 2. Key Laboratory of Symbol Computation and Knowledge Engineering (Shanxi University), Ministry of Education, Taiyuan 030006, China) Abstract: Label propagation algorithm (LPA) is one of the high-efficiency community detection algorithms for processing large-scale network data. It has attracted much attention because of its nearly linear time complexity with the number of nodes. However, in the algorithm, the label of each node depends on the labels of its neighbor nodes, which makes the iteration speed and clustering performance of the algorithm very sensitive to the order of label information update; this influences the accuracy and stability of the community detection result. To solve this problem, a new LPA is proposed based on weighted clustering ensemble. The new algorithm runs the LPAs many times to obtain several partition results, which can be regarded as a base clustering set. Furthermore, the modularity measure is used to evaluate the importance of each clustering. Based on the evaluation results, a weighted similarity measure is defined between nodes to obtain a weighted similarity matrix of pairwise nodes. Finally, hierarchical clustering on the similarity matrix is used to obtain a final community division result. In the experimental analysis, the new algorithm is compared with several other improved LPAs on five real representative network datasets. The experimental results show that the new algorithm is more effective for improving the community detection accuracy. Keywords: data mining; network data; community detection; label propagation algorithm; clustering ensemble; base clustering; modularity measure; weighted measure 现实世界中存在各种各样的复杂系统，网络 则是这些系统的普遍存在形式，如人际关系网， 收稿日期：2018−06−04. 网络出版日期：2018−07−17. 基金项目：国家自然科学基金项目（61773247）. 通信作者：张美琴. E-mail：landian.zhang@qq.com. 第 13 卷第 6 期 智 能 系 统 学 报 Vol.13 No.6 2018 年 12 月 CAAI Transactions on Intelligent Systems Dec. 2018
第6期 张美琴，等：基于加权聚类集成的标签传播算法 ·995· 因特网、大型电力网格等。为了能清晰地发现网 次LPA结果的重要性，加强了每个基聚类的有效 络中的信息，需要挖掘网络的社区结构。社区结 性，最后采用聚类集成技术实现提高社区发现结 构是复杂网络的一个重要特性，整个网络是由若 果的稳定性和准确性。 干个“社区”构成的，每个社区内部的节点之间的 连接相对非常紧密，而各个社区之间的连接却比 1基于加权聚类集成的标签传播算法 较稀疏。利用网络的拓扑结构，能更准确地发现 1.1 标签传播算法(LPA) 社区。网络社区结构的发现，有助于更好地了解 标签传播算法(LPA)的核心思想是每个节点 社区结构、理解网络的功能和特性、预测复杂网 的标签通过其出现次数最多的邻居节点的标签来 络的行为，在社会网络、信息推荐、精准营销等领 决定自身的标签，通过不断迭代，节点的标签变 域都有很大的应用价值。 化达到稳定后，将最终具有相同标签的节点划分 目前提出的代表性社区发现算法有潜在空间 为一个社区，完成社区划分。其最大的特点是简 算法四、谱聚类算法)、模块最大化算法4、标签 单、高效，缺点是每次迭代结果不稳定，准确率不 传播算法等，根据不同的科学需要，这些算法有 高。在文献「10]中给出了该算法的具体描述如下。 不同的社区定义或类定义网。其中，由Raghavan等o 1)为所有节点初始化一个唯一的标签，每个 在2007年提出的标签传播算法(LPA)由于其拥 标签代表一个社区。 有线性时间复杂度而被广泛应用于处理大规模网 2)产生随机遍历顺序遍历所有节点，每个节 络。然而，该算法中每个节点的标签更新取决于 点选择其出现次数最多的邻居节点标签来更新自 其邻居节点，更新效果受节点初始输入和标签更 身的标签，以此达到标签的传播。 新顺序的影响。因此LPA算法的最终结果存在 3)若存在节点的邻居节点标签数出现多个最 不确定性，影响了社区划分的准确性和稳定性。 大值，则随机选其中一个最大值所对应的标签来 基于LPA结果的不稳定性，众多学者提出了对 LPA的改进算法I-1。例如，Barber等在2009 更新该节点的标签。重复2)，直到标签更新稳 年提出使用模块度最大化的变体作为约束的 定，停止迭代。 4)将具有相同标签的节点划分为一个社区。 LPA算法(LPAm),该算法将标签传播算法转化为 等价优化问题处理；Liu等在2010年针对LPAm 该算法的时间复杂度为O(n+m)O(n+m),其 算法可能会出现社区划分陷入局部极大值的问 中，n代表为结点分配标签的时间，m代表每次迭 题，提出一种改进的标签传播算法(LPAm+),其核 代更新的时间。 心是将LPAm算法与多步贪婪凝聚算法(MSG)融 1.2基于加权聚类集成的标签传播算法 合，最大限度地减少模块空间，避免出现局部最 在介绍本文提出的新算法之前，首先给出网 大值；Xie等在2011年发表的文献[13]中提出了 络、模块度、基聚类集、节点加权相似性度量等相 针对提高社区检测速度和提高社区质量的改进 关概念如下。 LPA算法；He等n在2014年使用了PageRank来 定义1给定G=(WE)是一个无向无权的复 衡量网络中节点的重要性，提出了基于节点重要 杂网络，其中V={w,2,…,yl。若a,代表顶点，与 性的LPA算法；Sun等在2015年提出基于中心 顶点v,的关系，令a表示为 的标签传播算法(CenLP),通过高密度邻居节点的 1,(,v》∈E a=10,(,〉年E (1) 相似性使节点按特定顺序更新标签；Li等在 20I7年提出改进的LPA算法Stepping LPA-S算 则称(a)axn为G的邻接矩阵，记作A(G)。 法，它通过模块度和目标函数DN来度量节点或 定义261设G=(WE)是一个含有k个社区的 子网的相似性，其标签通过相似性进行传播，最 无向无权网络，令e,为k×k维矩阵中的元素，并令 终获得了比LPA更准确的结果。 b,=∑，e,则模块度记作 虽然已有多种改进的LPA算法被提出，但依 0=∑e-) (2) 然存在稳定性和精确性不高的问题-1。聚类集 式中：e,表示网络中连接第i个社区和第j个社区 成技术正是解决聚类算法结果不稳定和不精确的 的节点的边数在所有边中所占的比例，b表示与 重要方法之一。目前，多种聚类集成技术也已得 第个社区中的节点相连的边数在所有边中所占 到发展9-训。因此，本文通过将聚类集成技术与 的比例。Q值越大，表示社区划分结果越稳定，所 标签传播算法融合，提出了基于加权聚类集成的 对应的社区发现算法效果也更具代表性。 标签传播算法。该算法通过引入模块度来评估每 定义3设X={P,P2,…,P}是对图G中的节
因特网、大型电力网格等。为了能清晰地发现网 络中的信息，需要挖掘网络的社区结构。 社区结 构是复杂网络的一个重要特性，整个网络是由若 干个“社区”构成的，每个社区内部的节点之间的 连接相对非常紧密，而各个社区之间的连接却比 较稀疏。利用网络的拓扑结构，能更准确地发现 社区。网络社区结构的发现，有助于更好地了解 社区结构、理解网络的功能和特性、预测复杂网 络的行为，在社会网络、信息推荐、精准营销等领 域都有很大的应用价值。 目前提出的代表性社区发现算法有潜在空间 算法[1] 、谱聚类算法[2-3] 、模块最大化算法[4-8] 、标签 传播算法等，根据不同的科学需要，这些算法有 不同的社区定义或类定义[9]。其中，由 Raghavan 等 [10] 在 2007 年提出的标签传播算法 (LPA) 由于其拥 有线性时间复杂度而被广泛应用于处理大规模网 络。然而，该算法中每个节点的标签更新取决于 其邻居节点，更新效果受节点初始输入和标签更 新顺序的影响。因此 LPA 算法的最终结果存在 不确定性，影响了社区划分的准确性和稳定性。 基于 LPA 结果的不稳定性，众多学者提出了对 LPA 的改进算法[11−18]。例如，Barber 等 [11]在 2009 年提出使用模块度最大化的变体作为约束的 LPA 算法 (LPAm)，该算法将标签传播算法转化为 等价优化问题处理； Liu 等 [12]在 2010 年针对 LPAm 算法可能会出现社区划分陷入局部极大值的问 题，提出一种改进的标签传播算法 (LPAm+)，其核 心是将 LPAm 算法与多步贪婪凝聚算法 (MSG) 融 合，最大限度地减少模块空间，避免出现局部最 大值； Xie 等在 2011 年发表的文献[13]中提出了 针对提高社区检测速度和提高社区质量的改进 LPA 算法； He 等 [14]在 2014 年使用了 PageRank 来 衡量网络中节点的重要性，提出了基于节点重要 性的 LPA 算法； Sun 等 [15]在 2015 年提出基于中心 的标签传播算法 (CenLP)，通过高密度邻居节点的 相似性使节点按特定顺序更新标签； Li 等 [16]在 2017 年提出改进的 LPA 算法 Stepping LPA-S 算 法，它通过模块度和目标函数 DN 来度量节点或 子网的相似性，其标签通过相似性进行传播，最 终获得了比 LPA 更准确的结果。 虽然已有多种改进的 LPA 算法被提出，但依 然存在稳定性和精确性不高的问题[17−18]。聚类集 成技术正是解决聚类算法结果不稳定和不精确的 重要方法之一。目前，多种聚类集成技术也已得 到发展[19−21]。因此，本文通过将聚类集成技术与 标签传播算法融合，提出了基于加权聚类集成的 标签传播算法。该算法通过引入模块度来评估每 次 LPA 结果的重要性，加强了每个基聚类的有效 性，最后采用聚类集成技术实现提高社区发现结 果的稳定性和准确性。 1 基于加权聚类集成的标签传播算法 1.1 标签传播算法 (LPA) 标签传播算法 (LPA) 的核心思想是每个节点 的标签通过其出现次数最多的邻居节点的标签来 决定自身的标签，通过不断迭代，节点的标签变 化达到稳定后，将最终具有相同标签的节点划分 为一个社区，完成社区划分。其最大的特点是简 单、高效，缺点是每次迭代结果不稳定，准确率不 高。在文献[10]中给出了该算法的具体描述如下。 1) 为所有节点初始化一个唯一的标签，每个 标签代表一个社区。 2) 产生随机遍历顺序遍历所有节点，每个节 点选择其出现次数最多的邻居节点标签来更新自 身的标签，以此达到标签的传播。 3) 若存在节点的邻居节点标签数出现多个最 大值，则随机选其中一个最大值所对应的标签来 更新该节点的标签。重复 2)，直到标签更新稳 定，停止迭代。 4) 将具有相同标签的节点划分为一个社区。 该算法的时间复杂度为 O(n+m)O(n+m)，其 中，n 代表为结点分配标签的时间，m 代表每次迭 代更新的时间。 1.2 基于加权聚类集成的标签传播算法 在介绍本文提出的新算法之前，首先给出网 络、模块度、基聚类集、节点加权相似性度量等相 关概念如下。 G = ⟨V,E⟩ V = {v1, v2, ··· , vn} ai j vi vj ai j 定义 1 给定 是一个无向无权的复 杂网络，其中 。 若 代表顶点 与 顶点 的关系，令 表示为 ai j = { 1, ⟨ vi , vj ⟩ ∈ E 0, ⟨ vi , vj ⟩ < E (1) 则称 (ai j)n×n为 G 的邻接矩阵，记作 A(G)。 G = ⟨V,E⟩ k ei j k×k bi = ∑ j ei j 定义 2 [6] 设 是一个含有 个社区的 无向无权网络，令 为 维矩阵中的元素，并令 ，则模块度记作 Q = ∑ i (eii −b 2 i ) (2) ei j i j bi i Q 式中： 表示网络中连接第 个社区和第 个社区 的节点的边数在所有边中所占的比例， 表示与 第 个社区中的节点相连的边数在所有边中所占 的比例。 值越大，表示社区划分结果越稳定，所 对应的社区发现算法效果也更具代表性。 定义 3 设 X = {P1, P2, ··· , PT } 是对图 G 中的节 第 6 期 张美琴，等：基于加权聚类集成的标签传播算法 ·995·
·996· 智能系统学报 第13卷 点集V执行T次标签传播算法得到的结果集，其 ∫1，Xa+Xm 式中：X,X)={0,X=X# (i,jen,teT).Xn 中，P,代表第次执行标签传播算法的聚类结果。 为第次标签传播算法中第个节点所对应的标签。 第次运行标签传播算法所产生的单个聚类结 根据定义4可知，用模块度Q值来衡量每个基 果为一个基聚类，将多个标签传播算法的结果融合 聚类的质量，将不同质量的基聚类分配不同的权 来代替单个标签传播算法的结果，使用聚类集成技 值，使得新的相似性度量能更有效地反映节点在 术从结果集X中发现最一致的结果。然而，聚类集 基聚类空间下的相似性。 成的结果会受到单个基聚类质量的影响，为了提高 基于以上定义，提出基于加权聚类集成的标 聚类结果的稳定性，因此提出加权相似性度量。 签传播算法。用LPA算法对复杂网络G进行T次 定义4设P,为基聚类，X为基聚类集矩阵， 聚类，聚类产生的结果形成一个n×T的基聚类集 Q,为衡量基聚类P有效性的模块度值，则节点i与 矩阵，然后根据定义4融入模块度在基聚类集上 节点的加权相似性度量定义为 求出一个n×n维的节点加权相似性矩阵，最后通 Si,)= 2】 Q(Xi X) (3) 过层次聚类算法产生最终的结果。其聚类过程如 图1所示。 原始网络的稀疏 矩阵形式 LPA LPA 聚类集成 LPA LP 层次聚类 果 n×T矩阵 最终聚 n×n相似性矩阵 类结果 T次LPA结果作为基聚类 图1算法框架 Fig.1 The framework of the proposed algorithm 具体算法步骤如下： 赛关系构成的网络，共包含115支球队。Dol- 输入网络G: phins数据集是由新西兰的一个海豚群体组成的 输出节点集V的划分结果。 海豚关系网，网络中的边表示两只海豚之间的频 1)对网络G中的节点集V执行T次标签传播算 繁接触次数。Karate数据集是一个由34个空手 法运算，每次产生一列社区划分结果，最终形成 道俱乐部成员之间的关系构成的社会网络，网络 n×T的基聚类集矩阵x。 中的边表示两个俱乐部成员经常出现在俱乐部活 2)根据定义2计算每次LPA结果的模块度 动之外的其他场合的次数。Wb数据集是某网站 值，2，来作为对应基聚类的权重。 上所有网页构成的关系网，节点代表网页，边代 3)根据定义4计算节点之间的加权相似性矩 表超链接。Word数据集是名词形容词搭配网 阵S。 络。数据集的信息描述如表1所示。 4)对加权相似度矩阵S“采用层次聚类方法 表1数据集描述 (linkage)产生最终的社区划分结果。 Table 1 Description of network data sets 数据集 2实验分析 #vertex #edges #Classes football 115 613 2.1实验数据 karate 34 78 2 为了验证本文提出的算法的有效性，选取了 dolphins 62 159 2 5个不同规模的真实网络数据集，分别为foot- word 112 425 2 ball、dolphins、karate、web、word数据集。其中 web 75 113 football数据集是由美国橄榄球联赛中球队的比 5
V T Pt t 点集 执行 次标签传播算法得到的结果集，其 中， 代表第 次执行标签传播算法的聚类结果。 t X 第 次运行标签传播算法所产生的单个聚类结 果为一个基聚类，将多个标签传播算法的结果融合 来代替单个标签传播算法的结果，使用聚类集成技 术从结果集 中发现最一致的结果。然而，聚类集 成的结果会受到单个基聚类质量的影响，为了提高 聚类结果的稳定性，因此提出加权相似性度量。 Pt X Qt Pt i j 定义 4 设 为基聚类， 为基聚类集矩阵， 为衡量基聚类 有效性的模块度值，则节点 与 节点 的加权相似性度量定义为 S w (i, j) = ∑n i, j=1 ∑T t=1 Qtσ(Xit,Xjt) (3) σ(Xit,Xjt) = { 1, Xit , Xjt 0, Xit = Xjt (i, j ∈ n,t ∈ T),Xit t i 式中： 为第 次标签传播算法中第 个节点所对应的标签。 根据定义 4 可知，用模块度 Q 值来衡量每个基 聚类的质量，将不同质量的基聚类分配不同的权 值，使得新的相似性度量能更有效地反映节点在 基聚类空间下的相似性。 G T n×T n×n 基于以上定义，提出基于加权聚类集成的标 签传播算法。 用 LPA 算法对复杂网络 进行 次 聚类，聚类产生的结果形成一个 的基聚类集 矩阵，然后根据定义 4 融入模块度在基聚类集上 求出一个 维的节点加权相似性矩阵，最后通 过层次聚类算法产生最终的结果。其聚类过程如 图 1 所示。 具体算法步骤如下： 输入 网络 G ； 输出 节点集 V 的划分结果。 G V T n×T X 1) 对网络 中的节点集 执行 次标签传播算 法运算，每次产生一列社区划分结果，最终形成 的基聚类集矩阵 。 Qt 2) 根据定义 2 计算每次 LPA 结果的模块度 值， 来作为对应基聚类的权重。 S w 3) 根据定义 4 计算节点之间的加权相似性矩 阵 。 S w 4) 对加权相似度矩阵 采用层次聚类方法 (linkage) 产生最终的社区划分结果。 2 实验分析 2.1 实验数据 为了验证本文提出的算法的有效性，选取了 5 个不同规模的真实网络数据集，分别为 football、dolphins、karate、web、word 数据集。其中 football 数据集是由美国橄榄球联赛中球队的比 赛关系构成的网络，共包含 115 支球队。Dolphins 数据集是由新西兰的一个海豚群体组成的 海豚关系网，网络中的边表示两只海豚之间的频 繁接触次数。Karate 数据集是一个由 34 个空手 道俱乐部成员之间的关系构成的社会网络，网络 中的边表示两个俱乐部成员经常出现在俱乐部活 动之外的其他场合的次数。Web 数据集是某网站 上所有网页构成的关系网，节点代表网页，边代 表超链接。Word 数据集是名词形容词搭配网 络。数据集的信息描述如表 1 所示。 表 1 数据集描述 Table 1 Description of network data sets 数据集 #vertex #edges #Classes football 115 613 12 karate 34 78 2 dolphins 62 159 2 word 112 425 2 web 75 113 5 原始网络的稀疏 矩阵形式 LPA LPA n×T 矩阵 n×n 相似性矩阵 聚类集成 层次聚类 最终聚 类结果 ··· ··· T 次 LPA 结果作为基聚类 一 次 LPA 结 果 一 次 LPA 结 果 图 1 算法框架 Fig. 1 The framework of the proposed algorithm ·996· 智 能 系 统 学 报 第 13 卷
第6期 张美琴，等：基于加权聚类集成的标签传播算法 ·997· 2.2评价指标 文也对运行不同次标签传播算法得出的最终社区 本文使用标准互信息(normalized mutual in- 划分结果进行了实验，实验结果表明，随着运行 formation,NM⑩)和调整兰德系数(adjusted rand In- 次数的增多，社区划分结果越稳定，且运行到一 dex,ARI)来评价最终聚类质量。 定次数时，社区划分效果均能趋于平稳。综上所 标准互信息NMⅫ)和调整兰德系数(ARI)常 述，本文提出的基于加权聚类集成的标签传播算 常用于社区划分质量的评价，能有效衡量给定社 法较其他算法在NMI和ARI上都有良好的表现， 区划分结果与真实网络划分的相似程度。 且算法本身表现也收敛，因此新算法能在社区划 NMI的定义为 分的结果上更接近于实际社区划分情况，提高了 2乃 Cii'n 社区发现的精确性。 ciilog 1=1 bi.b' 表2不同算法的NMI值比较 NMI(A.B)= * (4) b:log(n b Table 2 Clustering results of different algorithms with re- spect to NMI =1 式中：n代表节点数量，C代表混合矩阵，C矩阵中 数据集 传播算法LPA LPA_S LPAmLPAm+BGLL 的元素C代表既在真实社区A中的社区又在发现 Football 0.903 0.7040.7800.8740.8930.885 社区B中的j社区的节点总数，cA(cB)是社区A(B)的 dolphins 0.602 0.4130.5330.4470.4540.445 社区数目，b,表示矩阵C中第行元素的总和，b表 karate 0.733 0.4310.8370.6260.609 0.587 示矩阵C中第j列元素的总和。对存在真实社区 web 0.152 0.1280.0980.135 0.147 0.045 划分的网络，NM具有较好的辨识能力，NM值 word 0.119 0.085 0 0.0210.065 越大，则表明发现的社区结构划分结果越准确， 0.008 当发现的社区划分与真实社区完全一致时， 表3不同算法的ARI值比较 NMI达到最大值I。 Table 3 Clustering results of different algorithms with re- ARI的定义为 spect to ARI ARI= ro-r: (5) 数据集传播算法LPALPA_S LPAmLPAm+BGLL 2 Football 0.820 0.4250.4440.739 0.8110.804 dolphins 0.569 0.2550.3180.223 0.2480.280 n-。ARI的取值范围为-1，，其值越大 2n2 karate 0.772 0.3650.8820.4700.4460.462 意味着社区发现结果与真实情况越吻合。 web 0.016-0.011-0.0010.0260.037 -0.014 2.3实验结果分析 word 0.001-0.0020-0.010-0.001-0.009 为了测试新算法的有效性，使其分别与5个 3结束语 现有的LPA的改进算法在真实数据集上进行了 比较测试，这些LPA的改进算法包括LPAI1 本文主要利用聚类集成技术对LPA进行了 LPA SI6、LPAm!、LPAm+2、BGLL8。分别从 改进，提出了基于加权聚类集成的标签传播算 NMⅡ和ARI两个评价指标将新算法与经典算法 法。该算法首先执行多次LPA产生多个标签传 进行了比较，每个算法在每个数据集上都运行了 播结果作为基聚类集，并计算出每次LPA结果的 100次，实验结果如表2~3所示。通过对实验结 模块度值作为对应基聚类的权重，然后计算出融 果的对比分析显示，新算法的实验效果在foot- 入权值后的节点相似性矩阵，最后采用层次聚类 ball、dolphins、web、word数据集上都有明显的提 方法得到最终的社区划分结果。在真实网络数据 高，即其社区划分更接近于真实社区的划分，尤 集上的实验结果表明，新算法在NMI和ARI两个 其是在dolphins数据集，该算法的效果较其他算 评价指标上效果都有所提高，表明新算法可以获 法高出l0%多。虽然在karate数据集上新算法的 得更好的社区发现结果，提高了社区发现的精确性。 实验结果并非最高，但也表明新算法在大部分数 据集上的表现仍然具有很大优势。同时，对于算 参考文献： 法本身的性能的测评中，由于该算法只涉及因运 [1]SARKAR P,MOORE A W.Dynamic social network ana- 行LPA算法次数的差异所形成的基聚类集的维 lysis using latent space models[J].ACM sigkdd explora- 度的不同对算法最终结果所造成的影响，因此本 tions newsletter,2005.7(2):31-40
2.2 评价指标 本文使用标准互信息 (normalized mutual information， NMI) 和调整兰德系数 (adjusted rand Index，ARI) 来评价最终聚类质量。 标准互信息 (NMI) 和调整兰德系数 (ARI) 常 常用于社区划分质量的评价，能有效衡量给定社 区划分结果与真实网络划分的相似程度。 NMI 的定义为 NMI(A,B) = −2 ∑cA i=1 ∑cB j=1 ci j ·log ci j · n bi · b ′ j ∑cA i=1 bi log(bi n )+ ∑cB j=1 bj′log( b ′ j n ) (4) n C C Ci j A i B j cA(cB) A(B) bi C i bj′ C j 式中： 代表节点数量， 代表混合矩阵， 矩阵中 的元素 代表既在真实社区 中的 社区又在发现 社区 中的 社区的节点总数， 是社区 的 社区数目， 表示矩阵 中第 行元素的总和， 表 示矩阵 中第 列元素的总和。对存在真实社区 划分的网络，NMI 具有较好的辨识能力，NMI 值 越大，则表明发现的社区结构划分结果越准确， 当发现的社区划分与真实社区完全一致时， NMI 达到最大值 1。 ARI 的定义为 ARI = r0 −rs r1 −r2 2 −rs (5) r0 = ∑ i j[ ni j 2 ] r1 = ∑ i [ bi 2 ] r2 = ∑ j [ b ′ j 2 ] r3 = 2r1r2 n(n−1) 式中： ， ， ， 。 ARI 的取值范围为[−1,1]，其值越大 意味着社区发现结果与真实情况越吻合。 2.3 实验结果分析 为了测试新算法的有效性，使其分别与 5 个 现有的 LPA 的改进算法在真实数据集上进行了 比较测试，这些 LPA 的改进算法包括 LPA[ 1 0 ] 、 LPA_S[16] 、LPAm[11] 、LPAm+[12] 、BGLL[18]。分别从 NMI 和 ARI 两个评价指标将新算法与经典算法 进行了比较，每个算法在每个数据集上都运行了 100 次，实验结果如表 2~3 所示。通过对实验结 果的对比分析显示，新算法的实验效果在 football、dolphins、web、word 数据集上都有明显的提 高，即其社区划分更接近于真实社区的划分，尤 其是在 dolphins 数据集，该算法的效果较其他算 法高出 10% 多。虽然在 karate 数据集上新算法的 实验结果并非最高，但也表明新算法在大部分数 据集上的表现仍然具有很大优势。同时，对于算 法本身的性能的测评中，由于该算法只涉及因运 行 LPA 算法次数的差异所形成的基聚类集的维 度的不同对算法最终结果所造成的影响，因此本 文也对运行不同次标签传播算法得出的最终社区 划分结果进行了实验，实验结果表明，随着运行 次数的增多，社区划分结果越稳定，且运行到一 定次数时，社区划分效果均能趋于平稳。综上所 述，本文提出的基于加权聚类集成的标签传播算 法较其他算法在 NMI 和 ARI 上都有良好的表现， 且算法本身表现也收敛，因此新算法能在社区划 分的结果上更接近于实际社区划分情况，提高了 社区发现的精确性。 3 结束语 本文主要利用聚类集成技术对 LPA 进行了 改进，提出了基于加权聚类集成的标签传播算 法。该算法首先执行多次 LPA 产生多个标签传 播结果作为基聚类集，并计算出每次 LPA 结果的 模块度值作为对应基聚类的权重，然后计算出融 入权值后的节点相似性矩阵，最后采用层次聚类 方法得到最终的社区划分结果。在真实网络数据 集上的实验结果表明，新算法在 NMI 和 ARI 两个 评价指标上效果都有所提高，表明新算法可以获 得更好的社区发现结果，提高了社区发现的精确性。 参考文献： SARKAR P, MOORE A W. Dynamic social network analysis using latent space models[J]. ACM sigkdd explorations newsletter, 2005, 7(2): 31–40. [1] 表 2 不同算法的 NMI 值比较 Table 2 Clustering results of different algorithms with respect to NMI 数据集 传播算法 LPA LPA_S LPAm LPAm+ BGLL Football 0.903 0.704 0.780 0.874 0.893 0.885 dolphins 0.602 0.413 0.533 0.447 0.454 0.445 karate 0.733 0.431 0.837 0.626 0.609 0.587 web 0.152 0.128 0.098 0.135 0.147 0.045 word 0.119 0.085 0 0.021 0.065 0.008 表 3 不同算法的 ARI 值比较 Table 3 Clustering results of different algorithms with respect to ARI 数据集 传播算法 LPA LPA_S LPAm LPAm+ BGLL Football 0.820 0.425 0.444 0.739 0.811 0.804 dolphins 0.569 0.255 0.318 0.223 0.248 0.280 karate 0.772 0.365 0.882 0.470 0.446 0.462 web 0.016 -0.011 -0.001 0.026 0.037 -0.014 word 0.001 -0.002 0 -0.010 -0.001 -0.009 第 6 期 张美琴，等：基于加权聚类集成的标签传播算法 ·997·
·998· 智能系统学报 第13卷 [2]ZARE H,SHOOSHTARI P,GUPTA A,et al.Data reduc- centrality-based label propagation algorithm for com- tion for spectral clustering to analyze high throughput flow munity detection in networks[J].Physica A:statistical cytometry data[J].BMC bioinformatics.2010.11:403. mechanics and its applications,2015,436:767-780. [3]SHI Jianbo,MALIK J.Normalized cuts and image seg- [16]LI Wei,HUANG Ce,WANG Miao,et al.Stepping com- mentation[J].IEEE transactions on pattern analysis and munity detection algorithm based on label propagation machine intelligence,2000,22(8):888-905. and similarity[J].Physica A:statistical mechanics and its [4]DJIDJEV H N,ONUS M.Scalable and accurate graph applications,.2017,472:145-155. clustering and community structure detection[J].IEEE [17]SUBELJ L,BAJEC M.Unfolding communities in large transactions on parallel and distributed systems,2013, complex networks:combining defensive and offensive la- 24(5):1022-1029. bel propagation for core extraction[J].Physical review E. [5]DUCH J,ARENAS A.Community detection in complex 2011,83(3:036103. networks using extremal optimization[J].Physical review [18]BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et E,2005,72(2):027104. al.Fast unfolding of communities in large networks[J] [6]NEWMAN M E J.Fast algorithm for detecting com- Journal of statistical mechanics:theory and experiment. munity structure in networks[J].Physical review E,2004, 2008(10):10008. 69(6):066133. [19]ELHADARY R S,TOLBA A S,ELSHARKAWY MA. [7]GIRVAN M,NEWMAN M E J.Community structure in et al.An efficient and robust combined clustering tech- social and biological networks[J.Proceedings of the na- nique for mining in large spatial databases[C]//Proceed- tional academy of sciences of the United States of Amer- ica,2002,9912):7821-7826. ings of 2007 International Conference on Computer En- [8]NEWMAN M E J.Modularity and community structure in gineering and Systems.Cairo,Egypt,2007:439-445. [20]FRED A L N,JAIN A K.Data clustering using evidence networks[J].Proceedings of the national academy of sci- ences of the United States of America,2006,103(23): accumulation[C]//Proceedings of the 16th International 8577-8582. Conference on Pattern Recognition.Quebec City,Quebec. [9]TANG Lei,WANG Xufei,LIU Huan.Community detec- Canada,2002:276-280. tion via heterogeneous interaction analysis[J].Data mining [21]YANG Yan,KAMEL M S.An aggregated clustering ap- and knowledge discovery,2012,25(1):1-33. proach using multi-ant colonies algorithms[J].Pattern re- [10]RAGHAVAN UN.ALBERT R.KUMARA S.Near lin- c0 gnition,2006,39(7):1278-1289. ear time algorithm to detect community structures in 作者简介： large-scale networks[J].Physical review E.2007,76(3): 张美琴，女，1992年生，硕士研究 036106. 生，主要研究方向为社区检测。 [11]BARBER M J,CLARK J W.Detecting network com- munities by propagating labels under constraints[J].Phys- ical review E,2009,80(2):026129. [12]LIU X,MURATA T.Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J].Physica A:statistical mechanics and its ap- plications,.2010,389(7:1493-1500. 白亮.男，1982年生，副教授，博 [13]XIE Jierui,SZYMANSKI B K.Community detection us- 士，主要研究方向为数据挖掘、机器 ing a neighborhood strength driven label propagation al- 学习。 gorithm[C]//Proceedings of 2011 IEEE Network Science Workshop.West Point,NY,USA:IEEE,2011:188-195. [14]HE Miao,LENG Mingwei,LI Fan,et al.A node import- ance based label propagation approach for community de- tection[M]//SUN Fuchun,LI Tianrui,LI Hongbo.Know- 王俊斌，男，1994年生，硕士研究 ledge Engineering and Management:Proceedings of the 生，主要研究方向为数据挖掘。 Seventh International Conference on Intelligent Systems and Knowledge Engineering,Beijing,China,Dec 2012 (ISKE 2012).Berlin Heidelberg:Springer,2014: 249-257. [15]SUN Heli,LIU Jiao,HUANG Jianbin,et al.CenLP:a
ZARE H, SHOOSHTARI P, GUPTA A, et al. Data reduction for spectral clustering to analyze high throughput flow cytometry data[J]. BMC bioinformatics, 2010, 11: 403. [2] SHI Jianbo, MALIK J. Normalized cuts and image segmentation[J]. IEEE transactions on pattern analysis and machine intelligence, 2000, 22(8): 888–905. [3] DJIDJEV H N, ONUS M. Scalable and accurate graph clustering and community structure detection[J]. IEEE transactions on parallel and distributed systems, 2013, 24(5): 1022–1029. [4] DUCH J, ARENAS A. Community detection in complex networks using extremal optimization[J]. Physical review E, 2005, 72(2): 027104. [5] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical review E, 2004, 69(6): 066133. [6] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the national academy of sciences of the United States of America, 2002, 99(12): 7821–7826. [7] NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of the national academy of sciences of the United States of America, 2006, 103(23): 8577–8582. [8] TANG Lei, WANG Xufei, LIU Huan. Community detection via heterogeneous interaction analysis[J]. Data mining and knowledge discovery, 2012, 25(1): 1–33. [9] RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical review E, 2007, 76(3): 036106. [10] BARBER M J, CLARK J W. Detecting network communities by propagating labels under constraints[J]. Physical review E, 2009, 80(2): 026129. [11] LIU X, MURATA T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J]. Physica A: statistical mechanics and its applications, 2010, 389(7): 1493–1500. [12] XIE Jierui, SZYMANSKI B K. Community detection using a neighborhood strength driven label propagation algorithm[C]//Proceedings of 2011 IEEE Network Science Workshop. West Point, NY, USA: IEEE, 2011: 188–195. [13] HE Miao, LENG Mingwei, LI Fan, et al. A node importance based label propagation approach for community detection[M]//SUN Fuchun, LI Tianrui, LI Hongbo. Knowledge Engineering and Management: Proceedings of the Seventh International Conference on Intelligent Systems and Knowledge Engineering, Beijing, China, Dec 2012 (ISKE 2012). Berlin Heidelberg: Springer, 2014: 249–257. [14] [15] SUN Heli, LIU Jiao, HUANG Jianbin, et al. CenLP: a centrality-based label propagation algorithm for community detection in networks[J]. Physica A: statistical mechanics and its applications, 2015, 436: 767–780. LI Wei, HUANG Ce, WANG Miao, et al. Stepping community detection algorithm based on label propagation and similarity[J]. Physica A: statistical mechanics and its applications, 2017, 472: 145–155. [16] ŠUBELJ L, BAJEC M. Unfolding communities in large complex networks: combining defensive and offensive label propagation for core extraction[J]. Physical review E, 2011, 83(3): 036103. [17] 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): 10008. [18] ELHADARY R S, TOLBA A S, ELSHARKAWY M A, et al. An efficient and robust combined clustering technique for mining in large spatial databases[C]//Proceedings of 2007 International Conference on Computer Engineering and Systems. Cairo, Egypt, 2007: 439–445. [19] FRED A L N, JAIN A K. Data clustering using evidence accumulation[C]//Proceedings of the 16th International Conference on Pattern Recognition. Quebec City, Quebec, Canada, 2002: 276–280. [20] YANG Yan, KAMEL M S. An aggregated clustering approach using multi-ant colonies algorithms[J]. Pattern recognition, 2006, 39(7): 1278–1289. [21] 作者简介： 张美琴，女，1992 年生，硕士研究 生，主要研究方向为社区检测。 白亮，男，1982 年生，副教授，博 士，主要研究方向为数据挖掘、机器 学习。 王俊斌，男，1994 年生，硕士研究 生，主要研究方向为数据挖掘。 ·998· 智 能 系 统 学 报 第 13 卷