高效的大型图聚类方法研究  

Study of Efficient Clustering Algorithm on Large Graphs

作　　者：王浩成[1] 马静[1] 

机构地区：[1]辽宁大学信息学院,沈阳110036

出　　处：《小型微型计算机系统》2013年第6期1417-1423,共7页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60703068)资助

摘　　要：对于大规模的图数据,当前的图聚类算法的时间和空间扩展性较差,且倾向于细粒度的簇.本文提出k层邻接点概念,从而避免单层邻接点导致的聚类细化.提出一种基于割集的分布式聚类算法,通过连通性判断搜索最小代价割集,从而降低图分片的关联性,提高算法的并行度和可扩展性.通过实际数据集上的大量实验表明,本文所提出的聚类方法较传统方法在时间和空间效率上具有较大优势,并且可以发现更高质量的簇.For large-scale graph data, most of algorithms of graph clustering suffered from poor scalablity on the complexity of time and space, and were prone to over-fine-grained clusters. In this paper the concept called k-layers neighbors is proposed to avoid over- fine-grained clusters caused by single-layer neighborhood. A distributed clustering algorithm based on cut set is proposed. It adopt a searching strategy of minimum cost cut set based on graph connectivity, to reduce the association of graph fragments and improve par- allelism and scalablity of clustering. With the extensive experiments on real data, it shows that the proposed algorithm achieves the better efficiency of time and space and the effective of clusters.

关 键 词：图聚类 k层邻接点集合 分布式聚类 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]