  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.
