Anonymizing Graphs

Details Anonymizing Graphs Anonymizing Graphs

2008-10-30

arxiv.org/abs/0810.5578v1

Computer Science

Databases

15 pages, 5 figures

Scientific paper

Motivated by recently discovered privacy attacks on social networks, we study the problem of anonymizing the underlying graph of interactions in a social network. We call a graph (k,l)-anonymous if for every node in the graph there exist at least k other nodes that share at least l of its neighbors. We consider two combinatorial problems arising from this notion of anonymity in graphs. More specifically, given an input graph we ask for the minimum number of edges to be added so that the graph becomes (k,l)-anonymous. We define two variants of this minimization problem and study their properties. We show that for certain values of k and l the problems are polynomial-time solvable, while for others they become NP-hard. Approximation algorithms for the latter cases are also given.

Affiliated with

Also associated with

No associations

Rating

Anonymizing Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Anonymizing Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Anonymizing Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-456435