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

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

计算机应用研究

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

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

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

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

１０００７２）

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

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

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

１

１

１

２

３

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

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

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

１

１

１

２

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

３

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

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

０　引言

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

［１～５］

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

［６］

研究热潮。

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

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

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

Ｔ

［７，８］［９］

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

Ｔ

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

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

－１／２

（Ｄ－Ａ）Ｄ

－１／２

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

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

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

［７，８］

与规范截方法

［９］

相结

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

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

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

方法和基于ＰＳＯ＋Ｋ唱ｍｅａｎｓ聚类的谱方法，并在人工随机网络和两个现实社会网络上实验验证了新方法的有效性。

１　算法描述

１畅１　基于社会生态学的粒子群优化算法ＰＳＯ聚类算法ｚａｔｉｏｎ，ＰＳＯ）

（ｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉ唱

［１０］

主要是在群体的集群行为和自组织原则指导下

的随机搜索和优化技术，它强调分布式、相对简单主体之间直接或间接的交互作用，具有很强的适应性和鲁棒性，被广泛用于解决搜索和优化问题ＰＳＯ提出了标准

般形式下聚类算法ＰＳＯ，算法与用于对一般数据集的聚类。２００３年，Ｍｅｒｗｅ等人

［１１］

Ｋ唱ｍｅａｎｓ算法相结合的混合聚类方法，同时最早提出了一。

假设在Ｄ维搜索空间中有ｎ个粒子组成的一个群体，第ｉ个粒子在Ｄ维空间中的位置表示为ｘｉ＝

（ｘｉ１，ｘｉ２，…，ｘｉＤ）。第ｉ个粒子经历过的最好位置（有最好适应度）记为Ｐｉ＝（ｐｉ１，ｐｉ２，…，ｐｉＤ），每个粒子的飞行速度为Ｖｉ＝（ｖｉ１，ｖｉ２，…，ｖｉＤ）；在整个群体中，所有粒子经历过的最好位置为Ｐｇ＝（ｐｇ１，ｐｇ２，…，ｐｇＤ）。每一代粒子根据下面的公式更新自己的速度和位置：

ｖｋｉｄ

＋１

＝ｗｖｋｉｄ＋ｃ１ξ（ｐｋｉｄ

－ｘｋｉｄ）＋ｃ２η（ｐｋｇｄ－ｘｋｉｄ）

（１）ｘｋｉｄ

＋１

＝ｘｋｉｄ＋ｖｋｉｄ

＋１

（２）

其中：ｗ为惯性权重；ｃ１和ｃ２为学习因子；ξ，η∈Ｕ［０，１］是在［０，１］ＰＳＯ内均匀分布的伪随机数聚类算法中粒子的适应度函数为。

Ｊｅ：

Ｊ∑Ｎｊ＝ｃ１［∑橙ｚｐ∈Ｃｊｄ（ｚｐ，ｍｊ）］／

｜Ｃｊ｜ｅ＝

Ｎｃ

（３）ｍｊ＝

１ｎｊ

橙ｚ∑ｐ∈Ｃｊｚｐ

（４）

ｄ（ｚｐ，ｍｊ）＝

∑ｂ

ｋ＝１

（ｚｐｋ－ｍｊｋ）２

（５）

其中：Ｎｂ为数据的维数；Ｎｃ为聚簇的个数；ｚｐ表示样本的数据向量；ｎｊ表示簇Ｃｊ中样本的个数；ｍｊ表示簇Ｃｊ中样本的均值（中心）。

基本ａ）初始化粒子群ＰＳＯ聚类算法的流程如下，随机选择簇的中心并赋值给各个粒子：随机产生粒子的速度，ｒｅｐｅａｔ

。

（３）计算各个粒子的适应值ｂ）对每个粒子按照最小距离原则对数据进行划分，更新个体极值。

，按式ｃｄ）根据各个粒子的个体极值找出全局极值和全局极值位置。

ｅ）按速度（式（１））更新粒子的速度，并把它限制在ｖｍａｘ内。ｕｎｔｉｌ）按位置（式（２））更新粒子的位置ｆ）输出最优粒子的位置即最优的满足终止条件

。Ｎｃ个聚类中心。算法的终止条件可以是达到一定的循环次数，簇的中心变化很小或簇的成员不再改变用Ｋ唱ＰＳＯｍｅａｎｓ与方法得到一组簇的中心Ｋ唱ｍｅａｎｓ算法相结合的混合算法的基本思路是先

