A logical framework for privacy-preserving social network publication

Social network analysis is an important methodology in sociological research. Although social network data are valuable resources for data analysis, releasing the data to the public may cause an invasion of privacy. In this paper, we consider privacy preservation in the context of publishing social network data. To address privacy concerns, information about a social network can be released in two ways. Either the global structure of the network can be released in an anonymized way; or non-sensitive information about the actors in the network can be accessed via a query-answering process. However, an attacker could re-identify the actors in the network by combining information obtained in these two ways. The resulting privacy risk depends on the amount of detail in the released network structure and expressiveness of the admissible queries. In particular, different sets of admissible queries correspond to different types of attacks. In this paper, we propose a logical framework that can represent different attack models uniformly. Specifically, in the framework, individuals that satisfy the same subset of admissible queries are considered indiscernible by the attacker. By partitioning a social network into equivalence classes (i.e., information granules) based on the indiscernibility relation, we can generalize the privacy criteria developed for tabulated data to social network data. To exemplify the usability of the framework, we consider two instances of the framework, where the sets of admissible queries are the ALCIALCI and ALCQIALCQI concept terms respectively; and we exploit social position analysis techniques to compute their indiscernibility relations. We also show how the framework can be extended to deal with the privacy-preserving publication of weighted social network data. The uniformity of the framework provides us with a common ground to compare existing attack models; while its generality could extend the scope of research to meet privacy concerns in the era of social semantic computing.