Preserving Privacy with Probabilistic Indistinguishability in Weighted Social Networks

The increasing popularity of social networks has inspired recent research to explore social graphs for marketing and data mining. As social networks often contain sensitive information about individuals, preserving privacy when publishing social graphs becomes an important issue. In this paper, we consider the identity disclosure problem in releasing weighted social graphs. We identify weighted 1*-neighborhood attacks, which assume that an attacker has knowledge about not only a target's one-hop neighbors and connections between them (1-neighborhood graph), but also related node degrees and edge weights. With this information, an attacker may re-identify a target with high confidence, even if any node's 1-neighborhood graph is isomorphic with k-1 other nodes’ graphs. To counter this attack while preserving high utility of the published graph, we define a key privacy property, probabilistic indistinguishability, and propose a heuristic indistinguishable group anonymization (HIGA) scheme to anonymize a weighted social graph with such a property. Extensive experiments on both real and synthetic data sets illustrate the effectiveness and efficiency of the proposed scheme.