STK-anonymity: k-anonymity of social networks containing both structural and textual information

We study the problem of anonymizing social networks to prevent individual identifications which use both structural (node degrees) and textual (edge labels) information in social networks. We introduce the concept of Structural and Textual (ST)-equivalence of individuals at two levels (strict and loose), and formally define the problem as Structure and Text aware K-anonymity of social networks (STK-Anonymity). In an STK-anonymized network, each individual is ST-equivalent to at least K-1 other nodes. The major challenge in achieving STK-Anonymity comes from the correlation of edge labels, which causes the propagation of edge anonymization. To address the challenge, we present a two-phase approach. In particular, a set-enumeration tree based approach and three pruning strategies are introduced in the second phase to avoid the propagation problem during anonymization. Experimental results on both real and synthetic datasets are presented to show the effectiveness and efficiency of our approaches.