Search papers, labs, and topics across Lattice.
This paper formalizes the CriticalSet problem, which aims to identify a set of *k* contributors in a bipartite dependency network whose removal isolates the largest number of items. They prove that the problem is NP-hard and that greedy algorithms offer no approximation guarantees. To address this, they propose MinCov, a linear-time iterative peeling algorithm that accounts for connection redundancy, and ShapleyCov, a closed-form centrality measure based on the Shapley value.
A surprisingly simple, linear-time algorithm, MinCov, nearly matches the performance of much slower metaheuristics in identifying critical nodes in bipartite dependency networks.
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.
