Academic
Publications
The union-split algorithm and cluster-based anonymization of social networks

The union-split algorithm and cluster-based anonymization of social networks,10.1145/1533057.1533088,Brian Thompson,Danfeng Yao

The union-split algorithm and cluster-based anonymization of social networks   (Citations: 9)
BibTex | RIS | RefWorks Download
Knowledge discovery on social network data can uncover latent social trends and produce valuable findings that ben- efit the welfare of the general public. A growing amount of research finds that social networks play a surprisingly pow- erful role in people's behaviors. Before the social network data can be released for research purposes, the data needs to be anonymized to prevent potential re-identification at- tacks. Most of the existing anonymization approaches were developed for relational data, and cannot be used to handle social network data directly. In this paper, we model social networks as undirected graphs and formally define privacy models, attack mod- els for the anonymization problem, in particular an i-hop degree-based anonymization problem, i.e., the adversary's prior knowledge includes the target's degree and the degrees of neighbors within i hops from the target. We present two new and efficient clustering methods for undirected graphs: bounded t-means clustering and union-split clustering algo- rithms that group similar graph nodes into clusters with a minimum size constraint. These clustering algorithms are contributions beyond the specific social network problems studied and can be used to cluster general data types be- sides graph vertices. We also develop a simple-yet-effective inter-cluster matching method for anonymizing social net- works by strategically adding and removing edges based on nodes' social roles. We carry out a series of experiments to evaluate the graph utilities of the anonymized social net- works produced by our algorithms.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: