点击次数：

论文类型：会议论文

发表时间：2006-11-01

页面范围：1

关键字：复杂网络;群落结构;聚类算法;公共邻居;谱分析

摘要：现实世界网络的研究发现,无论是社会网络还是其它类型的网络都表现出群落结构 (community structure)。群落结构是指顶点组中有密集的关联边,而组与组之间的关联边的密集程度则要低的多。这些结构在实际中有重要意义。例如,如果将引文网络分割为若干群组,分别代表特定的研究兴趣领域,对此现象的研究对分析哪些学科是一个研究集团格外重要。传统上的提取网络中群落结构的方法是聚类分析。近来,Newman提出了一种快速聚类算法, 算法的思想是每一时间步合并使得模块性的增加量△Q最大的两个类。算法的优点是速度快,比其他算法快上千倍。但是算法也有一些致命的缺陷,例如算法仅仅考虑当前两个类合并后模块性的增加量,而没有考虑下一步合并的影响,所以很容易陷入局部最优解。因此,我们给出了基于公共邻居的一类快速聚类算法。算法的思想是:每个时间步,两个类的合并不取决于△Q,而是取决于两个类公共邻居的多少,即集团之间的集聚性。模块性指标Q等指标表明,该算法的聚类准确性比Newman的快速想法更好,不同数据集上的试验证实了这一点。