Community Deception in Large Networks: Through the Lens of Laplacian Spectrum

Many complex networks in the real world have community structures. Typical examples include online social net-works and ecology networks. While the identification of commu-nities bears numerous practical applications, with the increasing awareness of data security and privacy concerns, the need to protect the community affiliations of individuals from disclosing by attackers emerges. This raises the community deception (CD) problem, that is, the opposite of community detection, which asks for ways to minimally perturb the network structures by rewiring nodes so that the target communities maximally hide themself from community detection algorithms. To this end, we investigate the CD problem through a Laplacian spectrum lens and propose a method named ComDeceptor to hide a flexible target set of communities, which is more universal than most existing methods that either focus on hiding the entire communities or a single community. The key idea of ComDeceptor is to first allocate the resources of perturbations fairly and effectively. By proving that hiding communities through intercommunity edge addition and intracommunity edge deletion correspond to maximizing the second smallest eigenvalue ?(2) and minimizing the largest eigenvalue ?(n) of the graph Laplacian, respectively, ComDeceptor then incorporates efficient heuristics for approx-imately solving the problems, thus selecting the appropriate edge to perturb. Experimental results over nine real-world networks and six community detection algorithms not only demonstrate the efficiency of ComDeceptor, but also the superior performance on obfuscating community structures over the baselines.