Efficient algorithm on anonymizing social networks with reachability preservation

被引：0
作者：
Liu X.-Y. [1 ]
Li J.-J. [1 ]
An Y.-Z. [1 ]
Zhou D.-H. [1 ]
Xia X.-F. [1 ]
机构：
[1] School of Computer Science, Shenyang Aerospace University, Shenyang
来源：
Ruan Jian Xue Bao/Journal of Software | 2016年 / 27卷 / 08期
基金：
中国国家自然科学基金;
关键词：
Anonymization; Privacy; Reachability; Social network;
D O I：
10.13328/j.cnki.jos.005092
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
As a proven effective solution to privacy preservation, graph anonymization has been studied extensively. The goal of graph anonymization is to avoid disclosure of privacy in social networks through graph modifications while at the same time preserving data utility of the anonymized graph for social network analysis and graph queries. Reachability is an important graph data utility as reachable queries are not only common on graph databases but also serving as fundamental operations for many other graph queries. However, the reachability of each vertex in the anonymized graph is severely distorted after the anonymization due to neglecting that the reachability is highly sensitive to edge modifications. This work solves the problem by designing a reachability preserving anonymization (RPA) algorithm. The main idea of RPA is to organize vertices into groups and greedily anonymizes each vertex with low impact on reachability. A number of techniques are designed to make RPA efficient. Firstly, reachable interval is proposed to efficiently measure the anonymization cost incurred by an edge addition. Secondly, an index structure, CN-index is adopted to accelerate anonymizing each vertex. Extensive experiments on real datasets demonstrate that RPA performs with high efficiency and the generated anonymized social networks preserve high data utility on reachable queries. © Copyright 2016, Institute of Software, the Chinese Academy of Sciences. All rights reserved.
引用
收藏
页码：1904 / 1921
页数：17
相关论文
共 29 条
[1]  
Liu K., Terzi E., Towards identity anonymization on graphs, Proc. of the 2008 ACM SIGMOD Int'l Conf. on Management of Data, pp. 93-106, (2008)
[2]  
Zhou B., Pei J., Preserving privacy in social networks against neighborhood attacks, Proc. of the 24th IEEE Int'l Conf. on Data Engineering, pp. 506-515, (2008)
[3]  
Hay M., Miklau G., Jensen D., Towsley D., Resisting structural identification in anonymized social networks, Proc. of the 34th Int'l Conf. on Very Large Databases, pp. 102-114, (2008)
[4]  
Zou L., Chen L., Ozsu M.T., K-Automorphism: A general framework for privacy preserving network publication, Proc. of the 35th Int'l Conf. on Very Large Databases, pp. 946-957, (2009)
[5]  
Cormode G., Srivastava D., Yu T., Zhang Q., Anonymizing bipartite graph data using safe groupings, Proc. of the 34th Int'l Conf. on Very Large Databases, pp. 833-844, (2008)
[6]  
Bhagat S., Cormode G., Krishnamurthy B., Srivastava D., Class-Based graph anonymization for social network data, Proc. of the 35th Int'l Conf. on Very Large Databases, pp. 766-777, (2009)
[7]  
Fard A.M., Wang K., Yu P.S., Limiting link disclosure in social network analysis through subgraph-wise perturbation, Proc. of the 15th Int'l Conf. on Extending Database Technology, pp. 109-119, (2012)
[8]  
Gao J., Xu J.Y., Jin R., Zhou J., Wang T., Yang D., Neighborhood-Privacy protected shortest distance computing in cloud, Proc. of the 2011 ACM SIGMOD Int'l Conf. on Management of Data, pp. 409-420, (2011)
[9]  
Wang Y., Zheng B., Preserving privacy in social networks against connection fingerprint attacks, Proc. of the 2015 IEEE Int'l Conf. on Data Engineering, pp. 54-65, (2015)
[10]  
Cheng J., Fu A.W.C., Liu J., K-Isomorphism: Privacy preserving network publication against structural attacks, Proc. of the 2010 ACM SIGMOD Int'l Conf. on Management of Data, pp. 459-470, (2010)
123