BOTBIN:用于动态图上结构图聚类的加速索引技术

《IEEE Transactions on Knowledge and Data Engineering》:BOTBIN: Accelerated Indexing for Structural Graph Clustering on Dynamic Graphs

【字体: 大 中 小 】 时间:2025年12月11日 来源:IEEE Transactions on Knowledge and Data Engineering 10.4

编辑推荐:

  动态图环境下SCAN算法的索引结构优化研究,提出基于底部k草图维护和分桶策略的解决方案,在保持聚类质量的同时将更新时间复杂度降至O((M+m)?log log(M+m)),实验显示比现有方法快两个数量级。

  

摘要:

图聚类是一种基本的数据挖掘任务,它将顶点分为不同的组。结构图聚类算法(SCAN)是一种广泛使用的图聚类算法,不仅能生成聚类结果,还能识别出图中的关键节点(如中心节点)和异常节点。在本文中,我们研究了基于Jaccard相似度的动态图的结构图聚类问题。现有的基于索引的解决方案主要针对静态图设计,且维护索引所需的更新成本非常高。最近,提出了一种高效的动态结构图聚类算法DynStrClu,但它需要固定输入参数,而SCAN算法的参数设置通常需要微调才能获得良好的聚类效果。针对这些限制,我们提出了针对动态图的SCAN算法的有效索引结构设计。与现有的动态算法类似,我们通过引入近似方法来降低时间复杂度;不过我们的解决方案无需固定输入参数。为实现这一目标,我们的方案包含两个关键组件:首先为每个顶点维护一个底层k-gram结构,以便轻松更新受影响的顶点之间的相似度;其次采用分桶策略,高效地更新聚类结果和顶点的角色分配。理论分析表明,我们提出的算法能够实现O(log log M + m pf log log M + mp f)的预期更新成本,并保证在最多M次更新后以1-p的概率返回近似聚类结果。实验结果表明,我们的解决方案比现有的基于索引的算法快两个数量级,同时仍能保持高质量的聚类效果。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

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

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号