。

，然后在粒子群初始化时将其赋值给某个粒子，其余粒子随机初始化，最后用标准ＰＳＯ聚类算法完成聚类。该方法可简记为ＰＳＯ＋Ｋ唱ｍｅａｎｓ方法。１畅２　复杂网络聚类与空间数据聚类有很多相似之处基于ＰＳＯ的复杂网络聚类算法

。目前应

用空间数据聚类来探测复杂网络的簇结构主要分为两大步骤ａ）将原问题转换为数值聚类问题，即要把网络中节点间的联

：系在特征向量空间中表述出来，谱方法正好可以实现这一转换；ｂ）对转换后的数据进行聚类并将聚类结果还原为相应的社团结构。根据上述思路本文提出了两种基于ＰＳＯ聚类的复杂网络簇结构算法。其算法的基本思想是首先应用谱方法中的Ａ唱ｃｕｔ方法或Ｎ唱ｃｕｔ方法将复杂网络聚类问题转换为空间数据聚类问题；通过应用Ａ唱ｃｕｔ方法或Ｎ唱ｃｕｔ方法将复杂网络中的簇结构信息转换为由非平凡特征向量构成的空间数据集。该空间数据集中的每个数据样本对应原复杂网络中的一个节点。通过对该空间数据集中数据样本的聚类得出复杂网络中节点的簇信息，最终完成复杂网络聚类。

ＰＳＯ聚类的复杂网络簇结构探测算法的基本步骤如下对于某复杂网络Ｇ（Ｖ，Ｅ，Ｗ），给定一个簇的数目：

ｋ，基于中Ｄａ为对角矩阵）由连接权矩阵，ｄＷ得出网络的度矩阵Ｄ＝（ｄｉ）ｎ×ｎ。其

ｉ为第ｉ个节点的度，ｎ为节点数。注意，这里考虑的均为无向网络聚类问题ｂ）用谱方法将寻找复杂网络的簇结构问题转换为数据的

。

。设Ａ为网络的邻接矩阵。对于平均截方法，具体就是计算Ｍ＝Ｄ－Ａ的前ｋ－１个非平凡特征向量ｅ１，ｅ１，…，

ｅｋ－１（ｅｉ∈Ｒ

ｎ×１

，ｉ＝１，…，ｋ－１）并组成矩阵Ｅ。对于规范截方

法，具体就是计算Ｍ＝Ｄ－１／２

（Ｄ－Ａ）Ｄ

－１／２

的前ｋ－１个非平凡

特征向量ｅｋ－１（ｅｉ∈Ｒ

ｎ×１

１，ｅ１，…，ｅ，ｉ＝１，…，ｋ－１）并组成矩

阵Ｅ。由Ｅ的行向量得到ｎ个数据向量形式的待聚类样本。Ｋ唱ｍｅａｎｓｃ）用基于聚类算法对上面得到的数据样本集ＰＳＯ的聚类算法，如基本ＰＳＯＥ聚类算法或进行聚类。

ＰＳＯ＋

２　实验与分析

为了定量地分析和比较本文提出的复杂网络聚类算法的性能，分别选取了不同的基准数据集与基于Ｋ唱ｍｅａｎｓ聚类的复杂网络聚类算法，从聚类精度和算法稳定性两个方面进行对比实验。

首先采用已知簇结构的随机网络测试所选择算法的聚类精度和稳定性。该实验方法被相关工作广泛采用，已成为测试复杂网络聚类算法准确性的一种基准方法

［１，１２，１３］

。已知簇结

构的随机网络定义为ＲＮ（Ｃ，ｓ，ｄ，ｐｉｎ）。其中，Ｃ表示网络簇的个数；ｓ表示每个簇包含节点的个数；ｄ表示网络中节点的平均度；ｐｉｎ表示簇内连接密度（即簇内连接总数与网络连接总数的比值），ｐｉｎ值越大，随机网络的簇结构越明显，反之簇结构越模糊。特别地，当ｐｉｎ＜０．５时，认为该随机网络不具有簇结构。一个随机网络被正确聚类当且仅当预定义的Ｃ个网络簇被全部正确识别，且没有某个簇被进一步分割为多个子簇。图１和２给出了实验结果，这里所采用的随机网络是被普遍采用的基准随机网络ＲＮ（４，３２，１６，ｐｉｎ），ｐｉｎ分别取０．１，０．２，０．３，０．４，０．５，０．６，０．７，０．８，０．９，１．０。在图１和２中，ｙ轴分别表示聚类精度和聚类精度的标准差，曲线上的每个数据点是采用不同算法进行１００次随机实验得到的平均值。

