A Novel Approach to Preserving Privacy in Social Network Data Publishing
Today, more and more social network data are published for data analysis. Although this analysis is important, these publications may be targeted by re-identification attacks i.e., where an attacker tries to recover the identities of some nodes that were removed during the anonymization process. Among these attacks, we distinguish "the neighborhood attacks" where an attacker can have background knowledge about the neighborhoods of target victims. Researchers have developed anonymization models similar to k-anonymity, based on edge adding, but can significantly alter the properties of the original graph. In this work, a new anonymization algorithm based on the addition of fake nodes is proposed, which ensures that the published graph preserves another important utility that is the average path length “APL”.
Neighborhood attack; Social network data publication; Anonymization; Utility.