Multi-level attacks on community detection

Community detection is an important task in social network analysis, with applications ranging from identifying criminal groups to finding protein-protein structures. However, recent research has pointed to serious privacy threats associated with community detection algorithms. This has opened a new strand of research called community deception which aims at developing tools for users to protect their community affiliation from the eye of detection algorithms. But state-of-the-art community deception has been constrained with several limitations that hinder its applicability. This thesis makes several important contributions that expands the utility and effectiveness of community deception algorithms. First, we develop a novel approach to the deception problem by considering node-centric attacks on social networks. This constitutes an important development over traditional community deception algorithms which considered only edge-centric operations. Specifically, we present node-centric operations in undirected networks, using safeness as a deception objective. Secondly, we introduce node-centric deception in Directed Influence Networks (DIN); a more challenging context where edges have both a direction attribute and an influence attribute. Through extensive experiments, we demonstrate that our proposed deception algorithms, designed specifically to work in DIN, significantly outperforms baseline methods. Despite the prevalence of DIN in real-world, baseline approaches have been generally oblivious to edge direction and influence, giving more weight to this contribution. Finally, we develop a new comprehensive community deception framework that tackles the deception problem from a more generic perspective. Contrary to existing approaches we present a community deception algorithm that can be used to hide an entire community structure, a single community, and even a single individual in directed networks. To this end, we develop this framework using Normalized Directed Residual Entropy (NDRE) as the deception objective function of choice. With thorough experimental evaluation, this information-theoretic approach to deception shows promising results over state-of-the-art.