ABSTRACT
The increasing growth of online social networks provides an unprecedented opportunity to study the complex interactions among human beings. Privacy-preserved network-data publishing is becoming increasingly popular in both industry and academia. This articles focuses on evolving social subscription networks (ESSN), which indicate social actors’ participation in certain media channels, such as Hollywood stars’ Twitter pages, during a series of time intervals. The discussion first introduces a new identity disclosure attack by exploring the subscribed channel sizes of a social actor and the actor’s frequency of joining/leaving the channels. For privacy protection, K-anonymity should be ensured for the whole evolving graph. However, unlike the conventional topology information, such as node degree, the ESSN data points are much more sparse. Moreover, during the construction of anonymous groups, the unpopular channel-related information is likely to be discarded. How to maximally preserve ESSN data utility during anonymization is an open problem. These authors propose an effective three-step framework to solve it: data space compression, anonymity construction, and realizable publishing. Also provided are comprehensive studies on the performance of this approach. Extensive results show that this approach is effective in terms of privacy, utility, and efficacy. To the best of the knowledge of these authors, this work is the first systematic study to the anonymization of time-evolving multi-relation graphs.