We live in an era of social networks where privacy control is a massive concern. Users leave digital traces, which may breach privacy even after anonymization. Social networking service providers collect user-provided data, and the users (naturally) want to share their information with their connections and with the outside world in a controlled manner while preserving their privacy. One naive way to control privacy is to anonymize the user through omission of basic identification information. Though a number of defense and attack algorithms have been proposed concerning privacy control, the area is still quite new and a lot of work needs to be done. In this paper, the authors propose a deanonymization algorithm to orchestrate an attack against anonymized social networks.

In the graph model of the social network, the authors define privacy as the “knowledge of existence or absence of vertices, edges, or labels,” as well as “betweenness, closeness, and centrality” in metric terms. They also use utility as a dimension to measure “information loss and distortion in the anonymization process,” and the attacker’s background knowledge as a possible way to “compromise privacy protection.” Both the anonymized network and the attacker’s background knowledge are graphs. The seed-and-grow algorithm “first identifies a seed subgraph, either planted by an attacker or divulged by collusion of a small group of users, and then grows the seed larger based on the attacker’s existing knowledge of the users’ social relations.” Simulation on real-world data verifies the authors’ claims on the effectiveness and accuracy of user identification in anonymized social networks using their method.

The paper is good for easy reading and I recommend it to readers interested in graphs and networks.