一种新的复杂网络聚类算法

第２７卷第６期２０１０年６月　

计算机应用研究

ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ

Ｖｏｌ．２７Ｎｏ．６Ｊｕｎ．２０１０

一种新的复杂网络聚类算法

李峻金，向　阳，牛　鹏，刘丽明，芦英明

１０００７２）

摘　要：揭示网络簇结构的复杂网络聚类方法研究具有重要的理论意义和应用价值。应用两种谱方法将复杂网络簇结构发现问题转换为空间数据聚类问题，并将粒子群聚类算法应用到对复杂网络簇结构的探测，提出了两种新的结合粒子群聚类的复杂网络簇结构探测算法。最后在两类复杂网络上进行实验并对实验结果进行了比较分析，提出的新算法在聚类准确性方面效果更好。

关键词：复杂网络；网络聚类；网络簇结构；谱方法；粒子群聚类算法

中图分类号：ＴＰ３０１畅６　　　文献标志码：Ａ　　　文章编号：１００１唱３６９５（２０１０）０６唱２０９７唱０３ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１唱３６９５．２０１０．０６．０２９

１

１

１

２

３

（１．西安通信学院，西安７１０１０６；２．中国人民解放军７２５５６部队，济南２５００２２；３．中国特种车辆研究所，北京

（１．Ｘｉ’ａｎＣｏｍｍｕｎｉｃａｔｉｏｎｓＩｎｓｔｉｔｕｔｅ，Ｘｉ’ａｎ７１０１０６，Ｃｈｉｎａ；２．ＰＬＡ７２５５６Ｕｎｉｔ，Ｊｉｎａｎ２５００２２，Ｃｈｉｎａ；３．Ｃｈｉｎａ’ｓＳｐｅｃｉａｌＶｅｈｉｃｌｅＲｅｓｅａｒｃｈＩｎｓｔｉｔｕｔｅ，Ｂｅｉｊｉｎｇ１０００７２，Ｃｈｉｎａ）

ＬＩＪｕｎ唱ｊｉｎ，ＸＩＡＮＧＹａｎｇ，ＮＩＵＰｅｎｇ，ＬＩＵＬｉ唱ｍｉｎｇ，ＬＵＹｉｎｇ唱ｍｉｎｇ

１

１

１

２

Ｎｅｗｃｏｍｐｌｅｘｎｅｔｗｏｒｋｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ

３

Ａｂｓｔｒａｃｔ：Ｎｅｔｗｏｒｋｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓｗｈｉｃｈａｉｍｔｏｄｉｓｃｏｖｅｒａｌｌｎａｔｕｒａｌｎｅｔｗｏｒｋｃｏｍｍｕｎｉｔｉｅｓｆｒｏｍｇｉｖｅｎｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓａｒｅｆｕｎｄａｍｅｎｔａｌｌｙｉｍｐｏｒｔａｎｔｆｏｒｂｏｔｈｔｈｅｏｒｅｔｉｃａｌｒｅｓｅａｒｃｈｅｓａｎｄｐｒａｃｔｉｃａｌａｐｐｌｉｃａｔｉｏｎｓ．Ｔｈｉｓｐａｐｅｒｕｓｅｄｔｗｏｓｐｅｃｔｒａｌｐａｒｔｉｔｉｏｎｍｅｔｈｏｄｓｉｎｏｒｄｅｒｔｏｔｒａｎｓｆｏｒｍｔｈｅｃｏｍｍｕｎｉｔｉｅｓｄｅｔｅｃｔｉｎｇｉｎｔｏｃｌｕｓｔｅｒａｎａｌｙｓｉｓｐｒｏｂｌｅｍ．Ｔｈｅｎ，ａｐｐｌｉｅｄＰＳＯｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓｔｏｄｅｔｅｃｔｃｌｕｓｔｅｒｓｔｒｕｃｔｕｒｅ．ＰｒｏｐｏｓｅｄｔｗｏｎｅｗｎｅｔｗｏｒｋｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓｃｌｏｓｅｌｙｃｏｍｂｉｎｅｄｗｉｔｈＰＳＯａｎｄｄｅｍｏｎｓｔｒａｔｅｄｔｈｅａｖａｉｌａｂｉｌｉｔｙｏｆｔｈｅａｌｇｏｒｉｔｈｍｉｎｔｗｏｄｉｆｆｅｒｅｎｔｋｉｎｄｓｏｆｎｅｔｗｏｒｋｄａｔｕｍ．Ｉｔａｌｓｏｍａｋｅｓｔｈｅｃｏｍｐａｒｉｓｏｎａｎｄａｎａｌｙｓｉｓｏｆｔｈｅｅｘｐｅｒｉ唱ｍｅｎｔａｌｒｅｓｕｌｔｓａｎｄｏｂｔａｉｎｓａｃｏｎｃｌｕｓｉｏｎｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｓｐｒｅｓｅｎｔｆｉｔｎｅｓｓｉｎｃｌｕｓｔｅｒｉｎｇｖｅｒａｃｉｔｙ．

