Obfuscating Community Structure in Complex Network With Evolutionary Divide-and-Conquer Strategy
Jie Zhao, Kang Hao Cheong
Abstract
As the number of social network users grows exponentially with increasingly complex profiles, community detection algorithms play a critical role in user portrait analysis. The associated privacy concerns, however, have not sufficiently received the attention that it deserves. In this work, we investigate methods for obfuscating the original community structure by modifying a small number of connections imperceptibly so as to protect the privacy of users. The existing evolutionary models have some successes in this type of NP-hard problem but can only be applied to small-scale datasets, rendering them inadequate for real-world applications. To alleviate this problem, we propose an original and novel CoeCo, a cooperative evolutionary community obfuscation model. In CoeCo, we leverage the divide-and-conquer strategy and put forward a co-evolutionary optimization algorithm suitable for community structure, in which two different fitness functions promote each other to find the optimal edge set. In addition, the motif hypergraph and permanence are used to improve population initialization. The experimental results indicate that our proposed method can achieve excellent efficacy in obfuscating community structure and also greatly reduces running time.