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

时间：2026-01-27

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

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

１　算法描述

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

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

［１０］

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

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

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

［１１］

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

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

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

ｖｋｉｄ

＋１

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

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

（１）ｘｋｉｄ

＋１

＝ｘｋｉｄ＋ｖｋｉｄ

＋１

（２）

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

Ｊｅ：

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

｜Ｃｊ｜ｅ＝

Ｎｃ

（３）ｍｊ＝

１ｎｊ

橙ｚ∑ｐ∈Ｃｊｚｐ

（４）

ｄ（ｚｐ，ｍｊ）＝

∑ｂ

ｋ＝１

（ｚｐｋ－ｍｊｋ）２

（５）

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

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

。

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

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

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

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

。

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

。目前应

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

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

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

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

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

。

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

ｅｋ－１（ｅｉ∈Ｒ

ｎ×１

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

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

（Ｄ－Ａ）Ｄ

－１／２

的前ｋ－１个非平凡