大型图中基于最大连通性的准团高效查询
《Proceedings of the ACM on Management of Data》:Efficient Querying of Maximum Connectivity-Based Quasi-Cliques in Large Graphs
【字体:
大
中
小
】
时间:2026年10月22日
来源:Proceedings of the ACM on Management of Data
编辑推荐:
# 摘要
涉及连通性约束的结构图查询是现代数据管理与分析中的基本操作原语。与基于度和边的变体相比,基于连通性的 γ-拟团(γ-CQCs)施加了更强的结构约束和容错能力,其中鲁棒性通过顶点连通度来衡量,即断开子图所需移除的最少顶点数。然而,在大型图上处理此类查询仍然具有计算上
# 摘要涉及连通性约束的结构图查询是现代数据管理与分析中的基本操作原语。与基于度和边的变体相比,基于连通性的 γ-拟团(γ-CQCs)施加了更强的结构约束和容错能力,其中鲁棒性通过顶点连通度来衡量,即断开子图所需移除的最少顶点数。然而,在大型图上处理此类查询仍然具有计算上的挑战性。本文研究了 *最大连通度 γ-拟团*(MCQC)查询的高效执行问题,该查询旨在寻找包含顶点数最多的 γ-CQC。该问题为 NP 难问题,且顶点连通度的非遗传特性使许多传统的剪枝技术失效,给精确查询处理带来了显著挑战。现有解决方案依赖于通用的优化公式,在实际中可扩展性较差。为应对这些挑战,我们提出了 MCQC-TD,一个针对 MCQC 查询的专用精确分支定界框架。MCQC-TD 采用自顶向下的搜索策略,并利用 γ-CQCs 的一种新颖结构特征来实现有效的剪枝和引导式分支。这些技术相比于现有方法大幅降低了理论最坏情况复杂度。我们进一步集成了实际的查询优化技术,包括优化的初始化策略和查询分解框架,以增强在大型图上的可扩展性。大量实验表明,MCQC-TD 始终优于现有最优方案,查询时间加速比最高可达五个数量级。---## AI 生成摘要(实验性)*本摘要由自动化工具生成,未经本文作者撰写或审阅。其目的是辅助发现、帮助读者评估相关性,并协助相关研究领域的读者理解该工作。本摘要旨在补充作者提供的摘要,作者提供的摘要仍然是本文的主要摘要。全文仍然是权威版本记录。[点击此处了解有关 ACM AI 摘要的更多信息](/generative-ai/summarizations)。**点击[此处](srv.openModal)对本摘要的准确性、清晰度和实用性进行评论。这样做将有助于改进未来的重新生成版本。*如需查看此 AI 生成的通俗语言摘要,您需要具有高级访问权限。
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号