arXiv:2608.16906cs.SIcs.AI2026-08

提出通用动态社区检测框架,局部更新提升效率且不损失精度。

ComNetX: Local Hierarchical Adaptation for Dynamic Community Detection

论文配图:ComNetX: Local Hierarchical Adaptation for Dynamic Community Detection
图 1 · 摘自论文原文
  • 构建多层级社区状态,通过闭合与压缩实现精准局部更新
  • 在最大真实图上实现41.9倍加速,模体值仅下降0.006
  • 兼容多种算法,适合大规模动态图分析场景

动态社区检测通常采用全快照重计算或特定求解器的动态方法。前者虽保留成熟静态求解器语义,但小更新时重复处理未变区域;后者虽降低开销,但更新规则跨目标、特征表示和实现的迁移性差。此外,仅依赖图距离定位计算可能遗漏高质量求解器所需的社区上下文。我们提出ComNetX,一种求解器无关的层次化自适应框架,用于局部动态更新。ComNetX维护多级社区状态,扩展更新区域,闭合并压缩受影响社区为紧凑本地实例。该过程在保持求解器上下文的同时,将计算限制在图中变化部分。同一接口可封装模块度启发式、使用节点特征的图聚类模型及原生动态求解器作为本地后端。我们在六个真实网络上进行多后端评估,针对拓扑类后端测试更长的真实数据流,并在受控动态随机块模型压力流下验证。结果表明,ComNetX在保持强模块度求解器质量的同时显著降低更新时间:在最大真实图上的配对运行中,局部Leiden算法最终模度值与全快照重算相差仅0.006,速度提升41.9 ± 0.2倍。组合协议还识别出局部性失效的区间,此时全刷新更优。

原文摘要 · Abstract (English)

Dynamic community detection is commonly addressed either by full-snapshot recomputation or by solver-specific dynamic procedures. Full recomputation preserves the semantics of mature static solvers, but it repeatedly processes unchanged graph regions when updates are small. Solver-specific dynamic methods can reduce this cost, but their update rules often have limited transferability across objectives, feature representations, and implementations. In addition, localizing computation only by graph distance may omit community context needed by high-quality solvers. We introduce ComNetX, a solver-agnostic hierarchical adaptation framework for local dynamic updates. ComNetX maintains a multi-level community state, expands the updated region, closes it over affected communities, and contracts these communities into compact local instances. This affected-community closure and contraction preserve solver context while restricting computation to the changed part of the graph. The same interface can wrap modularity heuristics, graph-clustering models that use node features, and native dynamic solvers as local backends. We evaluate ComNetX through a multi-backend study on six real networks, longer real-data streams for topology-based backends, and controlled dynamic stochastic block model stress streams. The results show that ComNetX can preserve the quality of strong modularity-based solvers while reducing update time on large graphs: in paired runs on the largest real graph, Local Leiden keeps final modularity within 0.006 of full-snapshot recomputation while achieving a 41.9 +/- 0.2x speedup. The combined protocols also identify regimes where locality breaks down and a full refresh is preferable.

社区发现动态图图算法优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。