随着信息技术的发展,社交网络和物联网快速普及,传统的人与人之间的关联关系被延展到了人与物、物与物之间。随之产生的数据具有强关联,非结构化等特征,图结构可以非常好地表示这些非结构化数据。随着移动互联网的普及,手持设备和物联网设备大量增加,可收集的数据呈现爆炸性的增长趋势。目前中国移动用户已经达到9亿,微信月活跃账户数达到11.51亿。这些海量的用户与海量用户之间的复杂关系组成了大规模图。海量用户产生的数据可以应用于多种场景,例如疾病爆发路径的预测,社交网络群组挖掘,电商推广,网页搜索等。图数据分析可以从庞大的图数据中迅速、准确地获取关键信息,成为当下的研究热点。在这些应用中图拓扑结构查询的重要性不断提升,拓扑结构查询主要包括点关系查询、社区挖掘和子图结构查询。其中拓扑序和子图结构查询在拓扑结构查询中占有很大比例。查询节点的拓扑序可以分析图中点的依赖关系,也是很多其他查询的前置步骤;子结构查询是在图拓扑结构查询中的基本问题。虽然图拓扑结构查询在现代应用中占有越来越重要的地位,但是传统的拓扑结构分析技术不能解答针于大规模图的拓扑结构查询。本文主要对大规模图中的拓扑结构分析问题进行了研究,采用了I/O-efficient技术,并行计算技术和分布式技术优化大规模图拓扑结构分析技术。并取得了以下成果:1.大规模图上的拓扑排序优化。首先本文从有向无环图的拓扑结构入手,研究拓扑排序问题。拓扑排序问题是拓扑结构分析中最基础的一环,也是很多其他查询的前置步骤,拓扑序亦可以优化子图匹配的顺序。传统基于内存的算法难以在大规模图中处理拓扑排序问题。第三章提出了新的算法模式,将I/O-efficient技术应用于拓扑排序。算法使用先压缩再扩张的方法,把原始图一步步压缩成能够放入内存的子图,再通过算法还原出原始图的拓扑排序,最后计算了算法的I/O复杂度,并用实验验证的算法的效率。该模式易于实现并且拓展了现有算法的使用界限。2.大规模图上的环搜索优化。对于一般图来说,环结构是图的子结构中非常重要的一个。由于拓扑结构查询中环结构因为应用对于其速度的需求,经常被单独研究。图的环结构在现实中有很多应用,比如金融反欺诈、风险评估等等,所以本文选择了图的环结构搜索问题作为切入点。而环搜索是一个计算密集型问题,传统的基于单线程的算法难以高效处理。本文将并行技术应用于环搜索,提出了一个使用两阶段解决环搜索的模式。该模式从给定点出发得到一系列前缀,再从前缀扩展为所有结果集合,基于这个模式,本文提出了一个负载估计方法提高线程之间的负载均衡。我们证明了本文中提出的算法是工作有效(work-efficient)的,且通过实验验证此算法拥有良好的加速比。3.大规模图上子图匹配算法的比较。在现实应用中,环结构匹配只是图模式匹配的一部分,在第五章,本文更进一步研究了通用子图匹配问题。传统的大规模子图匹配大多是基于回溯实现,而分布式技术可以用自然连接的方法解决子图匹配问题。目前已经有非常多的解决方案,但是它们性能孰优孰劣,仍然没有得到科学的比较。本文正交分离了连接策略和优化方法,利用统一的分布式平台,组织一系列针对标签图和无标签图的实验分析。在实验中,我们选择了多种类型的查询子图和数据集,最后得到一个在实践中行之有效的选择策略。基于以上研究工作,本文对图拓扑结构分析的多个方面进行了深度研究和讨论,并把新的技术应用在已有问题上,且取得了较好的提速成果。我们不但从理论上证明了本文提出的算法的优越性,其中环结构的并行搜索和分布式子图匹配的研究已经投入大规模图数据挖掘实践项目中。