对大规模图数据的紧凑存储,能够有效的解决图数据的增长速度快导致的数据量过大问题。随着互联网络的发展和图数据在各个领域的应用,传统的图数据存储方式已经不能支持大规模图数据的存储和操作。如何有效紧凑的表示大规模图数据并且在表示的基础上支持图的基本操作,不论是对大规模图数据的管理而言,还是基于大规模图数据做数据分析和知识推理,都是一项值得研究的工作。k~2-tree和k~2-BDC能够对大规模图数据的邻接矩阵进行紧凑的表示,但仍然不能充分的压缩邻接矩阵中的0单元。为此,本文在k~2-tree和k~2-BDC的研究基础上,将聚类技术引入到大规模图数据的紧凑表示中,较好的达到了空间/时间均衡,本文的主要内容和研究成果如下:(1)综述了目前大规模图数据紧凑表示的相关经典算法,包括基于邻接矩阵的大规模图数据压缩技术,基于邻接表的大规模图数据压缩技术,基于符号计算的大规模图数据压缩技术,分析了三类算法的核心思想和适用领域。(2)针对k~2-tree和k~2-BDC存在的问题,提出了一种新的基于聚类和k~2-tree的大规模图数据紧凑表示方法——k~2-tree-cluster,该方法在k~2-tree和k~2-BDC的基础上进行优化和改进,利用网页图和社交网络图的邻接矩阵的分布规律,使用聚类算法来充分的发现该矩阵中的稠密块,然后用k~2-tree紧凑表示稠密块,来实现更加紧凑的目的。在真实数据集上Enron,EU-2005,CNR-2000进行实验,实验结果表明k~2-tree-cluster的压缩效果优于k~2-tree和k~2-BDC。(3)在k~2-tree-cluster紧凑表示大规模图数据的基础上,给出了k~2-tree-cluster的顶点邻居查询算法,包括顶点的直接邻居查询算法和顶点的反向邻居查询算法。并且对该算法进行了实验验证。在真实数据集上Enron,EU-2005,CNR-2000进行实验,实验结果表明k~2-tree-cluster的顶点邻居查询时间优于k~2-tree和k~2-BDC。