聚类(或分类)是数学、计算科学、管理科学等领域的热门研究话题,并且在诸如模式识别、数据分析、通信、生物以及商务等领域有着广泛的应用.图聚类,就是应用图理论方法对图(顶点集)进行分类,是数据聚类领域一种很重要的变体.与普通的数值聚类不同的是,基于图理论的聚类具有其本身的特殊性,可以用图来表示数据集中的相似程度.　　 一般来说,图聚类是按照图结点间所具有的关联特性对结点进行分类或标识,其最终目标是将图中结点分组,使其组内具有紧密的关联,而组间的关联相对稀疏.本文在分析了Moussiades与Vakali(Clustering dense graph:A web site graphparadigm.Information Processing and Management,2010)提出的基于内部连通比率(inter connection ratio,ICR)的图聚类算法(以下简称MV-ICR聚类算法)基础上,进行了相应的改进,提出了一个新的聚类指标和基于新指标的聚类算法.主要工作如下:　　 (1)提出了一种基于ICR的聚类策略,改进了MV-ICR聚类算法中无法将关系相等的多个类同时归类的问题,改进后的算法使得聚类过程更加快速、聚类结果更加清晰,较MV-ICR算法更加合理有效.　　 (2)提出了一种基于类内关联顶点个数的新聚类指标(称为类内顶点连接比率),并给出了基于类内顶点连接比率的聚类算法；实例分析表明,提出的新算法合理有效.　　 (3)对ICR算法、ICR改进算法以及IVCR算法所适应的图类进行了比较讨论.