从图１可以看出，对于随机网路，在网络簇结构比较明显的情况下Ｎ（ｐｉｎ＞０．６），基于ＰＳＯ聚类的谱方法（Ａ唱构不明显的情况下唱ｃｕｔ方法）均能得到很好的聚类精度（ｐｉｎ＜０．５），所有算法的聚类精度都很低（＞９８％）；在网络簇结ｃｕｔ方法和，

但是与基于Ｋ唱ｍｅａｎｓ的谱方法相比，基于ＰＳＯ聚类的谱方法的聚类精度更高。从图２可以看出，基于ＰＳＯ＋Ｋ唱ｍｅａｎｓ聚类的谱方法在获得最高的聚类精度的同时聚类精度的标准差最低，说明基于ＰＳＯ＋Ｋ唱ｍｅａｎｓ聚类的谱方法稳定性最强。

第６期李峻金，等：一种新的复杂网络聚类算法 ２０　　　９９

Ｋａｒａｔｅ为进一步测试本文算法的性能ｃｌｕｂ它是网络

，选取两个基准社会网络

［１４］

ｃｌｕｂ网络，２０世纪和Ｆｏｏｔｂａｌｌ７０年代初期网络

［１］

Ｚａｃｈａｒｙ进行实验用了两年的时间。图３是Ｋａｒａｔｅ

观察得到的美国一所大学中的空手道俱乐部成员间的相互社会关系网络。在Ｚａｃｈａｒｙ的调查过程中，该俱乐部的主管与校

长之间因是否提高俱乐部收费的问题产生了争执，结果该俱乐部分裂成了两个分别以主管和校长为核心的小俱乐部。

网络。Ｆｏｏｔｂａｌｌ

足球联赛中有若干支球队

，网络的节点代表一只足球队，两个节点之间的边表示两支球队之间进行过一场比赛。联赛中存在若干的联盟，每个球队都属于其中一个联盟，联盟内部球队

间进行的比赛次数多于联盟之间的球队间进行的比赛次数。该网络数据收集于Ｎｅｗｍａｎ２０００年赛季的真实比赛情况，（边），包含了收集整理而成１２个联盟，。存在Ｆｏｏｔｂａｌｌ１１５支球队网络如图（节点４所示）及由。

６１６Ｇｉｒｖａｎ场比赛与

实验结果如表１所示。从表１可以看出，对于Ｋａｒａｔｅｃｌｕｂ网络和ｃｕｔＦｏｏｔｂａｌｌ网络，基于ＰＳＯ聚类的谱方法（Ａ唱ｃｕｔ差。方法方法和Ｎ唱

其中基于基本）同样获得了较高的聚类精度和较低的聚类精度标准ＰＳＯ聚类的谱方法在Ｋａｒａｔｅｃｌｕｂ网络上的聚类精度最高ＦｏｏｔｂａｌｌＰＳＯ＋Ｋ唱网络上聚类精度最高（＞９８％），基于ｍｅａｎｓ聚类的谱方法得到的聚类精度的标准差均最低（ＰＳＯ＞９２％）。＋Ｋ唱ｍｅａｎｓ在三种方法中聚类的谱方法在，基于。

３　结束语

复杂网络聚类是最重要的复杂网络分析方法之一，复杂网络簇结构探测已成为一个具有挑战性的研究课题。尽管人们已经投入了大量的、艰苦的研究工作并取得诸多令人鼓舞的研

究结果，但复杂网络聚类问题还远未被很好地解决。本文首先介绍了复杂网络聚类中的两种谱方法（Ａ唱ｃｕｔ方法和Ｎ唱ｃｕｔ方法）和两种空间聚类方法（ＰＳＯ聚类算法和ＰＳＯ＋Ｋ唱ｍｅａｎｓ聚类算法）；然后提出和分析了两种基于ＰＳＯ聚类的复杂网络簇ｍｅａｎｓ结构探测算法聚类的谱方法，即基于；最后在ＰＳＯ聚类的谱方法和基于１０个随机复杂网络和两个基准ＰＳＯ＋Ｋ唱

