结构图聚类是针对无向图,根据顶点的相似度定义,将图顶点分类。结构图聚类算法作为数据挖掘和机器学习的基础算法之一,为海量数据的研究与分析提供一种基本方法,被广泛应用于现实生活的各个领域,如:生态环境、交通管理、模式识别、生物基因网络以及电子商务等,其运行效率决定了众多图分析算法的应用范围,是研究者最关心的热点话题之一。本文重点研究结构图的高效聚类问题,具体研究内容如下。首先,针对现有结构图聚类算法在处理大规模图数据时需大量计算边的相似度导致运行效率低的问题,提出了一种高效聚类算法CUWG。该算法通过状态转换图快速产生规模较小的聚类,合并这些小的聚类从而产生聚类结果,并且在计算边的相似度之前,先通过简单的相似边界判断,减少一些边相似度的计算,从而提高算法的运行效率。其次,针对CUWG算法处理极大规模图数据时大量计算边的相似度和频繁查询合并聚类导致运行效率较低的问题,结合并行处理的想法,提出优化方法CUWG+。相似度的计算和聚类的查询都是针对单个边或节点的操作,利用这种特性,提出将算法并行化处理,同时计算多条边的相似度,并行查询不同节点所属的聚类,从而提高算法的运行效率。最后,通过在多个真实数据集上进行实验测试,分析实验结果,验证了本文提出算法的高效性。