Research On Privacy-preserving Social Network Analysis: De-anonymization And Seamless Privacy

Over the past few years, the proliferation of online social networking services hascreated numerous amounts of social network data. While these data are valuable to so-ciologists, economists, data-mining researchers and many others, their containing sensi-tive information of individuals have aroused serious privacy concerns, which have thenquickly led into a growing body of eforts in the literature known as privacy-preservingsocial network analysis (PPSNA).Despite of the notable achievements that have been made, research in this area isstill in its infancy. In non-interactive PPSNA, current eforts have been focused on one-time instead of serial releases of social network data. On the one hand, this amplifies theinherent uncertainty of the existing de-anonymization methods, and on the other hand, itmakes it very difcult to carry out dynamic analysis over the anonymized data. In interac-tive PPSNA, where data are accessed through selected queries and privacy is guaranteedby output perturbation, current eforts rely heavily on the Diferential Privacy (DP) the-ory. However, DP is actually specialized for the dealing with tabular data, and is not fitfor the handling of social network data. Particularly, for subgraph counting queries, ex-isting DP-based solutions have to either limit the allowed queries to a restricted range, ortrade too much utility for privacy by adding excess noise to the query answers.In this work, we tried to solve these problems by making the following contribu-tions. First, we propose a threading-based de-anonymization method that can utilize thecorrelations between a dynamic social network’s serial releases to improve the accuracyof re-identification. Then, we propose a connection-rebuilding algorithm to recover thenode-to-node connections between anonymized social network data, so as to enable thedynamic analysis of them. Finally, we propose the Seamless Privacy (SP) frameworkfor the noisy answering of subgraph counting queries in interactive PPSNA. While pri-vacy is theoretically guaranteed, SP can not only deal with all types of subgraph countingqueries, but also reduce the required magnitude of noise significantly.