Accés ràpid intranet

Més informació...

a a a



k-Anonymity for social networks and graphs


Klara Stokes (joint work with Vicen Torra)

Professor/a organitzador/a

Maria Bras-Amors




18-04-2012 12:30


Relations can be represented using graphs. Databases that contain relations are common for example in research areas as epidemiology and sociology. The concern of data privacy is to protect the database, so that the researchers can access the data without violating the privacy of the individuals behind the records. A popular approach for protecting tabular data is to k-anonymize the data. A table is k-anonymous if there are k copies of every record in the restriction of the table to any collection of attributes (quasi-identifier) that makes reidentification possible. It has been argued that achieving k-anonymity for graphs is more complicated than for pure tabular data, and several quasi-identifiers have been suggested. We argue that k-anonymity for graphs is a special case of k-anonymity for tabular data. The adjacency matrix is a loss-less representation of the graph in table form. If we can k-anonymize the adjacency matrix, the graph will be k-anonymous with respect to any possible graph property that comes in mind. In this talk I will characterize the k-anonymous graphs from the combinatorial point of view. I will also present a relaxation of k-anonymity for graphs and relate this to some approaches for clustering in graphs. Finally I will discuss some possible open questions of future research.


Aula 204