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

。

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

。目前应

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

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

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

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

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

。

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

ｅｋ－１（ｅｉ∈Ｒ

ｎ×１

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

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

（Ｄ－Ａ）Ｄ

－１／２

的前ｋ－１个非平凡

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

ｎ×１

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

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

ＰＳＯ＋

２　实验与分析

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

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

［１，１２，１３］

。已知簇结

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

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

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

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

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

，选取两个基准社会网络

［１４］

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

［１］

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

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

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

网络。Ｆｏｏｔｂａｌｌ

足球联赛中有若干支球队

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

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

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

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

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

３　结束语

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

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

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

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

（聚类精度±标准差）

算法

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

ｃｌｕｂ网络

±

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

±

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

Ｆｏｏｔｂａｌｌ网络

Ｋ±

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

±

８．００１７７．７８９６６．００６７７．０６８２ＰＳＯ９８．９１１８± …… 此处隐藏：1689字，全部文档内容请下载后查看。喜欢就下载吧 ……