Sybil Attacks on Centrality Measures

Centrality measures are fundamental tools for assessing the importance of nodes in a network, with widespread use in security analysis and the study of covert structures. Importantly, these are precisely the domains where participants may have strong incentives to mislead the analysis. In this work, we investigate Sybil attacks on centrality measures, where an adversary creates multiple identities and distributes connections among them to obscure their true importance. We show that computing an optimal hiding strategy is tractable for degree centrality but NP-complete for both closeness and betweenness centralities. Despite this hardness, we draw from the literature on community detection to design heuristic algorithms that perform well in practice. Experiments on real-world covert networks demonstrate that Sybil-based obfuscation can significantly outperform existing hiding strategies. Our results highlight the risks of relying uncritically on centrality-based methods in security-sensitive applications.