arXiv:2604.21537cs.AIcond-mat.stat-mech2026-04

找出依赖网络中关键贡献者,让最多项目失联

The CriticalSet problem: Identifying Critical Contributors in Bipartite Dependency Networks

  • 将关键贡献者识别建模为合作博弈,用谢帕利值定义新中心性
  • 提出MinCov算法,线性时间运行,在2.5亿边数据上近最优
  • 适合分析维基百科等大规模依赖网络中的核心贡献者

在二部依赖网络中识别关键节点是图挖掘的基础任务。现有方法多采用全或无覆盖机制,尚未充分探索此类网络的特性。本文形式化了CriticalSet问题:给定一个描述项目与贡献者间依赖关系的二部图,找出移除后导致最多项目孤立的k个贡献者。证明该问题是NP难的,需最大化超模集合函数,传统前向贪心算法无近似保证。为此,将问题建模为合作博弈,推导出基于谢帕利值的闭式中心性度量ShapleyCov,其可解释为贡献者离开时预期导致孤立的项目数。基于此,提出MinCov算法——一种线性时间迭代剥除算法,显式考虑连接冗余,优先选择唯一支持大量项目的贡献者。在合成及大规模真实数据集(含超过2.5亿条边的维基百科图)上的实验表明,MinCov与ShapleyCov显著优于传统基线;尤其值得一提的是,MinCov性能接近随机爬山元启发式方法,差距仅0.02 AUC,但速度高几个数量级。

原文摘要 · Abstract (English)

Identifying critical nodes in complex networks is a fundamental task in graph mining. Yet, methods addressing an all-or-nothing coverage mechanics in a bipartite dependency network, a graph with two types of nodes where edges represent dependency relationships across the two groups only, remain largely unexplored. We formalize the CriticalSet problem: given an arbitrary bipartite graph modeling dependencies of items on contributors, identify the set of k contributors whose removal isolates the largest number of items. We prove that this problem is NP-hard and requires maximizing a supermodular set function, for which standard forward greedy algorithms provide no approximation guarantees. Consequently, we model CriticalSet as a coalitional game, deriving a closed-form centrality, ShapleyCov, based on the Shapley value. This measure can be interpreted as the expected number of items isolated by a contributor's departure. Leveraging these insights, we propose MinCov, a linear-time iterative peeling algorithm that explicitly accounts for connection redundancy, prioritizing contributors who uniquely support many items. Extensive experiments on synthetic and large-scale real datasets, including a Wikipedia graph with over 250 million edges, reveal that MinCov and ShapleyCov significantly outperform traditional baselines. Notably, MinCov achieves near-optimal performance, within 0.02 AUC of a Stochastic Hill Climbing metaheuristic, while remaining several orders of magnitude faster.

图挖掘依赖网络中心性算法优化

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