Multilevel Attacks on Community Detection: From Global Deception to Individual Evasion

Abstract

Community detection reveals meso-scale structure in graphs but can inadvertently expose sensitive affiliations and operational patterns. We study community structure deception (CSD) as a budgeted edge-perturbation problem on directed networks, aiming to reduce the recoverability of communities under heterogeneous detectors. We present a unified, multilevel framework that operates at three granularities within the same optimization model: structure-wide (CSD), single-community [single-community hiding (SCD)], and individual [individual node hiding (IND)]. Our objective is a direction-aware deception functional built on structural entropy and its directed residual entropy. For CSD and SCD, this objective yields closed-form edge-level differentials and principled edit policies with respect to a selected reference partition. For IND, where the target user has only local ego-network visibility and no partition access, we introduce a label-free ego-centric surrogate based on local degree and neighborhood-overlap statistics. We explicitly distinguish the exact partition-based results from this approximation-based IND heuristic and validate the latter empirically against alternative local scoring rules. Empirically, across multiple detectors (spectral, modularity, stochastic block model (SBM), label-propagation) and datasets, the method consistently lowers detectability by significant margins. Together, these results establish directed residual entropy as a theoretically grounded objective for multilevel community deception with respect to a reference partition and show empirically that the resulting perturbations transfer across heterogeneous detectors, with applications to privacy-preserving data release, robustness benchmarking, and individual anonymity.