社交网络下的不确定图隐私保护算法
|
摘要
社交网络平台的快速普及使得社交网络中的个人隐私泄露问题愈发受到用户的关心,传统的数据隐私保护方法无法满足用户数量巨大、关系复杂的社交网络隐私保护需求.图修改技术是针对社交网络数据的隐私保护所提出的一系列隐私保护措施,其中不确定图是将确定图转化为概率图的一种隐私保护方法.主要研究了不确定图中边概率赋值算法,提出了基于差分隐私的不确定图边概率赋值算法,该算法具有双重隐私保障,适合社交网络隐私保护要求高的场景.同时提出了基于三元闭包的不确定图边概率分配算法,该算法在实现隐私保护的同时保持了较高的数据效用,适合简单的社交网络隐私保护场景.分析与比较表明:与(k,ε)-混淆算法相比,基于差分隐私的不确定图边概率赋值算法可以实现较高的隐私保护效果,基于三元闭包的不确定图边概率分配算法具有较高的数据效用性.最后,为了衡量网络结构的失真程度,提出了基于网络结构熵的数据效用性度量算法,该算法能够度量不确定图与原始图结构的相似程度.
The rapid popularization of the social network platform is causing growing concern among users of personal privacy disclosure in social networks, and due to the characters of social network which have the large number of users and with complicated relationships, the traditional privacy preserving method cannot be applied to the social network privacy protection which have a number of users and complicated. Graph modification technique is a series of privacy preserving methods proposed for the privacy preserving of social network data. Uncertain graph is a privacy preserving method, which converting a deterministic graph into a probability graph. In this study, the edge probability assignment algorithm is mainly focused on in the uncertain graph, and an algorithm for assigning the edge probability assignment is proposed based on differential privacy. The algorithm has a double privacy protection, which is suitable for social networks with high privacy requirements. Meanwhile, a different algorithm of uncertain graphs' edge probability assignment is presented based on the triadic closure, which achieves privacy preserve while maintains high data utility and suitable for simple social networks. The analysis and comparison show that the algorithm for assigning the edge probabilities of uncertain graph based on differential privacy can achieve a higher privacy preserving which was compared with obfuscation algorithm, and the algorithm of uncertain graphs' edge probability assignment based on triadic closure has higher data utility. Finally, in order to measure the distortion of the network structure, a data utility measure is proposed based on network structure entropy. The algorithm can measure the similarity between the uncertain graph and the original structure.
The rapid popularization of the social network platform is causing growing concern among users of personal privacy disclosure in social networks, and due to the characters of social network which have the large number of users and with complicated relationships, the traditional privacy preserving method cannot be applied to the social network privacy protection which have a number of users and complicated. Graph modification technique is a series of privacy preserving methods proposed for the privacy preserving of social network data. Uncertain graph is a privacy preserving method, which converting a deterministic graph into a probability graph. In this study, the edge probability assignment algorithm is mainly focused on in the uncertain graph, and an algorithm for assigning the edge probability assignment is proposed based on differential privacy. The algorithm has a double privacy protection, which is suitable for social networks with high privacy requirements. Meanwhile, a different algorithm of uncertain graphs' edge probability assignment is presented based on the triadic closure, which achieves privacy preserve while maintains high data utility and suitable for simple social networks. The analysis and comparison show that the algorithm for assigning the edge probabilities of uncertain graph based on differential privacy can achieve a higher privacy preserving which was compared with obfuscation algorithm, and the algorithm of uncertain graphs' edge probability assignment based on triadic closure has higher data utility. Finally, in order to measure the distortion of the network structure, a data utility measure is proposed based on network structure entropy. The algorithm can measure the similarity between the uncertain graph and the original structure.
引文
[1]T1 life.Ten major data breaches in 2016:Social networking has become a harder-hit area(in Chinese).2016.http://www.sohu.com/a/122021640_5266-42
[2]Liu XY,Wang B,Yang XC.Survey on privacy preserving techniques for publishing social network data.Ruan Jian Xue Bao/Journal of Software,2014,25(3):576-590(in Chinese with English abstract).http://www.jos.org.cn/1000-9825/4511.htm[doi:10.13328/j.cnki.jos.004511]
[3]Backstrom L,Dwork C,Kleinberg J.Wherefore art thou r3579x:Anonymized social networks,hidden patterns,and structural steganography.In:Proc.of the 16th Int’l Conf.on World Wide Web.New York:ACM,2007.181-190.[doi:10.1145/1242572.1242598]
[4]Dwork C.Differential privacy:A survey of results.In:Proc.of the Int’l Conf.on Theory and Applications of Models of Computation.Springer-Verlag,2008.1-19.[doi:10.1007/978-3-540-79228-4_1]
[5]Hay M,Li C,Miklau G,et al.Accurate estimation of the degree distribution of private networks.In:Proc.of the IEEE Int’l Conf.on Data Mining.Washington:IEEE Computer Society,2009.169-178.[doi:10.1109/ICDM.2009.11]
[6]Day WY,Li N,Lyu M.Publishing graph degree distribution with node differential privacy.In:Proc.of the Int’l Conf.on Management of Data.New York:ACM,2016.123-138.[doi:10.1145/2882903.2926745]
[7]Karwa V,Raskhodnikova S,Smith A,et al.Private analysis of graph structure.ACM Trans.on Database Systems,2014,39(3):1146-1157.[doi:10.1145/2611523]
[8]Task C,Clifton C.A guide to differential privacy theory in social network analysis.In:Proc.of the IEEE Int’l Conf.on Advances in Social Networks Analysis and Mining.Washington:IEEE Computer Society,2012.411-417.[doi:10.1109/ASONAM.2012.73]
[9]Stokes K,Torra V.On some clustering approaches for graphs.In:Proc.of the IEEE Int’l Conf.on Fuzzy Systems.IEEE,2011.409-415.[doi:10.1109/FUZZY.2011.6007447]
[10]Hay M,Miklau G,Jensen D,et al.Resisting structural re-identification in anonymized social networks.VLDB Journal,2010,19(6):797-823.[doi:10.14778/1453856.1453873]
[11]Zheleva E,Getoor L.Preserving the privacy of sensitive relationships in graph data.In:Proc.of the ACM SIGKDD Int’l Conf.on Privacy,Security,and Trust in KDD.Berlin,Heidelberg:Springer-Verlag,2007.153-171.[doi:10.1007/978-3-540-78478-4_9]
[12]Ying X,Wu X.Randomizing social networks:A spectrum preserving approach.In:Proc.of the SIAM Int’l Conf.on Data Mining.SIAM,2008.739-750.[doi:10.1137/1.9781611972788.67]
[13]Liu K,Terzi E.Towards identity anonymization on graphs.In:Proc.of the ACM SIGMOD Int’l Conf.on Management of Data.New York:ACM,2008.93-106.[doi:10.1145/1376616.1376629]
[14]Esmerdag E,Gursoy ME,Inan A,et al.Explode:An extensible platform for differentially private data analysis.In:Proc.of the16th IEEE Int’l Conf.on Data Mining Workshops(ICDMW).IEEE,2016.1300-1303.[doi:10.1109/ICDMW.2016.0189]
[15]Boldi P,Bonchi F,Gionis A,et al.Injecting uncertainty in graphs for identity obfuscation.Proc.of the VLDB Endowment,2012,5(11):1376-1387.[doi:10.14778/2350229.2350254]
[16]Mittal P,Papamanthou C,Song D.Preserving link privacy in social network based systems.Computer Science,2012.
[17]Nguyen HH,Imine A,Rusinowitch M.A maximum variance approach for graph anonymization.In:Proc.of the Int’l Symp.on Foundations and Practice of Security.Cham:Springer-Verlag,2014,8930:49-64.[doi:10.1007/978-3-319-17040-4]
[18]Nguyen HH,Imine A.Anonymizing social graphs via uncertainty semantics.In:Proc.of the 10th ACM Symp.on Information,Computer and Communications Security.New York:ACM,2015.495-506.[doi:10.1145/2714576.2714584]
[19]Hu J.The research on preserving privacy methods in social networks based on uncertainty graph[MS.Thesis].Xi’an:Shaanxi Normal University,2018(in Chinese with English abstract).
[20]Leskovec J,Kleinberg J,Faloutsos C.Graph evolution:Densification and shrinking diameters.ACM Trans.on Knowledge Discovery from Data,2007,1(1):2.[doi:10.1145/1217299.1217301]
[21]Vázquez A.Growing network with local rules:Preferential attachment,clustering hierarchy,and degree correlations.Physical Review E Statistical Nonlinear&Soft Matter Physics,2003,67(2):056104.[doi:10.1103/PhysRevE.67.056104]
[22]Kelly DJ,Raines RA,Grimaila MR,et al.A survey of state-of-the-art in anonymity metrics.In:Proc.of the ACM Workshop on Network Data Anonymization.New York:ACM,2008.31-40.[doi:10.1145/1456441.1456453]
[1]T1生活.2016年十大数据泄露事件:社交网络成泄露重灾区.2016.http://www.sohu.com/a/122021640_526642
[2]刘向宇,王斌,杨晓春.社会网络数据发布隐私保护技术综述.软件学报,2014,25(3):576-590.http://www.jos.org.cn/1000-9825/4511.htm[doi:10.13328/j.cnki.jos.004511]
[19]胡静.基于不确定图的社交网络隐私保护方法研究[硕士学位论文].西安:陕西师范大学,2018.
[2]Liu XY,Wang B,Yang XC.Survey on privacy preserving techniques for publishing social network data.Ruan Jian Xue Bao/Journal of Software,2014,25(3):576-590(in Chinese with English abstract).http://www.jos.org.cn/1000-9825/4511.htm[doi:10.13328/j.cnki.jos.004511]
[3]Backstrom L,Dwork C,Kleinberg J.Wherefore art thou r3579x:Anonymized social networks,hidden patterns,and structural steganography.In:Proc.of the 16th Int’l Conf.on World Wide Web.New York:ACM,2007.181-190.[doi:10.1145/1242572.1242598]
[4]Dwork C.Differential privacy:A survey of results.In:Proc.of the Int’l Conf.on Theory and Applications of Models of Computation.Springer-Verlag,2008.1-19.[doi:10.1007/978-3-540-79228-4_1]
[5]Hay M,Li C,Miklau G,et al.Accurate estimation of the degree distribution of private networks.In:Proc.of the IEEE Int’l Conf.on Data Mining.Washington:IEEE Computer Society,2009.169-178.[doi:10.1109/ICDM.2009.11]
[6]Day WY,Li N,Lyu M.Publishing graph degree distribution with node differential privacy.In:Proc.of the Int’l Conf.on Management of Data.New York:ACM,2016.123-138.[doi:10.1145/2882903.2926745]
[7]Karwa V,Raskhodnikova S,Smith A,et al.Private analysis of graph structure.ACM Trans.on Database Systems,2014,39(3):1146-1157.[doi:10.1145/2611523]
[8]Task C,Clifton C.A guide to differential privacy theory in social network analysis.In:Proc.of the IEEE Int’l Conf.on Advances in Social Networks Analysis and Mining.Washington:IEEE Computer Society,2012.411-417.[doi:10.1109/ASONAM.2012.73]
[9]Stokes K,Torra V.On some clustering approaches for graphs.In:Proc.of the IEEE Int’l Conf.on Fuzzy Systems.IEEE,2011.409-415.[doi:10.1109/FUZZY.2011.6007447]
[10]Hay M,Miklau G,Jensen D,et al.Resisting structural re-identification in anonymized social networks.VLDB Journal,2010,19(6):797-823.[doi:10.14778/1453856.1453873]
[11]Zheleva E,Getoor L.Preserving the privacy of sensitive relationships in graph data.In:Proc.of the ACM SIGKDD Int’l Conf.on Privacy,Security,and Trust in KDD.Berlin,Heidelberg:Springer-Verlag,2007.153-171.[doi:10.1007/978-3-540-78478-4_9]
[12]Ying X,Wu X.Randomizing social networks:A spectrum preserving approach.In:Proc.of the SIAM Int’l Conf.on Data Mining.SIAM,2008.739-750.[doi:10.1137/1.9781611972788.67]
[13]Liu K,Terzi E.Towards identity anonymization on graphs.In:Proc.of the ACM SIGMOD Int’l Conf.on Management of Data.New York:ACM,2008.93-106.[doi:10.1145/1376616.1376629]
[14]Esmerdag E,Gursoy ME,Inan A,et al.Explode:An extensible platform for differentially private data analysis.In:Proc.of the16th IEEE Int’l Conf.on Data Mining Workshops(ICDMW).IEEE,2016.1300-1303.[doi:10.1109/ICDMW.2016.0189]
[15]Boldi P,Bonchi F,Gionis A,et al.Injecting uncertainty in graphs for identity obfuscation.Proc.of the VLDB Endowment,2012,5(11):1376-1387.[doi:10.14778/2350229.2350254]
[16]Mittal P,Papamanthou C,Song D.Preserving link privacy in social network based systems.Computer Science,2012.
[17]Nguyen HH,Imine A,Rusinowitch M.A maximum variance approach for graph anonymization.In:Proc.of the Int’l Symp.on Foundations and Practice of Security.Cham:Springer-Verlag,2014,8930:49-64.[doi:10.1007/978-3-319-17040-4]
[18]Nguyen HH,Imine A.Anonymizing social graphs via uncertainty semantics.In:Proc.of the 10th ACM Symp.on Information,Computer and Communications Security.New York:ACM,2015.495-506.[doi:10.1145/2714576.2714584]
[19]Hu J.The research on preserving privacy methods in social networks based on uncertainty graph[MS.Thesis].Xi’an:Shaanxi Normal University,2018(in Chinese with English abstract).
[20]Leskovec J,Kleinberg J,Faloutsos C.Graph evolution:Densification and shrinking diameters.ACM Trans.on Knowledge Discovery from Data,2007,1(1):2.[doi:10.1145/1217299.1217301]
[21]Vázquez A.Growing network with local rules:Preferential attachment,clustering hierarchy,and degree correlations.Physical Review E Statistical Nonlinear&Soft Matter Physics,2003,67(2):056104.[doi:10.1103/PhysRevE.67.056104]
[22]Kelly DJ,Raines RA,Grimaila MR,et al.A survey of state-of-the-art in anonymity metrics.In:Proc.of the ACM Workshop on Network Data Anonymization.New York:ACM,2008.31-40.[doi:10.1145/1456441.1456453]
[1]T1生活.2016年十大数据泄露事件:社交网络成泄露重灾区.2016.http://www.sohu.com/a/122021640_526642
[2]刘向宇,王斌,杨晓春.社会网络数据发布隐私保护技术综述.软件学报,2014,25(3):576-590.http://www.jos.org.cn/1000-9825/4511.htm[doi:10.13328/j.cnki.jos.004511]
[19]胡静.基于不确定图的社交网络隐私保护方法研究[硕士学位论文].西安:陕西师范大学,2018.