Knowledge discovery on social network data can benefit general public, since these data contain latent social trends and valuable information. Recent research finds that preserving data privacy plays a vital role in knowledge discovery. Therefore, social network data need to be anonymized to preserve users’ identity before the data can be released for research purposes. In this paper, we model social network data as directed graphs with signed edge weights; formally define privacy, attack models for the anonymization problem. Based on our analysis, we develop a graph anonymization approach. The other main contribution is our graph clustering algorithm which can effectively group similar graph nodes into clusters with minimum cluster size constraints. Finally, we carry out a series of experiments to evaluate the effectiveness and utility of our approach on anonymizing social network data.
NarayananA. and ShmatikovV., How to break anonymity of the netflix prize dataset, Proceedings of the IEEE Symposium on Security and Privacy, IEEE, 2008.
2.
LiuK. and TerziE., Towards identity anonymization on graphs, Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, ACM, 2008, pp. 93–106.
3.
YingX. and WuX., Randomizing social networks: A spectrum preserving approachIn SDM, 8, SIAM, 2008, pp. 739–750.
4.
ZouL., ChenL. and ÖzsuM.T., K-automorphism: A general framework for privacy preserving network publication, Proceedings of the VLDB Endowment2(1) (2009), 946–957.
5.
ChengJ., Wai-Chee FuA., LiuJ., K-isomorphism: Privacy preserving network publication against structural attacks, Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, ACM, 2010, pp. 459–470.
6.
HayM., MiklauG., JensenD., TowsleyD. and WeisP., Resisting structural re-identification in anonymized social networks, Proceedings of the VLDB Endowment1(1) (2008), 102–114.
7.
ZhelevaE., GetoorL., (2008)Preserving the privacy of sensitive relationships in graph data. In Privacy, security, and trust in KDD153–171Springer,
8.
ZhouB. and PeiJ., Preserving privacy in social networks against neighborhood attacks, IEEE 24th International Conference on Data Engineering (ICDE’08), IEEE, 2008, pp. 506–515.
9.
BhagatS., CormodeG., KrishnamurthyB. and SrivastavaD., Class-based graph anonymization for social network data, Proceedings of the VLDB Endowment2(1) (2009), 766–777.
10.
ThompsonB. and YaoD., The union-split algorithm and cluster-based anonymization of social networks, Proceedings of the 4th International Symposium on Information, Computer and Communications Security, ACM, 2009, pp. 218–227.
11.
ZhouB. and PeiJ., The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks, Knowledge and Information Systems28(1) (2011), 47–77.
12.
YuanM., ChenL. and YuP.S., Personalized privacy protection in social networks, Proceedings of the VLDB Endowment4(2) (2010), 141–150.
13.
HaoY., CaoH., HuC., BhattaraiK. and MisraS., K-anonymity for social networks containing rich structural and textual information, Social Network Analysis and Mining4(1) (2014), 1–40.
14.
LiuX. and YangX., A generalization based approach for anonymizing weighted social network graphs, Web-Age Information Management, Springer, 2011, pp. 118–130.
15.
SweeneyL., K-anonymity: A model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems10(5) (2002), 557–570.
16.
CormodeG., SrivastavaD., YuT. and ZhangQ., Anonymizing bipartite graph data using safe groupings, Proceedings of the VLDB Endowment1(1) (2008), 833–844.
17.
CartwrightD. and HararyF., Structural balance: A generalization of heider’s theory, Psychological Review63(5) (1956), 277.
18.
DavisJ.A., Clustering and structural balance in graphs, Human relations, 1967.
19.
BatageljV. and MrvarA., Pajek-program for large network analysis, Connections21(2) (1998), 47–57.
20.
DoreianP. and MrvarA., Partitioning signed social networks, Social Networks31(1) (2009), 1–11.
21.
AggarwalG., FederT., KenthapadiK., KhullerS., PanigrahyR., ThomasD. and ZhuA., Achieving anonymity via clustering, Proceedings of the 25th ACM SIGMOD-SIGACTSIGART Symposium on Principles of Database Systems, ACM, 2006, pp. 153–162.
22.
ChakrabartiD., ZhanY. and FaloutsosC., R-mat: A recursive model for graph mining, SDM4, SIAM, 2004, pp. 442–446
23.
C++ Boost. Libraries, 2008
24.
CampanA. and TrutaT.M., Data and structural kanonymity in social networks. In Privacy, Security, and Trust in KDD, Springer, 2009, pp. 33–54.
25.
TaiC-H, YuP.S., YangD-N and ChenM-S, Privacy-preserving social network publication against friendship attacks, Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2011, pp. 1262–1270.
26.
ScottJ., Social network analysis, Sage, 2012.
27.
WattsD.J. and StrogatzS.H., Collective dynamics of small-world networks, Nature393(6684) (1998), 440–442.
28.
ChangC., ThompsonB., WangH. and YaoD., Towards publishing recommendation data with predictive anonymization, Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security, ACM, 2010, pp. 24–35.
29.
DworkC., Differential privacy, Automata, languages and programming, Springer, 2006, pp. 1–12.
