On Hiding Communities and Evading Link Prediction in Social Networks

Community detection and link prediction are two of the main research problems in social network analysis. While various private and public institutions are interested in identifying communities, it raises serious privacy issues as well as security-related concerns. We introduce the problem of hiding communities, in which a community is concerned with concealing its existence within a social network. That is, the community's objective is to avoid detection by various community-detection algorithms. Link prediction involves the identification which connections are most likely to occur in the network or that have not yet been found. We ask the question whether and how it is possible to strategically evade link prediction, i.e., whether members of a social network could deliberately decrease the probability of some their connections being identified by link prediction algorithms. For both problems we perform theoretical analysis and provide effective heuristic solutions.