现实世界中存在着诸多复杂的网络结构,为了揭示隐藏在复杂结构中有价值的信息,网络结构图的思想引起了研究人员的注意。图是网络结构建模的方法,现实生活中很多实体都可以抽象为图的节点,而实体间的关系抽象为边,这样,对复杂网络结构的分析就转化为对图结构的分析。图聚类作为图数据挖掘的一种重要的分析技术,目的是在复杂的图中寻找出关联紧密的子图,使得子图内的节点之间相似性较大,而子图与子图之间的节点具有较弱的相似性。目前图聚类的算法研究有很多,如Kernighan-Lin算法、基于Laplace矩阵的传统谱平分法、GN算法(Girvan和Newman提出的基于边阶数的聚类算法)及Newman算法等,但是这些算法都存在一些缺陷,Kernighan-Lin算法和基于Laplace矩阵的传统谱平分法只有在图能很明显地分成两个子图的情况下才有效；GN算法是它在反复去边的过程中,一直到没有剩余的边才停止,这样下来,没有直接给出聚类的最终结果,还需再做进一步的分析和判断才能得到最终的聚类结果。总之,现有的图聚类算法存在以下问题：(1)当数据量很大时,图的规模会非常大,在相似性度量方面,计算量会很大,导致运行时间会非常长；(2)图结构本身的复杂性影响聚类效果。基于以上问题,本文将图着色理论应用到图聚类中。图着色问题是一个被广泛研究的组合优化问题,它在对行政区域的划分、资源分配、离散规划、网络的自动检测等方面有着广泛的应用。解决图着色问题有很多种方法,如盲目搜索、启发式算法以及贪心算法等。本文采用的是贪心算法,这是因为在处理海量数据时,贪心算法相比其它算法,运行时间几乎以毫秒为单位,这样,算法的时间复杂度就在某种程度上就大大降低了。本文首次将图着色理论应用到图聚类中,首先采用贪心算法的图着色理论进行初步聚类,得到初步聚类结果；然后通过对贪心算法的图着色理论进行改进,目的是对初步着色结果进行重新调整,使结果更加符合聚类要求,从而达到更好的聚类效果。论文的主要工作包括以下几个方面：(1)通过系统介绍现阶段图聚类技术的研究现状,总结了图聚类技术的特点、现实意义以及目前研究面临的问题。(2)分析了图着色理论应用的领域,总结了图着色问题的三种定义,分别为图的顶点着色、图的边着色和图的全着色,其中后两种都可以转化为图的顶点着色来分析。本文主要对图的顶点着色进行重点描述。(3)采用贪心算法的图着色理论,聚类后的结果并不是唯一的。因此,本文引入评价聚类结果好坏的指标DunnG,然后将DunnG进行扩展,又提出一种新的评价指标Distinctness,与DunnG结合起来衡量聚类效果的好坏。(4)算法选取UCI数据集中不同类型的六种数据进行实验验证,实验结果与经典算法k-means方法以及改进前的算法进行比较,证明本文改进后的算法可以达到较高的聚类质量。