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

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

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

，选取两个基准社会网络

［１４］

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

［１］

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

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

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

网络。Ｆｏｏｔｂａｌｌ

足球联赛中有若干支球队

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

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

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

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

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

３　结束语

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

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

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

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

（聚类精度±标准差）

算法

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

ｃｌｕｂ网络

±

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

±

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

Ｆｏｏｔｂａｌｌ网络

Ｋ±

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

±

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

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

０．００００

１．３７９８

０．８７９０

参考文献：

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

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

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

ｔｈｅｏｖｅｒｌａｐ唱

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

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

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

ｔｈｅＮａｔｉｏｎａｌＡｃａｄ …… 此处隐藏：1060字，全部文档内容请下载后查看。喜欢就下载吧 ……