在大图中高效查询基于最大连通性的拟团

《Proceedings of the ACM on Management of Data》：Efficient Querying of Maximum Connectivity-Based Quasi-Cliques in Large Graphs

　　

摘要AI 摘要

要查看此 AI 生成的摘要，您必须具有高级访问权限。

了解更多登录

摘要

摘要

涉及连接性约束的结构图查询是现代数据管理和分析中的基本原理。与基于度数和边的变体相比，基于连接性的 γ-拟团（γ-CQCs）施加了更强的结构约束和容错性，其中鲁棒性是通过顶点连接性来衡量的，即移除后会断开子图的顶点最小数量。然而，在大型图上处理此类查询仍然具有计算挑战性。在本文中，我们研究了高效执行 最大连接性 β-拟团（MCQC）查询的方法，该查询旨在找到具有最多顶点的 γ-CQC。这个问题是 NP 难的，而顶点连接性的非遗传特性使得许多传统的剪枝技术无效，给精确查询处理带来了重大挑战。现有的解决方案依赖于通用的优化公式，在实践中可扩展性较差。为了解决这些挑战，我们提出了 MCQC-TD，这是一个专门用于 MCQC 查询的精确分支定界框架。MCQC-TD 采用自上而下的搜索策略，并利用 γ-CQCs 的新颖结构特征来实现有效的剪枝和指导性分支。这些技术大大降低了理论上的最坏情况复杂性。我们进一步整合了实用的查询优化技术，包括优化的初始化策略和查询分解框架，以提高在大型图上的可扩展性。广泛的实验表明，MCQC-TD 一致性地优于最先进的解决方案，在查询时间上实现了高达五个数量级的加速。

AI 摘要

此摘要是使用自动化工具生成的，未由文章作者撰写或审核。它旨在帮助发现、帮助读者评估相关性，并协助来自相关研究领域的读者理解工作内容。它旨在补充作者提供的摘要，后者仍是论文的主要摘要。完整文章仍是权威版本。点击这里了解更多。

点击 这里 评论此摘要的准确性、清晰度和实用性。这样做将有助于改进和未来重新生成的版本。

要查看此 AI 生成的通俗语言摘要，您必须具有高级访问权限。