Privacy-Preserving Social Network Publication Based on Positional Indiscernibility

摘要

In this paper, we address the issue of privacy preservation in the context of publishing social network data. The individuals in pub- . lished social networks are typically anonymous; however, an adversary may be able to combine the released anonymous social network data with publicly available non-sensitive information to re-identify the individuals in a social network. In this paper, we consider the case that an adversary can query such publicly available databases with description logic(DL) concepts. To address the privacy issue, we utilize social position analysis techniques to determine the indiscernibility of individuals in a social network. Social position analysis attempts to find individuals that occupy the same position in a social network based on the pattern of their relationships to other actors. Recently, it was shown that social positions can be characterized by modal logics; thus, individuals occupying the same social position will satisfy the same set of modal formulas. Since DL has a close correspondences with modal logic, individuals occupying the same social position can not be distinguished by the knowledge expressed in DL formalisms. By partitioning a set of individuals into indiscernible classes in this way, we can easily test the safety of publishing the social network data.