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

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

计算机应用研究

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

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

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

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

１０００７２）

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

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

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

１

１

１

２

３

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

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

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

１

１

１

２

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

３

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

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

０　引言

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

［１～５］

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

［６］

研究热潮。

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

　　收 …… 此处隐藏：808字，全部文档内容请下载后查看。喜欢就下载吧 ……