图是实体及其关系建模的一种常见方法并广泛地运用于Internet，Web结构，社会网络，代谢网络，蛋白质作用网络，文献共引关系网络，以及通讯网络等的结构描述。随着通讯技术、计算机及网络技术的飞速发展和社会信息化进程的持续推进，用于描述真实世界网络结构的图的规模普遍呈现出指数增长趋势。这一现象，一方面确定了大型复杂网络结构特征研究的必要性和挑战性；另一方面激发了很多研究者试图探索以聚类方法分析、理解和表示它们的浓厚兴趣。图聚类是按照结点具有的关联特性对结点进行分类或标识。其目标是分组图的结点，使其组内紧密关联，组间稀疏关联。不同于一般的数值聚类，图聚类具有其自身的特殊性。主要是因为图的许多特性，如结点间的距离，关联关系等，对图中的边具有高度敏感性；另外，图的距离往往是整数，结点到多个聚类中心等距的情况十分常见。因此，一般很难简单复制数值聚类的现有方法达到图聚类的目标。本文以连通的无向非加权图为研究对象，在系统地分析和比较几种典型的图聚类方法的基础上，主要完成如下研究工作：(1)提出了结点连接度和图的连接度矩阵的概念，并给出了它们的定义及计算方法，该方法的效率主要依赖于计算过程中所用的最短路径算法。(2)将最大最小距离聚类方法的基本思想与连接度矩阵相结合，提出了最大最小连接度图聚类方法，该聚类方法的时间复杂度为O((k+3)k/2 n)，其中，k是期望的聚类数目，n是图的结点数。(3)引入结点相异度和图的相异度矩阵的概念，给出其具体定义和计算模型，该模型的算法复杂度均为O(n~2)。(4)给出了已知图的相异度矩阵的前提下，子聚类间的一种相异度度量方法，允许以之为依据实现对图结点的凝聚层次聚类。(5)通过实例检验了上述度量标准及聚类算法的正确性和有效性。