社会网络上进行实验，验证了两种算法在复杂网络聚类分析中的有效性。从实验结果可知，通过将ＰＳＯ聚类算法与谱方法相结合，有效提高了谱方法在复杂网络聚类中的聚类精度和稳定性。

表１　不同算法在基准社会网络上１００次随机实验结果

（聚类精度±标准差）

算法

唱ｍｅａｎｓ８６．Ａ１１７６唱Ｋａｒａｔｅｃｕｔ

ｃｌｕｂ网络

±

９３．Ｎ６４７１唱ｃｕｔ

±

８１．Ａ２０００唱ｃｕｔ

Ｆｏｏｔｂａｌｌ网络

Ｋ±

８２．Ｎ４１７４唱ｃｕｔ

±

８．００１７７．７８９６６．００６７７．０６８２ＰＳＯ９８．９１１８±９８．５８８２±８１．５２１７±８１．９２１７±３．１３０８２．４０６７３．９７８０４．１７２６ＰＳＯ＋Ｋ唱ｍｅａｎｓ

９７．０５８８±９７．０５８８±９２．５１３０±９２．６８７０±０．００００

０．００００

１．３７９８

０．８７９０

参考文献：

［１］ＧＩＲＶＡＮＭ，ＮＥＷＭＡＮＭＥＪ．Ｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅｉｎｓｏｃｉａｌａｎｄ

ｂｉｏｌｏｇｉｃａｌＳｃｉｅｎｃｅｏｆｎｅｔｗｏｒｋｓＵＳＡ，２００２，［Ｊ］．Ｐｒｏｃｅｅｄｉｎｇｓ９９（１２）：７８２１唱ｏｆ７８２６．

ｔｈｅＮａｔｉｏｎａｌＡｃａｄｅｍｙｏｆ［２］ＧＵＩＭＥＲＡＲ，ＡＭＡＲＡＬＬＡＮ．Ｆｕｎｃｔｉｏｎａｌｃａｒｔｏｇｒａｐｈｙｏｆｃｏｍｐｌｅｘ［３］ＰＡＬＬＡｍｅｔａｂｏｌｉｃＧ，ｎｅｔｗｏｒｋｓＤＥＲＥＮＹＩ［Ｊ］．Ｉ，ＮａｔｕｒｅＦＡＲＫＡＳ，２００５，Ｉ，４３３ｅｔａｌ（７０２８）．Ｕｎｃｏｖｅｒｉｎｇ：８９５唱９００．

ｔｈｅｏｖｅｒｌａｐ唱

ｐｉｎｇ［Ｊ］．ｃｏｍｍｕｎｉｔｙＮａｔｕｒｅ，２００５，ｓｔｒｕｃｔｕｒｅｓ４３５（７０４３）ｏｆｃｏｍｐｌｅｘ：８１４唱８１８．

ｎｅｔｗｏｒｋｓｉｎｎａｔｕｒｅａｎｄｓｏｃｉｅｔｙ［４］ＷＩＬＫＩＮＳＯＮＤＭ，ＨＵＢＥＲＭＡＮＢＡ．Ａｍｅｔｈｏｄｆｏｒｆｉｎｄｉｎｇｃｏｍｍｕ唱

ｎｉｔｉｅｓｏｆＳｃｉｅｎｃｅｏｆｒｅｌａｔｅｄｏｆＵＳＡｇｅｎｅｓ，２００４，［Ｊ］．Ｐｒｏｃｅｅｄｉｎｇｓ１０１（１）：５２４１唱ｏｆ５２４８．

ｔｈｅＮａｔｉｏｎａｌＡｃａｄｅｍｙ［５］ＲＡＤＩＣＣＨＩＦ，ＣＡＳＴＥＬＬＡＮＯＣ，ＣＥＣＣＯＮＩＦ，ｅｔａｌ．Ｄｅｆｉｎｉｎｇａｎｄ

ｔｉｏｎａｌｉｄｅｎｔｉｆｙｉｎｇＡｃａｄｅｍｙｃｏｍｍｕｎｉｔｉｅｓｏｆＳｃｉｅｎｃｅｉｎｎｅｔｗｏｒｋｓｏｆＵＳＡ［，２００４，Ｊ］．Ｐｒｏｃｅｅｄｉｎｇｓ１０１（９）：２６５８唱ｏｆｔｈｅ２６６３．Ｎａ唱

