随着社会信息化的推进和通讯技术以及网络技术的飞速发展,信息的流量越来越庞大,存储的数据量正在以指数速度迅速增长,图是一种广泛使用的数据结构,它能很好地表示数据对象之间的结构关系。在现实世界中,诸多系统以网络图的结构形式存在,如因特网、万维网、人际关系网、科学家协作网和电话网等等。同时用于描述真实世界网络结构的图的规模也具有较大的增长趋势。目前面对浩渺无际的数据,人们迫切需要从数据汪洋中去粗存精、去伪存真,通过技术手段分析得到有用的结果。图聚类是一个非常有趣和具有挑战性的研究课题,近年来已经引起众多研究者的广泛关注,并应用到多个领域。图聚类的目的是按照各种不同的标准把大型图的节点拆分成不同的簇,使得同一簇内的节点连接紧密,不同簇之间节点的连接稀疏。许多现有的图聚类方法主要关注图的拓扑结构,使得每个簇达到一个有凝聚力的内部结构。但是在实际应用中由于图结构数据集的异质性,图本身存在着诸多的潜在信息,如图节点的属性信息和节点间的权重信息等等。随着图结构数据集的日趋庞大和复杂,仅仅分析图的拓扑结构信息很难得到理想的聚类结果。为此本文在综合考虑图的拓扑结构、节点属性以及节点间权重的基础上提出了两种新的图聚类方法来解决上述问题。1.多属性网络图结构化凝聚层次聚类方法图聚类的目的是按照各种不同的标准把大型图的节点拆分成不同的簇。该方法综合考虑图的拓扑结构和节点属性信息,利用节点的属性信息辅以图的拓扑结构产生新的簇,避免了传统图聚类方法的单一性。该方法首先通过在原图上添加多个属性节点的方法来增强同属性节点间的紧密度,同时可以让非连通图变为连通图;再根据节点的直接邻居关系计算边的结构化相似度,为了提高新添加的属性节点的贡献,本文计算属性节点转移概率矩阵,由此得到相邻节点间的相似度值。该方法只访问图节点和边各一次、简单、高效。2.基于最大最小距离度量的加权网络图结构化聚类方法该方法统一考虑图的拓扑结构和节点间的权重,使具有较大权重边连接的两点不被分开、同时使聚类结果的拓扑结构划分明显,即从图的拓扑结构上讲同一簇内的节点连接密集,不同簇间的节点连接稀疏,避免了传统方法的单一性。为此我们提出基于最大最小距离度量的加权网络图结构化聚类方法,归一化处理每一条边上的权重,按照图的拓扑结构计算具有直接边相连的节点的结构化相似度,综合考虑图的拓扑结构和权重各自的贡献,以最小关联度原则选取新的聚类中心,再以最大关联度原则进行模式归类。