Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Anonymizing Graphs   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.

9
The categories of this paper are: nlin
2
The categories of this paper are: math
22
The categories of this paper are: chao-dyn
8
The categories of this paper are: hep-ex
30
The categories of this paper are: q-alg
33
The categories of this paper are: plasm-ph
0
The categories of this paper are: hep-ph
36
The categories of this paper are: cmp-lg
28
The categories of this paper are: alg-geom
5
The categories of this paper are: gr-qc
31
The categories of this paper are: ao-sci
17
The categories of this paper are: q-fin
18
The categories of this paper are: econ
25
The categories of this paper are: patt-sol
23
The categories of this paper are: solv-int
20
The categories of this paper are: acc-phys