TY - GEN
T1 - Towards identity disclosure control in private hypergraph publishing
AU - Li, Yidong
AU - Shen, Hong
N1 - Funding Information:
is associate professor of early modern French literature and culture at Utrecht University. She is the author of Un théâtre des frontières. La culture dramatique dans les provinces du Nord aux XVC?XeVt IC?cslieès (2011) and the co-author of the Recueil des sotties françaises (3 volumes, ongoing publication). She is the principal investigator of the project ‘Uncovering Joyful Culture: Parodic Literature and Practices in and around the Low Countries (13th–17th centuries)’, funded by the Dutch ?rganisation for Scientific Research. With a team of international researchers, she is currently developing the Sammelband 15–16 book historical project, for which she received the Descartes-Huygens Prize from the French and Dutch Academies of Sciences in 2018.
PY - 2012
Y1 - 2012
N2 - Identity disclosure control (IDC) on complex data has attracted increasing interest in security and database communities. Most existing work focuses on preventing identity disclosure in graphs that describes pairwise relations between data entities. Many data analysis applications need information about multi-relations among entities, which can be well represented with hypergraphs. However, the IDC problem has been little studied in publishing hypergraphs due to the diversity of hypergraph information which may expose to many types of background knowledge attacks. In this paper, we introduce a novel attack model with the properties of hyperedge rank as background knowledge, and formalize the rank-based hypergraph anonymization (RHA) problem. We propose an algorithm running in near-quadratic time on hypergraph size for rank anonymization which we show to be NP-hard, and in the meanwhile, maintaining data utility for community detection. We also show how to construct the hypergraph under the anonymized properties to protect a hypergraph from rank-based attacks. The performances of the methods have been validated by extensive experiments on real-world datasets. Our rank-based attack model and algorithms for rank anonymization and hypergraph construction are, to our best knowledge, the first systematic study for private hypergraph publishing.
AB - Identity disclosure control (IDC) on complex data has attracted increasing interest in security and database communities. Most existing work focuses on preventing identity disclosure in graphs that describes pairwise relations between data entities. Many data analysis applications need information about multi-relations among entities, which can be well represented with hypergraphs. However, the IDC problem has been little studied in publishing hypergraphs due to the diversity of hypergraph information which may expose to many types of background knowledge attacks. In this paper, we introduce a novel attack model with the properties of hyperedge rank as background knowledge, and formalize the rank-based hypergraph anonymization (RHA) problem. We propose an algorithm running in near-quadratic time on hypergraph size for rank anonymization which we show to be NP-hard, and in the meanwhile, maintaining data utility for community detection. We also show how to construct the hypergraph under the anonymized properties to protect a hypergraph from rank-based attacks. The performances of the methods have been validated by extensive experiments on real-world datasets. Our rank-based attack model and algorithms for rank anonymization and hypergraph construction are, to our best knowledge, the first systematic study for private hypergraph publishing.
KW - Anonymization
KW - Community detection
KW - Identity disclosure control
KW - Private hypergraph publishing
UR - http://www.scopus.com/inward/record.url?scp=84861437198&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-30220-6_29
DO - 10.1007/978-3-642-30220-6_29
M3 - Conference contribution
AN - SCOPUS:84861437198
SN - 9783642302190
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 347
EP - 358
BT - Advances in Knowledge Discovery and Data Mining - 16th Pacific-Asia Conference, PAKDD 2012, Proceedings
T2 - 16th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2012
Y2 - 29 May 2012 through 1 June 2012
ER -