在大型图上进行密度的扩展分解

《Proceedings of the ACM on Management of Data》:Scaling Up Density Decomposition on Massive Graphs

【字体: 大 中 小 】 时间:2026年10月22日 来源:Proceedings of the ACM on Management of Data

编辑推荐:

  摘要AI摘要要查看此AI生成的摘要,您必须具有高级访问权限。了解更多登录摘要摘要密度分解可以表征大型网络的多层次密集结构,并支持各种图挖掘应用。给定一个图G = (V, E),它为每个顶点分配一个整数密集编号(IDN),并生成一个嵌套的层次序列D0 ? D1 ? ... ? Dp

  

摘要

摘要

密度分解可以表征大型网络的多层次密集结构,并支持各种图挖掘应用。给定一个图G = (V, E),它为每个顶点分配一个整数密集编号(IDN),并生成一个嵌套的层次序列D0 ? D1 ? ... ? Dp,这些层次分别捕获图中越来越密集和结构上重要的区域。然而,现有的计算密度分解的算法计算成本较高。最先进的 divide-and-conquer 算法 BinaryDC 的运行时间为 O(?og p • |E|1.5),但其基于二分查找的枢轴选择在每次划分步骤中会导致多次最大流计算,这使得它在处理大规模图时变得非常缓慢。为了解决这个问题,我们专注于共享内存环境,并通过算法改进来减少全局最大流计算并提高局部性。我们首先提出了 MeanDC,它用基于平均值的策略替换了基于二分查找的枢轴选择,显著减少了最大流计算次数,同时保持了相同的渐进复杂度。然后,我们提出了一种新的 core-prepartition 技术,并开发了 CoreDC,该技术利用 k-core 层次结构将图预分割成 O(?og p) 个不相交的区域,并在每个区域内进行局部化的 divide-and-conquer 操作,大大缩小了流网络的大小。对于并行计算,我们开发了一种 heat-extraction 技术,通过轻量级的、基于边的热扩散迭代实现高度并行化,可以在不进行任何最大流计算的情况下提取多层信息。基于这一想法,我们设计了 HeatDC,并进一步将 heat-extraction 与 core-prepartition 结合到我们的最快并行算法 CoreHeatDC 中。在包含多达 18.1 亿条边的 10 个真实世界图上的实验表明,我们的算法始终优于现有的方法,而且 CoreHeatDC 能够在共享内存环境中在几秒钟内计算出具有数十亿条边的图的重度分解。

AI摘要

AI生成摘要(实验性)

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

点击这里对摘要的准确性、清晰度和有用性进行评论。这样做将有助于改进未来的版本。

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

相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号