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