Research On Topological Structure Based Privacy Protection For Social Networks

Privacy protection of sensitive information in social networks has become an urgent problem to be solved.In the existing social network privacy protection schemes,the privacy protection for nodes and edges are mainly based on randomized perturbation strategy and K anonymity algorithm.These schemes can guarantee data security to a certain extent,but will cause noise redundancy,which means data security and availability cannot be well balanced.Differential privacy has become a hot research topic because it provides more stringent security control.Among these differential privacy schemes,many researches focus on network topology information query such as degree distribution,shortest path distribution etc.In these schemes,the query function is sensitive to network scale,which will change dramatically with network scale,making the implementation process of differential privacy complicated.In addition,these scheme do not consider the combination of vertices protection and edges protection.Thus,two topological structure based privacy preservation algorithms that simultaneously keep vertices and edges privacy information are proposed.In order to effectively reduce noise redundancy and take data security and availability into account,a privacy protection algorithm based on collective influence(CI)is proposed.Firstly,through the detailed introduction and corresponding analysis of CI,the distribution characteristics of CI is obtained.On the basis of fully understanding of CI,a weighted edge perturbation strategy is proposed.CI is used as the noise sources on edge weight perturbation after randomization and normalization.The influence of this strategy on the shortest path in the network is proved by theoretical analysis.Secondly,node perturbation strategy is added based on edge weight perturbation strategy: CI is used as the discriminant index to identify redundant vertices in the network,then some redundant vertices are removed.Experiments show that the distribution of CI is consistent with the network node degree distribution,which agrees with the theoretical analysis.Compared with previous work,it is found that perturbation strategy proposed can retain better data availability and greatly improve data security when achieve the privacy protection for both vertices and edge weights.In order to ensure the data security in network topology information query,a differential privacy security mechanism with average path length(APL)query is proposed,which realize the privacy protection of both network vertices and edge weights.Firstly,by describing the network APL,the reasons for choosing this attribute as the query function are analyzed.Secondly,global sensitivity of APL query under the need of node privacy protection is analyzed and proved.Based on previous studies,the concept of edge-weighted neighborhood graph in differential privacy is proposed,and the global sensitivity of APL-based query under edge-weighted privacy protection is analyzed and proved.Finally,the global sensitivity that content both vertices and edges privacy protection is obtained.The proposed algorithm simplifies the execution process of differential privacy algorithm and ensures that the privacy data in the network,including vertices and edge weights,are not leaked.The relationship between data availability and privacy control parameters in differential privacy is analyzed through experiments.