Preserving Privacy with Probabilistic Indistinguishability in Weighted Social Networks

被引:134
作者
Liu, Qin [1 ]
Wang, Guojun [2 ]
Li, Feng [3 ]
Yang, Shuhui [4 ]
Wu, Jie [5 ]
机构
[1] Hunan Univ, Coll Comp Sci & Elect Engn, Changsha 410082, Hunan, Peoples R China
[2] Guangzhou Univ, Sch Comp Sci & Educ Software, Guangzhou 510006, Guangdong, Peoples R China
[3] Indiana Univ Purdue Univ, Dept Comp & Informat Technol, Indianapolis, IN 46202 USA
[4] Purdue Univ Calumet, Dept Math Comp Sci & Stat, Hammond, IN 46323 USA
[5] Temple Univ, Dept Comp & Informat Sci, Philadelphia, PA 19122 USA
关键词
Weighted social networks; weighted 1(star)-neighborhood attack; probabilistic indistinguishability; privacy;
D O I
10.1109/TPDS.2016.2615020
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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.
引用
收藏
页码:1417 / 1429
页数:13
相关论文
共 27 条
[1]  
[Anonymous], 2010, Proceedings of the 19th International Conference on World Wide Web, WWW'10, DOI DOI 10.1145/1772690.1772778
[2]  
[Anonymous], 2006, KDD
[3]  
[Anonymous], 1999, SIDLWP19990120
[4]  
[Anonymous], 2014, SOCIAL NETW ANAL MIN
[5]  
[Anonymous], 2008, Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data
[6]  
[Anonymous], ANONYMIZING SOCIAL N
[7]   Emergence of scaling in random networks [J].
Barabási, AL ;
Albert, R .
SCIENCE, 1999, 286 (5439) :509-512
[8]   Identity obfuscation in graphs through the information theoretic lens [J].
Bonchi, Francesco ;
Gionis, Aristides ;
Tassa, Tamir .
INFORMATION SCIENCES, 2014, 275 :232-256
[9]   Design and analysis of a social botnet [J].
Boshmaf, Yazan ;
Muslukhov, Ildar ;
Beznosov, Konstantin ;
Ripeanu, Matei .
COMPUTER NETWORKS, 2013, 57 (02) :556-578
[10]  
Campan A., 2008, P 2 ACM SIGKDD WORKS, P33