基于谱约束和敏感区划分的社会网络隐私保护扰动方法

摘要：针对社会网络中以社会个体邻域信息作为背景知识进行敏感边识别的攻击，提出了基于谱约束的敏感区划分随机扰动方法。该方法的主要思想是将网络分为敏感区和非敏感区，根据前一次扰动后社会网络图与原始社会网络图谱大小的关系，再基于谱约束条件选择合适的边对社会网络图随机地增删或转换扰动，从而提高社会网络数据的可用性。该方法可以排除无效扰动以提高隐私保护程度，实验结果表明在隐私保护的同时可更好地保持社会网络的结构特性。

关键词：社会网络；谱约束；敏感区；隐私保护；扰动

0引言

社会网络是一个由个人或社区组成的点状网络拓扑结构。其中每个点（Node）代表一个个体，个体与个体之间可能存在各种相互依赖的社会关系，在拓扑网络中用点与点之间的边（Tie）表示。随着社会网络的不断盛行，有关社会网络数据的研究也不断增加。社会网络数据的利用可以为科学研究、组织决策、社会疾病分析等提供帮助。为保证社会网络数据进行顺利分析，要求分析者们所看到的数据尽可能地保持原始社会网络数据的结构特性。

社会网络数据中包含属性数据和关系数据，因此存在隐私泄露的问题。本文关注于关系数据隐私保护的研究：一是研究社会个体间敏感关系的隐私保护；二是研究在保证社会网络中个体间敏感关系不被泄露的同时尽可能高地保证社会网络数据的可用性。

1研究现状

社会网络是一个由个人或社区组成的点状网络拓扑结构，也就是说社会网络已经为用户潜在地组成了一个社交图，它可以让一个人清楚地看到自己或别人的朋友圈子，这就为个人人际关系的泄露带来隐患。

文献[1-2]提出随机化扰动社会网络的方法，该方法通过随机地扰动社会网络的边来保护社会网络的隐私。基本方法有：随机增加/删除边；随机交换边。随着增删、交换边次数的增加可以很好地保护社会网络用户的隐私，但扰动后网络的可用性变得较差。文献[3-5]提出了基于谱约束的随机化扰动方法，相对于随机化社会网络扰动方法它可以很好地保持社会网络的结构特性，但隐私保护的针对性不够强。文献[6-9]针对敏感边敏感节点提出了一个k 匿名方法，相对于随机扰动算法它能更好地保留原始社会网络的结构特性，但隐私保护程度是1/k，不是很理想，而且很难抵制结构攻击。文献[10]采用k 自同构的方法对社会网络的隐私进行保护，在抵制结构攻击上，它比k 匿名算法要好，但此方法转换后的图与原图的差异程度需要有很好的划分和聚类，就现在看来这还是个NP问题，所以不能使转换后的图很好地保持原图的结构特性。

针对以上问题本文提出了基于谱约束和敏感区划分的社会网络隐私保护扰动方法——senSpec算法，此方法是在S_Spec[3]2算法的基础上进行改进得到的。传统的敏感区划分是针对个体的保护，将社会网络图中节点度较大的一些个体作为敏感个体，它们所组成的区域称为敏感区，而本文中侧重于敏感关系的保护，将社会网络中作为不同社区间联系“枢纽”的关系称为敏感关系，敏感关系对应的个体为敏感个体，它们所组成的区域为敏感区。

由实验数据分析可知senSpec算法较S_Spec算法而言在对社会网络数据扰动程度相同的情况下提高了社会网络中敏感边的隐私保护程度，可以抵御结构攻击，且更好地维持了原始社会网络的结构特性。