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号