Practical anonymity models on protecting private weighted graphs

详细信息    查看全文

• 作者：Yidong Li^a ; ^{ydli@bjtu.edu.cn" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Hong Shen^bAuthor Vitae ; Congyan Lang^aAuthor Vitae ; Hairong Dong^cAuthor Vitae
• 关键词：Anonymity ; Weighted graph ; Privacy preserving graph mining ; Weight anonymization
• 刊名：Neurocomputing
• 出版年：2016
• 出版时间：19 December 2016
• 年：2016
• 卷：218
• 期：Complete
• 页码：359-370
• 全文大小：1600 K

文摘

Identity disclosure control (IDC) on graph data has attracted increasing interest in security and database communities. Most existing work focuses on preventing identity disclosure derivable from certain structural information in unweighted graphs. In weighted graphs, when the weight of an edge implying relevance/association between its adjacency vertices is taken into account, this problem becomes more complex due to the diversity of weight-related information which may expose to many types of background knowledge attacks and hence significantly increases the time complexity for preventing privacy breaches. This paper systematically studies IDC in weighted graphs, which has no known solution to our knowledge, by employing elementary weight invariants as background knowledge. We propose a general anonymity model against weight-related attacks, and introduce a new utility metric based on spectral graph theory. Then we distinguish two types of practical breaches, namely volume and histogram attack, which the adversary has the knowledge of the sum and the set of adjacent weights for each vertex respectively. We propose an efficient method for volume anonymization, and a heuristic scheme for histogram anonymization which we show to be NP-hard. We show how to construct the graph under these anonymized properties to protect a graph from both attacks. Our approaches are effective in terms of efficiency and data utility preservation: run in near-quadratic time on graph size, and preserve a similar utility as the original graph. The performances of the algorithms have been validated by extensive experiments on both synthetic and real-world datasets.