Anonymizing graphs against weight-based attacks

Yidong Li, Hong Shen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

28 Citations (Scopus)


The increasing popularity of graph data, such as social and online communities, has initiated a prolific research area in knowledge discovery and data mining. As more real-world graphs are released publicly, there is growing concern about privacy breaching for the entities involved. An adversary may reveal identities of individuals in a published graph by having the topological structure and/or basic graph properties as background knowledge. Many previous studies addressing such attack as identity disclosure, however, concentrate on preserving privacy in simple graph data only. In this paper, we consider the identity disclosure problem in weighted graphs. The motivation is that, a weighted graph can introduce much more unique information than its simple version, which makes the disclosure easier. We first formalize a general anonymization model to deal with weight-based attacks. Then two concrete attacks are discussed based on weight properties of a graph, including the sum and the set of adjacent weights for each vertex. We also propose a complete solution for the weight anonymization problem to prevent a graph from both attacks. Our approaches are efficient and practical, and have been validated by extensive experiments on both synthetic and real-world datasets.

Original languageEnglish
Title of host publicationProceedings - 10th IEEE International Conference on Data Mining Workshops, ICDMW 2010
Number of pages8
Publication statusPublished - 2010
Externally publishedYes
Event10th IEEE International Conference on Data Mining Workshops, ICDMW 2010 - Sydney, NSW, Australia
Duration: 14 Dec 201017 Dec 2010

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786


Conference10th IEEE International Conference on Data Mining Workshops, ICDMW 2010
CitySydney, NSW


  • Anonymity
  • Privacy preserving graph mining
  • Weight anonymization
  • Weighted graph


Dive into the research topics of 'Anonymizing graphs against weight-based attacks'. Together they form a unique fingerprint.

Cite this