图作为一种表示实体之间关联关系的数据结构被广泛应用于复杂系统、大规模集成电路和社交网络等领域的建模与分析。大规模的图一般呈现出全局稀疏但局部紧密的现象,这些紧密的局部结构代表了图的关键特征,在社区发现、病毒传播、广告推荐等领域有重要的应用价值。因此计算并挖掘图中的紧密区域,即紧密子图是非常有必要的。但是挖掘的紧密子图不仅要保证较高的内聚性,还要考虑计算上的高效性。挖掘紧密子图的需要选择合适的紧密子图指标以平衡子图的内聚性和计算效率,本文以k-truss和k-core两种紧密子图指标作为研究对象进行分析计算,这两个紧密子图指标可在接近线性和线性时间内计算且都能保证很好的内聚性。现实世界的图是不断增长和变化的,边和顶点都在不断的加入或删除,所以关于动态紧密子图的维护也是一项重要挑战。在本文中,通过应用图分析中的理论、技术和方法对紧密子图的挖掘进行系统的研究。针对多边动态图、全动态图、动态超图、流式超图中紧密子图挖掘和超图中的紧密子图模型设计等问题,本文进行深入研究,主要贡献归纳如下。1.本文研究多边动态图中的k-truss维护问题。维护k-truss是指在图动态变化后更新k-truss,但图在动态变化后通常只有少部分区域的k-truss是变化的,因此维护k-truss的关键是避免重新计算整个图以减少冗余计算。与现有的主要关注单条边动态的工作不同,本文提出了多条边同时插入或删除的k-truss维护的批处理算法。本文首先提出三角形不相关集的边集结构,这个边集的插入或删除可以使得k-truss最多改变1,解决批量处理中量化k-truss变化的难题;然后本文提出两个衡量k-truss变化的指标,能够极大减少算法搜索潜在变化边的范围。大量实验证明,与单边处理的方法相比,本文的批处理算法可以显著提高k-truss的维护效率,且动态边数越多时算法加速效果越明显。2.本文研究全动态图中的k-truss维护问题。全动态图的动态性更加复杂,包含了大量的动态边和动态顶点。具体来说,本文考虑批量动态边和顶点的k-truss维护问题,提出高效的算法,只需搜索图中小范围受影响的边就可以更新k-truss。同时,所提出的算法允许并行实现,以进一步提高k-truss的维护效率。大量实验证明本文算法的高效性和可扩展性。3.本文研究大规模动态超图中的k-core维护问题。超图中的超边包含任意数量的顶点,而不是像普通图中的边只包含两个顶点,超图可以在复杂的关联关系应用中代表多元的互动关系。然而,在超图动态变化时,由于超边的指数级数量会使得重新计算k-core产生难以承受的成本。本文提出一种高效的精确k-core维护方法,与重新计算的分解方法相比,能够显著减少计算k-core的时间。所提出的算法可以精确地指出需要更新的k-core的子图区域。本文还提出一个辅助索引结构,可以加速k-core维护算法的搜索过程。大量实验证明本文的算法的高效性。4.本文研究流式超图中的k-core维护批量处理问题。与现有的工作不同的是,本文提出了第一个用于维护k-core的批处理算法。通过提出联合超边集结构,本文解决了量化k-core变化和减小搜索更新范围的难题。此外,本文还通过寻找能够并行执行的k-联合超边集结构来进一步加速更新过程。实验证明了k-core维护算法的效率、可扩展性和有效性,并且本文的并行算法随着线程数量的增加而实现线性加速。5.本文研究基于超图顶点参与度的紧密子图计算问题。顶点参与度对社会复原力和网络稳定性有着重要的意义。然而,反映实体间多元关系的超图中的顶点参与度还从未被研究过。本文证明超图中顶点的参与度可以由两个关键的参数捕获,即群体参与度和邻居参与度。此外,本文还提出基于顶点参与度的紧密子图模型（k,h）-core,以整合这两个衡量标准的优点,从而解决只使用单一参与度因素的无效性和不全面性。本文提出一种在线性时间内完成分解（k,h）-core的算法;提出一种小规模的局部更新算法来维护（k,h）-core,这极大避免了动态超图中重新分解的低效方式。广泛的实验证明本文模型的通用性和算法的有效性。