Community Deception or: How to Stop Fearing Community Detection Algorithms
- 22 November 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 30 (4) , 660-673
Abstract
In this paper, we research the community deception problem. Tackling this problem consists in developing techniques to hide a target community (C) from community detection algorithms. This need emerges whenever a group (e.g., activists, police enforcements, or network participants in general) want to observe and cooperate in a social network while avoiding to be detected. We introduce and formalize the community deception problem and devise an efficient algorithm that allows to achieve deception by identifying a certain number (B) of Cs members connection to be rewired. Deception can be practically achieved in social networks like Facebook by friending or unfriending network members as indicated by our algorithm. We compare our approach with another technique based on modularity. By considering a variety of (large) real networks we provide a systematic evaluation of the robustness of community detection algorithms to deception techniques. Finally, we open some challenging research questions about the design of detection algorithms robust to deception techniques.Keywords
This publication has 33 references indexed in Scilit:
- Community detection in graphsPhysics Reports, 2010
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communitiesPhysical Review E, 2009
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Maps of random walks on complex networks reveal community structureProceedings of the National Academy of Sciences, 2008
- Near linear time algorithm to detect community structures in large-scale networksPhysical Review E, 2007
- Resolution limit in community detectionProceedings of the National Academy of Sciences, 2007
- Finding community structure in networks using the eigenvectors of matricesPhysical Review E, 2006
- Modularity and community structure in networksProceedings of the National Academy of Sciences, 2006
- Computing Communities in Large Networks Using Random Walks2005
- Finding community structure in very large networksPhysical Review E, 2004