Local Differential Privately Anonymizing Online Social Networks Under HRG-Based Model

Following the trend of online social networks (OSNs) data sharing and publishing, users raise serious concerns on OSN privacy. Differential privacy is a mechanism to anonymize sensitive data. It employs graph abstraction models, such as the hierarchical random graph (HRG) model, to extract graph features and then add sufficient noise. However, the noise amount, determined by the sensitivity, is usually proportional to the size of the whole network. Therefore, achieving global differential privacy may harm the utility of releasing graphs. In this paper, we define the notion of group-based local differential privacy. In particular, by resolving the network into 1-neighborhood graphs and applying HRG-based methods, our scheme preserves differential privacy and reduces the noise scale on the local graphs. By deploying the grouping algorithm, our scheme abandons the attempt to anonymize every relationship to be ordinary, but we focus on the similarities in HRG models. In the final released graph, each individual user in one group is not distinguishable, which greatly enhances the OSN privacy. We experimentally evaluate our approach on three real-world OSNs. It produces synthetic graphs that are more closely matched with the originals compared with the existing differential-privacy results.