近年来,大规模图数据管理与挖掘已经成为了当前学术界和工业界的研究热点。在大规模图数据中,通常都包含连接紧密的社区结构。从大图数据中搜索连接紧密的社区结构具有重要的科学价值和广泛的实际应用。当前主流的社区搜索技术主要包括基于极大团的社区搜索和基于k-核等稠密子图模型的社区搜索。这些算法的效率通常都依赖于图的退化度(Degeneracy)度量。退化度是一个用于度量网络稀疏性的一个重要指标,设计一个快速的退化度计算算法可以大幅度地优化极大团枚举算法。此外,退化度还是最稠密子图问题的一个二近似解,同时也是经典图的“荫度”(Arboricity)的二近似解,其中荫度也是度量图的稀疏性的一个重要指标。很多网络分析算法,比如极大团枚举、三角形枚举、truss分解等,在退化度较小的图中运行的效果都非常好。鉴于退化度的重要应用,本文研究了大规模图数据的退化度计算算法。提出了一种基于二分搜索和节点削减技术的半外存(semi-external)算法。该算法只需O(n)的内存空间来计算大规模图数据的退化度,其中n表示节点的数量,因此该算法可以适应于超大规模的图数据。并且,本文还将这一半外存算法应用于求解大规模图数据的k-峰(k-peak)分解问题,从而得到了一个快速的半外存k-峰分解算法。此外,本文还提出了一种面向动态图数据的、高效的、半外存的退化度维护算法。最后,本文在真实图数据集上进行了大规模的实验测试,实验结果验证了本文所提算法的有效性和可扩展性。具体地、我们系统地分析和计算了150个真实图数据的退化度,这是首次系统地计算几乎所有公开的大型图数据的退化度,这些计算结果可以为设计高效的图数据挖掘算法提供有价值的实践参考。此外,在这些数据集上,本文还测试了动态维护算法的性能。例如,在拥有9.3亿个节点和133亿条边的GSH网络中,本文所提出的半外存退化度维护算法平均只需0.1毫秒就能完成退化度的动态维护,而之前最好的算法则需要0.1秒,本文的算法要比之前最好的算法快近3个数量级。最后,本文还测试了我们所提的算法在计算k-峰分解问题上的性能,其实验结果表明我们的算法可以计算超大规模图数据的k-峰分解。