Privacy Risks and Countermeasures in Publishing and Mining Social Network Data

As interests in sharing and mining social network data continue to grow, we see a growing demand for privacy preserving social network data publishing. In this paper, we discuss privacy risks in publishing social network data and the design principles for developing countermeasures. The main contributions of this study are three folds. First, to the best of our knowledge, we make the first attempt to define the utility of released data in terms of exposure levels and query types, assuming queries are the most fundamental operations in social network analysis. We argue that using information exposure levels to characterize the utility of anonymized data can be used as a general and usage-neutral metric and query types can be used as the baseline usage driven utility metric. Second, we identify two types of background knowledge based inference attacks that can break some of most representative graph permutation based anonymization techniques in terms of anonymity violations. Third but not the least, we describe some design considerations for developing countermeasures in privacy preserving social network data publishing.