Differentially Private Network Graph Data Release Reasearch Via Parametric Graph Model

In the era of big data,the rapid growth of social networks leads to the formation of a huge user groups and information data,the research on social network attributes and operation laws has become a cross-field hot topic.The development of various attacks and analysis technologies pose a serious threat to users' privacy,which thwarts the further expansion and application.Facing the complex correlation and diversification of the big data,traditional methods,based on anonymization,have great limitations to effectively protect privacy under different situations.Differential privacy technology has emerged as a new solution to big data protection and acquired the wide reputation of public in the recent years,due to the resistence to any background knowledge attack and the quantification of privacy protection level.As a new approach to solve the privacy protection of large data applications,differential privacy is superior to deal with non-related data,but it is confronted with great challenge of data protection and mining analysis due to excessive sensitivity problem,so current focus is how to protect privacy while maintaining the accuracy and utility of published data.The privacy information of social network is mainly hidden in the network structure,the node and edge of the network,and the key attribute.This paper deeply studies the structural characteristics of the network and introduces 2 parametric grapg models,SKG(Stochastic Kronecker Graph)and ERGM(Exponential Random Graph Model).Because of the different network modeling scenarios of SKG and ERGM,paper combined with differential privacy,a rigorous mathematical model,to protect the social network graph privacy.The protection method focuses on releasing social network data under differential privacy,and adopts a two-phase privacy budget allocation.In the first stage,we cluster the similar communities of network,according to graph parameter,based on social network community structure.Secondly,we implement optimized privacy budget allocation in terms of cluster distribution.Through the approximate conversion of the parametric graph model,it does not jeopardize the characteristics of the network structure,so the release data can still be used for data analysis and data mining and the internal value of graph data can be captured under great efficiency comparing with the previous research.Eventually we prove methods meet the definition of differential privacy for both SKG and ERGM.The results of experiments show that methods not only effectively protects the privacy of the original structure of the network graph,but also guarantees the accuracy and utilization of released data.