Private Social Network Analysis: How to Assemble Pieces of a Graph PrivatelyAuthors: K. Frikken and P. Golle.
Abstract: To assuage these privacy concerns, we propose reconstructing the whole graph privately, i.e., in a way that hides the correspondence between the nodes and edges in the graph and the reallife entities and relationships that they represent. We first model the privacy threats posed by the private reconstruction of a distributed graph. Our model takes into account the possibility that malicious nodes may report incorrect information about the graph in order to facilitate later attempts to deanonymize the reconstructed graph. We then propose protocols to privately assemble the pieces of a graph in ways that mitigate these threats. These protocols severely restrict the ability of adversaries to compromise the privacy of honest subjects.
