近年来,互联网技术的高速发展为数据分析带来了前所未有的机遇。高速互联网下产生的海量图数据中蕴含了大量有用的信息。在图数据上进行稠密子图查询可以帮助人们在海量数据中获取有价值的信息。稠密子图查询可以应用到诸多现实场景中,如在社交网络中进行社区查找和朋友推荐、在蛋白质交互网络中进行复杂蛋白质检测、在购物网络中进行商品推送等。本文主要研究了两种有价值的全新的稠密子图模型:高阶Truss模型和平衡团模型,以及三种高效的稠密子图查询算法。本文的主要贡献如下:1.Truss模型是一种典型的稠密子图模型,近年来受到了广泛的关注。然而,Truss模型只考虑边的直接公共邻域,这限制了它揭示图中更细粒度结构信息的能力。基于此,本文提出了一种考虑边的高阶邻域信息的（k,τ）-Truss模型。基于（k,τ）-Truss模型,本文研究了（k,τ）-Truss子图分解问题,也就是在给定τ下,计算出所有可能的k值对应的（k,τ）-Truss。高阶Truss子图分解问题可以应用到社区检测与搜索、图层次结构分析、图形可视化等多个领域。为了解决这个问题,本文首先提出了一种自底向上的分解算法,按照k值的递增顺序来计算相应的（k,τ）-Truss。基于该分解算法,本文进一步设计了三种优化策略来减少不必要的计算量。另外,本文还研究了寻找前r个（k,τ）-Trusses问题,并设计了相应的搜索算法。本文在真实数据集和合成数据集上对设计的模型和分解算法进行了实验分析,实验结果证明了（k,τ）-Truss模型的有效性和提出的算法的高效性。2.团模型是稠密子图查询领域的最基本的稠密子图模型之一。与团模型相关的现有工作主要集中在无签名图上。然而,在现实世界中,许多应用场景被建模为由正负边组成的签名图。由于签名图具有与无签名图截然不同的结构性质,现有的团模型不再适用于签名图。因此,基于结构平衡理论,本文设计了平衡团模型,并研究了如何在给定签名图中枚举出所有平衡团的问题（MBCE）。平衡团子图枚举问题被证明是一个NP-难问题。该问题的直接解决方案是将签名图视为两个无签名图,并利用基于无签名图的现有技术来间接计算出结果。然而,这样的解决方案对于大型签名图来说是低效的。针对这一问题,本文利用签名图的独特结构性质,提出了一种新的平衡团枚举算法,在新算法的基础上,又设计了两种优化策略来进一步提高枚举效率。本文在大量的真实数据集和合成数据集上进行了广泛的实验。实验结果证明了算法的有效性、高效性和可扩展性。3.随着签名图规模的不断增长,当处理大规模签名图时,由于签名图中的平衡团数量众多,且平衡团之间有很多重叠部分,当用户希望得到最具代表性的平衡团时,平衡团子图枚举算法不再适用。在稠密子图查询领域,最大稠密子图往往是最有代表性的子图,最大稠密子图搜索问题一直是一个研究热点。因此,本文还研究了最大平衡团子图搜索问题,也就是寻找顶点数量最多的平衡团。该问题被证明是一个NP-难问题。该问题可以解决诸多应用,如在社交网络中发现对立的社区、在合作网络中挖掘相似课题的研究组、搜索竞争商业联盟、检测蛋白质拮抗关系等。针对该问题,本文首先探索了基于MBCE的最大平衡团子图搜索算法。该算法存在搜索空间过大的问题,于是本文又提出了基于搜索空间分区的搜索算法,通过在每个搜索区域对平衡团两侧顶点数量设置不同的下界来细化搜索空间。另外,本文还提出了多种优化策略来进一步减少搜索空间。最后,本文在大规模真实数据集上进行了广泛的实验,其中最大的数据集具有上亿条边。实验结果证实了算法的高效性、有效性和可拓展性。