Ｋｅｙｗｏｒｄｓ：ｃｏｍｐｌｅｘｎｅｔｗｏｒｋ；ｎｅｔｗｏｒｋｃｌｕｓｔｅｒｉｎｇ；ｎｅｔｗｏｒｋｃｌｕｓｔｅｒｓｔｒｕｃｔｕｒｅ；ｓｐｅｃｔｒａｌｐａｒｔｉｔｉｏｎ；ＰＳＯｃｌｕｓｔｅｒｉｎｇ

０　引言

现实世界中的诸多系统都以网络形式存在，并表现出很高的复杂性。网络簇结构（ｎｅｔｗｏｒｋｃｌｕｓｔｅｒｓｔｒｕｃｔｕｒｅ）是复杂网络最普遍和最重要的拓扑结构属性之一，具有同簇节点相互连接

［１～５］

密集、异簇节点相互连接稀疏的特点。为了揭示出复杂网络中真实存在的网络簇结构，人们提出了多种复杂网络聚类方法。复杂网络聚类方法的研究对分析复杂网络的拓扑结构、理解复杂网络的功能、发现复杂网络中的隐藏规律以及预测复杂网络的行为不仅具有十分重要的理论意义，而且在社会网、生物网和万维网中具有广泛的应用前景。由于复杂网络聚类研究具有重要的理论意义和应用价值，它不仅成为计算机领域中最具挑战性的基础性研究课题之一，也吸引了来自物理、数学、生物、社会学和复杂性科学等众多领域的研究者，掀起了一股

［６］

研究热潮。

谱方法最早用于解决图分割（ｇｒａｐｈｐａｒｔｉｔｉｏｎ）问题，近年来被应用到复杂网络聚类。谱方法采用二次型优化技术最小化预定义的“截”函数。当一个网络被划分为两个子网络时，“截”即指子网间的连接密度。具有最小“截”的划分被认为是最优的网络划分。针对不同问题，研究者们提出了不同的

　　收稿日期：２００９唱１１唱１０；修回日期：２００９唱１２唱２９　　

“截”函数，如针对分布式系统负载平衡提出的平均截（ａｖｅｒａｇｅｃｕｔ，Ａ唱ｃｕｔ）ｃｕｔ，Ｎ唱ｃｕｔ）

Ｔ

［７，８］［９］

以及针对图像分割提出的规范截（ｎｏｒｍａｌｉｚｅｄ

Ｔ

等。采用矩阵分析技术，谱方法将求解最小“截”

问题转换为求解带约束的二次型优化问题：ｍｉｎ｛（ＸＭＸ）／（ＸＸ）｝。其中，向量Ｘ表示网络划分，Ｍ表示对称半正定矩阵。对于平均截，Ｍ＝Ｄ－Ａ表示网络的拉普拉斯矩阵，其中Ｄ表示由节点度构成的对角矩阵，Ａ为网络的邻接矩阵；对于规范截，Ｍ＝Ｄ

－１／２

（Ｄ－Ａ）Ｄ

－１／２

表示网络的规范化拉普拉斯矩

阵；对于其他截函数，Ｍ是拉普拉斯矩阵的不同变体。由拉格朗日方法，以上约束二次型的近似最优解（即网络的近似最优划分）可以通过计算Ｍ的第二小特征向量求得。谱方法本质上是一种二分法，在每次二分过程中，网络被分割成两个近似平衡的子网络。当网络中含有多个簇时，谱方法递归地分割现存的子网络，直到满足预先定义的停止条件为止。谱方法具有严密的数学理论，已发展成数据聚类的一种重要方法（称为谱聚类法），被广泛应用于图分割和空间点聚类等领域。

本文研究了复杂网络聚类算法中谱方法的基本原理，其主要工作是将粒子群优化算法应用于复杂网络聚类，通过ＰＳＯ聚类算法和谱方法中的平均截方法

［７，８］

与规范截方法

［９］

相结

合，提出了两种新的复杂网络聚类算法，即基于ＰＳＯ聚类的谱

　　作者简介：李峻金（１９８５唱），男，安徽阜阳人，硕士研究生，主要研究方向为人工智能与聚类分析（ｔｓｐａｃｅ１９８５＠ｇｍａｉｌ．ｃｏｍ）；向阳（１９６８唱），女，湖南长沙人，副教授，硕士，主要研究方向为计算机与数据库安全；牛鹏（１９８５唱），男，河南安阳人，硕士研究生，主要研究方向为模式识别与图像处理；刘丽明（１９８３唱），女，河北邢台人，助理工程师，硕士，主要研究方向为网络安全；芦英明（１９８５唱），男，陕西西安人，助理工程师，主要研究方向为装备系统工程．

２０９８ 计算机应用研究　第２７卷

方法和基于ＰＳＯ＋Ｋ唱ｍｅａｎｓ聚类的谱方法，并在人 …… 此处隐藏：1922字，全部文档内容请下载后查看。喜欢就下载吧 ……