k-automorphism

TLDR

Social network data releases raise privacy concerns because structural queries can reidentify users even after removing personal identifiers. The paper proposes k‑automorphism as a protection against such structural attacks. An algorithm called KM is developed to enforce k‑automorphism, with an extension for dynamic data releases. Experiments show that KM provides strong protection.

Abstract

The growing popularity of social networks has generated interesting data management and data mining problems. An important concern in the release of these data for study is their privacy, since social networks usually contain personal information. Simply removing all identifiable personal information (such as names and social security number) before releasing the data is insufficient. It is easy for an attacker to identify the target by performing different structural queries. In this paper we propose k-automorphism to protect against multiple structural attacks and develop an algorithm (called KM) that ensures k-automorphism. We also discuss an extension of KM to handle "dynamic" releases of the data. Extensive experiments show that the algorithm performs well in terms of protection it provides.