TY - GEN

T1 - On identity disclosure in weighted graphs

AU - Li, Yidong

AU - Shen, Hong

PY - 2010

Y1 - 2010

N2 - As an integral part of data security, identity disclosure is a major privacy breach, which reveals the identification of entities with certain background knowledge known by an adversary. Most recent studies on this problem focus on the protection of relational data or simple graph data (i.e. undirected, un-weighted and acyclic). However, a weighted graph can introduce much more unique information than its simple version, which makes the disclosure easier. As more real-world graphs or social networks are released publicly, there is growing concern about privacy breaching for the entities involved. In this paper, we first formalize a general anonymizing model to deal with weight-related attacks, and discuss an efficient metric to quantify information loss incurred in the perturbation. Then we consider a very practical attack based on the sum of adjacent weights for each vertex, which is known as volume in graph theory field. We also propose a complete solution for the weight anonymization problem to prevent a graph from volume attack. Our approaches are efficient and practical, and have been validated by extensive experiments on both synthetic and real-world datasets.

AB - As an integral part of data security, identity disclosure is a major privacy breach, which reveals the identification of entities with certain background knowledge known by an adversary. Most recent studies on this problem focus on the protection of relational data or simple graph data (i.e. undirected, un-weighted and acyclic). However, a weighted graph can introduce much more unique information than its simple version, which makes the disclosure easier. As more real-world graphs or social networks are released publicly, there is growing concern about privacy breaching for the entities involved. In this paper, we first formalize a general anonymizing model to deal with weight-related attacks, and discuss an efficient metric to quantify information loss incurred in the perturbation. Then we consider a very practical attack based on the sum of adjacent weights for each vertex, which is known as volume in graph theory field. We also propose a complete solution for the weight anonymization problem to prevent a graph from volume attack. Our approaches are efficient and practical, and have been validated by extensive experiments on both synthetic and real-world datasets.

KW - Anonymity

KW - Privacy preserving graph mining

KW - Weight anonymization

KW - Weighted graph

UR - http://www.scopus.com/inward/record.url?scp=79951787874&partnerID=8YFLogxK

U2 - 10.1109/PDCAT.2010.23

DO - 10.1109/PDCAT.2010.23

M3 - Conference contribution

AN - SCOPUS:79951787874

SN - 9780769542874

T3 - Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

SP - 166

EP - 174

BT - Proceedings - 11th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2010

PB - IEEE Computer Society

ER -