K-isomorphism: Privacy preserving network publication against structural attacks
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
AbstractSerious concerns on privacy protection in social networks have been raised in recent years; however, research in this area is still in its infancy. The problem is challenging due to the diversity and complexity of graph data, on which an adversary can use many types of background knowledge to conduct an attack. One popular type of attacks as studied by pioneer work [2] is the use of embedding subgraphs. We follow this line of work and identify two realistic targets of attacks, namely, NodeInfo and LinkInfo. Our investigations show that k-isomorphism, or anonymization by forming k pairwise isomorphic subgraphs, is both sufficient and necessary for the protection. The problem is shown to be NP-hard. We devise a number of techniques to enhance the anonymization efficiency while retaining the data utility. A compound vertex ID mechanism is also introduced for privacy preservation over multiple data releases. The satisfactory performance on a number of real datasets, including HEP-Th, EUemail and LiveJournal, illustrates that the high symmetry of social networks is very helpful in mitigating the difficulty of the problem. Copyright 2010 ACM.
All Author(s) ListCheng J., Fu A.W.-C., Liu J.
Name of Conference2010 International Conference on Management of Data, SIGMOD '10
Start Date of Conference06/06/2010
End Date of Conference11/06/2010
Place of ConferenceIndianapolis, IN
Country/Region of ConferenceUnited States of America
Detailed descriptionorganized by ACM ,
Pages459 - 470
LanguagesEnglish-United Kingdom
Keywordsdata publishing, graph isomorphism, privacy preservation, social networks, structural attacks

Last updated on 2020-12-07 at 00:55