Graph k-Anonymity through k-Means and as Modular Decomposition
2013 (English)In: SECURE IT SYSTEMS, NORDSEC 2013, Springer Berlin/Heidelberg, 2013, Vol. 8208, 263-278 p.Conference paper (Refereed)
In this paper we discuss k-anonymous graphs in terms of modular decomposition and we present two algorithms for the k-anonymization of graphs with respect to neighborhoods. This is the strictest definition of k-anonymity for graphs. The first algorithm is an adaptation of the k-means algorithm to neighborhood clustering in graphs. The second algorithm is distributed of message passing type, and therefore enables user-privacy: the individuals behind the vertices can jointly protect their own privacy. Although these algorithms are not optimal in terms of information loss, they are a first example of algorithms that provide k-anonymization of graphs with respect to the strictest definition, and they are simple to implement.
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013. Vol. 8208, 263-278 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 8208
k-anonymity; graph; modular decomposition; message passing; distributed algorithm; k-means; user-privacy
Computer and Information Science
IdentifiersURN: urn:nbn:se:liu:diva-110507DOI: 10.1007/978-3-642-41488-6_18ISI: 000340414300018ISBN: 978-3-642-41487-9 (print)ISBN: 978-3-642-41488-6 (online)OAI: oai:DiVA.org:liu-110507DiVA: diva2:746388
18th Nordic Conference on Secure IT Systems, NordSec 2013; Ilulissat; Greenland