［６］杨博，刘大有，ＬＩＵＪｉ唱ｍｉｎｇ，等．复杂网络聚类方法［Ｊ］．软件学报，

２００９，２０（１）：５４唱６６．

［７］ＦＩＥＤＬＥＲＭ．Ａｌｇｅｂｒａｉｃｃｏｎｎｅｃｔｉｖｉｔｙｏｆｇｒａｐｈｓ［Ｊ］．Ｃｚｅｃｈｏｓｌｏｖａｋｉａｎ

ＭａｔｈｅｍａｔｉｃａｌＪｏｕｒｎａｌ，１９７３，２３（２）：２９８唱３０５．［８］

ＦＩＥＤＬＥＲＭ．ＡｐｒｏｐｅｒｔｙｏｆｅｉｇｅｎｖｅｃｔｏｒｓｏｆｎｏｎｎｅｇａｔｉｖｅｓｙｍｍｅｔｒｉｃＭａｔｈｅｍａｔｉｃａｌｍａｔｒｉｃｅｓａｎｄｉｔｓＪｏｕｒｎａｌａｐｐｌｉｃａｔｉｏｎ，１９７５，ｔｏ２５ｇｒａｐｈ（４）：６１９唱ｔｈｅｏｒｙ６３７．

［Ｊ］．Ｃｚｅｃｈｏｓｌｏｖａｋｉａｎ［９］ＳＨＩＪｉａｎ唱ｂｏ，ＭＡＬＩＫＪ．Ｎｏｒｍａｌｉｚｅｄｃｕｔｓａｎｄｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎ［Ｊ］．

ＩＥＥＥＴｒａｎｓｏｎＰａｔｔｅｒｎＡｎａｌｙｓｉｓａｎｄＭａｃｈｉｎｅＩｎｔｅｌｌｉｇｅｎｔ，２０００，２２（８）：８８８唱９０４．

［１０］ＫＥＮＮＥＤＹＪ，ＥＢＥＲＨＡＲＴＲ．Ｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］／／

１９４２唱Ｐｒｏｃｏｆ１９４８．

ＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＮｅｕｒａｌＮｅｔｗｏｒｋｓ．１９９５：

［１１］ＶａｎｄｅｒＭＥＲＷＥＤＷ，ＥＮＧＥＬＢＲＥＣＨＴＡＰ．Ｄａｔａｃｌｕｓｔｅｒｉｎｇｕｓｉｎｇ

ｔｉｏｎａｒｙｐａｒｔｉｃｌｅＣｏｍｐｕｔａｔｉｏｎｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎ．２００３：２１５唱［Ｃ］２２０．

／／ＰｒｏｃｏｆＩＥＥＥＣｏｎｇｒｅｓｓｏｎＥｖｏｌｕ唱

［１２］ＮＥＷＭＡＮＭＥＪ．Ｆａｓｔａｌｇｏｒｉｔｈｍｆｏｒｄｅｔｅｃｔｉｎｇｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅｉｎ［１３］ＮＥＷＭＡＮｎｅｔｗｏｒｋｓ［Ｊ］Ｍ．ＰｈｙｓｉｃａｌＥＪ，ＧＩＲＶＡＮＲｅｖｉｅｗＭ．Ｅ，２００４，Ｆｉｎｄｉｎｇ６９ａｎｄ（６）ｅｖａｌｕａｔｉｎｇ：０６６１３３唱１唱ｃｏｍｍｕｎｉｔｙ

１１．

０２６１１３唱ｓｔｒｕｃｔｕｒｅ１唱ｉｎ１５．

ｎｅｔｗｏｒｋｓ［Ｊ］．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，２００４，６９（２）：［１４］ＺＡＣＨＡＲＹＷＷ．Ａｎｉｎｆｏｒｍａｔｉｏｎｆｌｏｗｍｏｄｅｌｆｏｒｃｏｎｆｌｉｃｔａｎｄｆｉｓｓｉｏｎ

３３ｉｎ（４）ｓｍａｌｌ：４５２唱ｇｒｏｕｐｓ４７３．

［Ｊ］．ＪｏｕｒｎａｌｏｆＡｎｔｈｒｏｐｏｌｏｇｉｃａｌＲｅｓｅａｒｃｈ，１９７７，

本文来源：https://www.bwwdw.com/article/eage.html