Research On Spectrum-based Privacy Protection Technology In Weighted Social Networks

The macro nature of social networks has always been a hot topic of scientific research,which is of great help in studying the characteristics of human social behavior.In order to protect the privacy of users,the owner needs to provide privacy protection when he wants to provide queries or publish data.Privacy protection needs to maintain a balance between data security and availability.Traditional privacy protection methods,such as K-anonymity,random perturbation,can guarantee the security of data,but it has a great damage to the usability of graph.The spectrum is closely related to the nature of the network and determines certain information,including community division,loop,diameter,degree and so on.With the development of spectral theory,some spectral-based privacy protection methods have been emerged,such as singular value decomposition perturbations and eigenvalue perturbations.These methods can preserve the features of the graph data in a better performance but most of them are directed to the unweighted network and lack the security analysis and security models.To realize the security requirement of the spectral decomposition based privacy protection,the singular value decomposition is taken as an example in this paper to analyze and indicate that it has the risk of being reconstructed for the weighted network.Since the number of discarded spectra is a core issue in these methods,the impact of that on security is mainly analyzed.Firstly,three methods in network are proposed: one reconstruction method with integer weights and two inexact reconstruction methods with arbitrary weights.To evaluate the security,the reconfigurable coefficient ? and ?/N-tolerance of the network are defined.It is pointed that the upper bound of ? obtained by the current spectrum theory is too conservative and lacks guidance.The reconfigurable coefficients of model networks and actual networks are tested experimentally.The experimental results show that the ?/N-tolerance is independent of the network scale and closely related to other parameters of the network.It also indicates that weighted social networks have great tolerances on spectrum loss.Even if the network is double-disturbed,there is still existing the danger of being reconstructed and being inaccurately reconstructed when the ratio of deleted spectrum is less than 5%~50%.Although the spectral decomposition based method provides an accurate spectrum,it ignores the disclosure of privacy data in spectral query.To solve these problems,the differential privacy security framework is used to propose three algorithms for privacy protection of edge weights in spectrum query.Firstly,the basic concepts of edge weight neighbor graph and edge weight difference privacy are given,according to the definition of reconfiguration.For the single singular value query,the L1 global sensitivity of the function is analyzed and proved,and an algorithm satisfying ?-differential privacy is designed by using Laplace mechanism.It can guarantee the privacy of edge weights when we query someone singular value.However,it cannot provide reasonable privacy protection for multiple singular values queries.So the L2 global sensitivity of the query for multiple singular values is further analyzed and proved,and the Gaussian mechanism is used to design an algorithm that satisfies(?,?)-differential privacy.Finally,to combine with multi-singular values query strategy and spectral decomposition,a novel graph data publishing algorithm which can guarantee(?,?)-edge weight differential privacy is proposed.To verify the availability of these methods,experimental tests have been carried out in both model networks and actual networks,which shows that the algorithm can better guarantee the availability of data.