基于差分隐私的权重社会网络隐私保护

doi:10.11959/j.issn.1000-436x.2015165

摘要/Abstract

摘要：

针对权重社会网络发布隐私保护中的弱保护问题，提出一种基于差分隐私模型的随机扰动方法可实现边及边权重的强保护。设计了满足差分隐私的查询模型-WSQuery,WSQuery 模型可捕获权重社会网络的结构，以有序三元组序列作为查询结果集；依据 WSQuery 模型设计了满足差分隐私的算法-WSPA,WSPA 算法将查询结果集映射为一个实数向量，通过在向量中注入Laplace噪音实现隐私保护；针对WSPA算法误差较高的问题提出了改进算法-LWSPA,LWSPA算法对查询结果集中的三元组序列进行分割，对每个子序列构建满足差分隐私的算法，降低了误差，提高了数据效用。实验结果表明，提出的隐私保护方法在实现隐私信息的强保护同时使发布的权重社会网络仍具有可接受的数据效用。

关键词: 权重社会网络, 隐私保护, 差分隐私, 查询模型, Laplace分布

Abstract:

Focusing on the weak protection problems in privacy preservation of weighted social networks publication,a privacy preserving method based on differential privacy was put forward for strong protection of edges and edge weights.The WSQuery query model was proposed meeting with differential privacy on weighted social networks,could capture the structure of weighted social networks and returned the triple sequences as the query result set.The WSPA algorithm was designed according to the WSQuery model,could map the query result set into a real number vector and injected Laplace noise into the vector to realize privacy protection.The LWSPA algorithm was put forward because of the high error of the WSPA algorithm,partitioned the triples sequence of the query results into multiple subsequences,constructed the algorithms for each subsequence according with differential privacy and reduced the error and improved the data util-ity.The experimental results demonstrate that the proposed method can provide strong protection for privacy information,simultaneously the utility of the released weighted social networks is still acceptable.

Key words: weighted social network, privacy preserving, differential privacy, query model, Laplace distribution

兰丽辉,鞠时光. 基于差分隐私的权重社会网络隐私保护[J]. 通信学报, 2015, 36(9): 145-159.

Li-hui LAN,Shi-guang JU. Privacy preserving based on differential privacy for weighted social networks[J]. Journal on Communications, 2015, 36(9): 145-159.

图/表 11

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

参考文献 34

