基于k-度匿名的社会网络隐私保护方法

Privacy Preservation Method Based on k-Degree Anonymity in Social Networks

针对当前社会网络的匿名化隐私保护方法存在信息损失量巨大、网络关系结构被改变严重等问题,提出一种保持网络结构稳定的k-度匿名隐私保护模型Similar Graph,运用动态规划方法对社会网络按照节点度序列进行最优簇划分,然后采用移动边操作方式重构网络图以实现图的k-度匿名化.区别于传统的数值扰乱或图修改如随机增加、删除节点或边等方法,该模型的优势在于既不增加网络边数和节点数,也不破坏网络原有连通性和关系结构.实验结果表明,Similar Graph匿名化方法不仅能有效提高网络抵御度属性攻击的能力,并且还能保持网络结构稳定,同时具有较理想的信息损失代价.

To preserve the privacy of social networks,most existing methods are applied to satisfy different anonymity models,but some serious problems are involved such as often incurring large information losses and great structural modifi-cations of original social network after being anonymized.Therefore,an improved privacy protection model called Similar-Graph is proposed,which is based on k-degree anonymous graph derived from k-anonymity to keep the network structure sta-ble.Where the main idea of this model is firstly to partition network nodes into optimal number of clusters according to de-gree sequences based on dynamic programming,and then to reconstruct the network by means of moving edges to achieve k-degree anonymity with internal relations of nodes considered.To differentiate from traditional data disturbing or graph modif-ying method used by adding and deleting nodes or edges randomly,the superiority of our proposed scheme lies in which nei-ther increases the number of nodes and edges in network,nor breaks the connectivity and relational structures of original net-work.Experimental results show that our SimilarGraph model can not only effectively improve the defense capability against malicious attacks based on node degrees,but also maintain stability of network structure.In addition,the cost of information losses due to anonymity is minimized ideally.