论文部分内容阅读
近年来，随着社会网络、通信网络、生物网络等应用的快速发展，其上产生的图数据呈现暴发性增长。图聚类是图数据分析的有力技术之一，但是，对于大规模图数据来说，当前的大多数图聚类算法在时间和空间方面的扩展性表现很差，其主要原因是目前算法要发现图中所有的簇。实际上，许多聚类应用只需要最佳簇形成的子集合，而不是整个图中的所有簇。针对这种情况，Macropol和Singh于2010年提出了一种新的技术TopGC（Top Graph Clusters），它概率性的找到基于联接的大型图中联接良好的类似小集团的最佳簇。算法具备固有的可平行性，并且随着图规模的变大以线性时间运行。然而TopGC自身也存在不足。首先，由于TopGC是从种子顶点出发依据单层邻接点进行聚类，会使产生的聚类结果过度细化。其次，对于大规模的图，TopGC的时间和空间效率有待于进一步提高。为此，本文提出了一种快速的基于k层邻接点的分布式图聚类算法ITGC（Improved Top Graph Clusters），主要研究内容有：1)提出k层邻接点的概念，根据k层邻接点的相似性和顶点间边权大小找到所需数目的联接良好的类似小集团的最佳簇，从而避免依据单层邻接点进行聚类所导致的聚类细化。2)对于更大规模的基于联接的图，由于TopGC等技术没有采用分布式并行处理技术，在时间和空间方面并不能很好地满足实际应用的需求。本文进一步提出一种基于连通性判断搜索最小代价割集的方法，使用最小代价割集对基于联接的图进行分片，降低图分片的关联性，对基于联接的大型图进行分布式聚类。3)由于也可能找到一些重叠簇，找到所有簇之后，有一个后期处理步骤。本文提出了当两个簇的重叠比例超过给定阈值时，以簇得分的定义为标准保留一个最佳簇。4)采用Java语言设计程序进行了实验测试，通过实际数据集上的大量实验表明，本文所提出的聚类方法较传统方法在时间和空间效率上具有较大优势，并且可以发现更高质量的簇。