[1]	ZHELEVA E , GETOOR L . Preserving the privacy of sensitive rela-tionships in graph data[J]. Lecture Notes in Computer Science, 2008,4890:153-171.
[2]	CAMPAN A , TRUTA T M . Data and structural k-anonymity in social networks[J]. Lecture Notes in Computer Science, 2009,5456:33-54.
[3]	CORMODE G , SRIVASTAVA D , YU T . Anonymizing bipartite graph data using safe groupings[J]. VLDB Journal, 2010,19(1): 115-139.
[4]	SIHAG V K . A clustering approach for structural k-anonymity in social networks using genetic algorithm[A]. Proceeding of the Interna-tional Information Technology Conference[C]. CUBE,ACM, 2012.701-706.
[5]	TASSA T , COHEN D . Anonymization of centralized and distributed social networks by sequential clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2013,25(2): 311-324.
[6]	BABU K S , JENA S K . Anonymizing social networks:a generalization approach[J]. Computers &Electrical Engineering, 2013,39(7): 1947-1961.
[7]	HSU T , LIAU C J , WANG D W . A logical framework for pri-vacy-preserving social network publication[J]. Journal of Applied Logic, 2014,12(2): 151-174.
[8]	KULKARNI A R , YOGISH H K . Advanced unsupervised anonymiza-tion technique in social networks for privacy preservation[J]. Interna-tional Journal, 2014.118-125.
[9]	ZHOU B , PEI J . Preserving privacy in social networks against neigh-borhood attacks[A]. Proceeding of ICDE'08[C]. Cancun,Mexico, 2008.506-515.
[10]	LIU K , TERZI E . Towards identity anonymization on graphs[A]. Proceedings of SIGMOD'08[C]. ACM, 2008.93-106.
[11]	HAY M , MIKLAU G , JENSEN D , et al. Anonymizing Social Net-works[R]. Technical Report,University of Massachusetts Amherst, 2007.173-187.
[12]	YING X W , WU X T . Randomizing social networks:a spectrum preserving approach[A]. Proceeding of SIAM'08[C]. Atlanta,United States, 2008.739-750.
[13]	ZOU L , CHEN L , ?ZSU M T . K-automorphism:general framework for privacy reserving network publication[A]. Proceeding of VLDB'09[C]. Lyon,France, 2009.946-957.
[14]	TRIPATHY B K , SISHODIA M S , JAIN S , et al. Privacy and Ano-nymization in Social Networks[M]. Springer International Publishing, 2014.243-270.
[15]	TRIPATHY B K , PANDA G K . A new approach to manage security against neighborhood attacks in social networks[A]. Proceeding of ASONAM'10[C]. 2010.264-269.
[16]	TRUTA T M , CAMPAN A , RALESCU A L . Preservation of structural properties in anonymized social networks[A]. Proceeding of the 8th Collaborative Computing:Networking,Applications and Workshar-ing[C]. 2012.619-627.
[17]	MASOUMZADEH A , JOSHI J . Preserving structural properties in edge-perturbing anonymization techniques for social net-works[J]. IEEE Transactions on Dependable and Secure Computing, 2012,9(6): 877-889.
[18]	熊平，朱天清，王晓峰 . 差分隐私保护及其应用[J]. 计算机学报， 2014,37(1): 101-122. XIONG P , ZHU T Q , WANG XF . A survey on differential privacy and applications[J]. Chinese Journal of Computers, 2014,37(1): 101-122.
[19]	LIU L , WANG J , LIU J , et al. Privacy Preserving in Social Networks Against Sensitive Edge Disclosure[R]. Technical Report CMIDA-HiPSCCS 006-08.Department of Computer Science,University of Kentucky,KY, 2008.
[20]	DAS S , EGECIOGLU ? , ABBADI A E . Anónimos:an LP-based approach for anonymizing edge-weighted social network graphs[J]. IEEE Transac-tions on Knowledge and Data Engineering, 2012,4(4): 590-603.
[21]	SKARKALA M E , MARAGOUDAKIS M , GRITZALIS S , et al. Privacy preservation by k-anonymization of weighted social net-works[A]. Proceeding of ASONAM'12[C].IEEE Computer Society, 2012.423-428.
[22]	LI Y , SHEN H . Anonymizing graphs against weight-Based attacks[A]. Proceeding of ICDMW'10[C]. 2010.491-498.
[23]	HAY M , LI C , MIKLAU G , et al. Accurate estimation of the degree distribution of private networks[A]. Proceedings of ICDM '09, Miami,United States, 2009.169-178.
[24]	SALA A , ZHAO X H , WILSON C , et al. Sharing graphs using differentially private graph models[A]. Proceedings of SIG-COMM'11, Berlin,Germany, 2011.81-98.
[25]	KASIVISWANATHAN S P , NISSIM K , RASKHODNIKOVA S , et al. Analyzing Graphs with Node Differential Privacy[M]. Theory of Cryp-tography,Springer Berlin Heidelberg, 2013.457-476.
[26]	DWORK C . Differential Privacy[M]. Automata,Languages and Pro-gramming,Springer Berlin Heidelberg, 2006.1-12.
[27]	张啸剑，孟小峰 . 面向数据发布和分析的差分隐私保护[J]. 计算机学报， 2014,37(4): 927-949. ZHANG X J , MENG X F . Differential privacy in data publication and analysis[J]. Chinese Journal of Computers, 2014,37(4): 927-949.
[28]	DWORK C , MCSHERRY F , NISSIM K , et al. Calibrating Noise to Sensitivity in Private Data Analysis[M]. Springer Berlin Heidelberg, 2006.265-284.
[29]	HAY M , RASTOGI V , MIKLAU G , et al. Boosting the accuracy of differentially private histograms through consistency[J]. Proceedings of the VLDB Endowment, 2010,3(1): 1021-1032.
[30]	DWORK C . Differential Privacy:a Survey of Results[M]. Springer Berlin Heidelberg, 2008.1-19.
[31]	Karate[EB/OL]. , 2011-01-05/2012-03-02.
[32]	Lesmis[EB/OL]. , 2011-08-18/2012-03-02.
[33]	Prefuse[EB/OL]. , 2007-10-21/2012-03-02.
[34]	PowerGrid[EB/OL]. , 2013-04-15/2013-05-02.