The CriticalSet problem: Identifying Critical Contributors in Bipartite Dependency Networks

arXiv:2604.21537v1 Announce Type: new Abstract: 複雑なネットワークにおける批判的なノードの特定は、グラフマイニングの基本的なタスクの一つである。しかし、2 つのグループ間の依存関係を表すエッジを持つ二部依存ネットワークにおいて、「すべてか何もかも」のカバレッジ・メカニクスに対処する方法は、まだ大いに研究されていない。我々は CriticalSet 問題を形式化する：任意の物品と貢献者の依存関係をモデル化するための二部グラフに対して、その数を最大にする k つの貢献者の集合を特定する。我々は、この問題が NP-hard であること、および標準的なフワード・グリディ алгоритムは近似保証を提供できない超調和集合関数の最大化を必要とすることを証明する。したがって、我々は CriticalSet 問題を連合ゲームとしてモデル化し、シャプレイ値に基づいて閉じた形の中心性 ShapleyCov を導出する。この測度は、貢献者の退去によって孤立される物品の期待数を解釈できる。これらの洞察を利用し、我々は接続の冗長性を明示的に考慮し、多くの物品を唯一でサポートする貢献者を優先する線形時間反復ピリングアルゴリズム MinCov を提案する。合成および大規模な実データセット（2 億 5,000 万エッジを超過するウィキペディアグラフを含む）における広範な実験により、MinCov と ShapleyCov は伝統的なベースラインを大幅に超越していることが示された。特に、MinCov は Stochastic Hill Climbing メタヒューリスティックの 0.02 の AUC 以内のほぼ最適性能を達成しつつ、その何十倍も高速であることが明らかになった。

arXiv:2604.21537v1 Announce Type: new Abstract: 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.