随着信息网络的高速发展,真实世界的数据量正在呈指数增长,并且呈现大样本、更新快、含噪声等特点。因此如何从含噪声的大规模数据中提取有效信息,如何挖掘大样本数据的社区结构,如何提高挖掘社区结构的效率和质量,便成为了一个核心问题。聚类(或分类)是数学、计算科学、管理科学等领域的热门研究话题,并且在诸如模式识别、数据分析、通信、生物以及商务等领域有着广泛的应用。图聚类,就是应用图理论对真实网络进行分析,用图来表示数据集中的规律现象。图聚类分析方法作为数据挖掘技术中的重要方法之一,同时为海量数据的研究分析提供了一种方法,并被广泛应用到现实社交的各个领域,如模式识别、生物网络、基因网络及其电子商务等。与普通的数值聚类不同的是,基于图理论的聚类具有其本身的特殊性,可以用图来表示数据集中的相似程度。Web2.0时代的到来,社交网络正在全世界范围内流行起来。随着微博、社区、空间等的发展,社交网站渐渐在人们的日常娱乐中占了重要的地位。如我们所熟知的Facebook、人人网等社交网络平台,也已经拥有超过亿真实注册用户。社交网络数据多、数据量大,且社交网络同时作为数据挖掘的一个新的方向,吸引着越来越多研究者的关注,社区结构发现成为分析社交网络的一个重要研究方向,但是如何有效且高效的挖掘出社区结构,至今没有完全解决。基于上述的问题,本文将社区发现问题与图聚类算法结合起来,以全局和局部两个步骤来分层挖掘复杂网络重叠社区结构,并引入社交网络真实数据,实验验证结果。本文的贡献如下：(1)本文首先阐述社交网络的研究背景、意义以及国内外研究现状,总结了一些典型的社区结构发现算法以及典型的图聚类算法,并分析它们的优缺点。(2)通过启发式的重叠社区挖掘算法的研究,提出一种新的全局及局部相结合的GL算法,该算法首先全局划分生成候选种子集,然后局部凝聚种子集,挖掘出重叠社区结构。(3)设计和实现了上述各算法,并将其应用于空手道俱乐部关系网络和海豚家族关系网络来自真实世界的网络聚类分析基准测试数据集。通过在真实数据集上进行验证,改进后的算法使得聚类过程更加快速、聚类结果更加清晰,提出的算法合理有效,最后对文中提出的GL算法与传统算法进行了比较分析。