一种基于滤波的社交网络隐私保护强度评估方法

温 阁 颜 军 胡 静 吴振强

(陕西师范大学计算机科学学院 西安 710119)

(wenge32@snnu.edu.cn)

社交网络是现实生活中人与人关系的一种体现.在社交网络中,用户可以随时随地分享自己的心情状态、生活照片以及日常活动等信息来增强朋友之间的友谊.但当其发布数据时,用户的个人身份、朋友关系、习惯、爱好等会被泄露.而现在出现的一系列网络攻击事件主要利用的是用户发布的某些社交网络数据来挖掘用户的隐私信息.比如,2017年10月,南非发生史上规模最大的数据泄露事件,共有3160万份用户的个人资料被公之于众,连总统祖马和多位部长都未能幸免.此次被黑客公布的数据来源于Dracore Data Sciences企业的GoVault平台,其公司客户包括南非最大的金融信贷机构——TransUnion.2017年11月22日,美国国防部100 GB的顶级机密在AWS上曝光,据外媒报道称,美国五角大楼意外暴露了美国国防部的分类数据库,其中包含美国当局在全球社交媒体平台中收集到的18亿用户的个人信息[1].因此,如何在大家享受社交网络便利的同时,保护个人的敏感信息不被泄露成了急需解决的问题.

社交网络涉及多种角色,并且每个角色之间的关系也相当复杂.为了能够更加详细地描述社交网络中个体之间的关系,可以将社交网络抽象成图结构,用节点表示个体,用边来表示节点之间的关系.因此,通过对图结构进行研究使我们对社交网络的了解能够更加深入.

由于社交网络中包括许多个人隐私,将其抽象为图结构后,图中相应的节点和边也会涉及到个人敏感信息,因此针对社交图隐私保护,目前研究者提出了很多种隐私保护的方式,主要分为3类:标识符替换法、差分隐私法、图结构隐私法.1)标识符替换法.2007年,BackStrom等人[2]提出可以将真实图数据匿名化,使用一些无意义的标识符来代替保护用户的身份信息.2)差分隐私法.2009年,Hay等人[3]提出可以利用差分隐私来实现对社交图中的节点和边进行保护.3)图结构隐私法.针对图结构隐私保护,又分为以下3种.①图聚类方法.2007年,Zheleva和Getoor[4]针对在图数据中出现的链接关系重识别现象,提出了一种基于边的图聚类隐私保护方法.②图修改技术.Hay等人[5]研究了一个评估共享数据隐私风险的框架并与图论联系起来,提出了一种基于扰动的社交图匿名技术,从而减少了隐私风险.③不确定图.2012年Boldi等人[6]首次提出一种不确定图的隐私保护算法,该方法在抗顶点身份攻击的同时保证了图结构数据的最小化失真.

目前对隐私保护方法的评价都是从隐私的位置、关系等方面进行评价的.本文中我们借鉴隐私攻击的方法,从隐私挖掘的角度对隐私保护的强度进行评估.2017年,武汉大学徐正全等人[7]提出了基于滤波原理的时间序列差分隐私保护强度评估,根据信号处理中滤波的原理,设计一个攻击模型来滤除部分噪声,并取得了很好的攻击效果.

现有的社交网络隐私保护方法大都是使用加噪的方式,借鉴信号处理中滤波的原理,我们在不考虑背景知识的前提下,选择能够自动抑制噪声的维纳滤波对邻近图进行去噪来提取有用的信息.另外,我们还提出了一种基于滤波的社交图隐私保护强度评估模型,并在该模型下设计了隐私保护强度评估算法PPIE(privacy preserving intensity evaluation).实验表明,我们的方法能够滤除邻近图中的部分噪声,达到了隐私保护强度评价的目的,也为社交网络隐私保护的理论研究提供了指导.

1 相关工作

在针对社交图隐私攻击的研究中,现有的攻击方式大概有以下几类:1)节点重识别攻击.Narayanan等人[8-9]提出利用种子节点来实现对邻居节点的识别.Abawajy等人[10]提出使用节点对属性进行节点重识别攻击,此攻击利用2个相连顶点的局部区域的信息来识别目标个体.2)属性重识别攻击.Zheleva等人[11]研究发现,参与同一小组的用户倾向于具有相似的属性,并可利用用户的群组标签对用户可能具有的属性进行预测.Mislove等人[12]研究发现,用户可能与其好友具有类似的属性.可以通过好友公开的信息对用户未公开的信息进行推测.3)连接关系重识别攻击.Zhou等人[13]利用朋友间的关系作为弱连接,而将亲戚之间的关系作为强链接,最后发现两者有弱连接关系的人更容易形成朋友关系.4)位置社交关系攻击.Huo等人[14]提出一种以用户的签到历史轨迹、地理位置及各用户间的关系作为背景的签到框架,该系统为了检验用户是否真实签到,将用户可能去过的所有位置进行预测,并将预测到的位置反馈给用户.孟小峰等人[15]介绍了位置大数据的概念以及位置大数据的隐私威胁,总结了针对位置大数据隐私统一的基于度量的攻击模型,对目前位置大数据隐私保护领域已有的研究成果进行了归纳.

为了评价隐私保护的强度,现有的方法是从隐私的位置、关系等方面进行评价.然而,这些方法缺乏具体的评价模型和算法来验证其有效性,隐私保护强度也无法进行统一性的评价.因此,本文给出一种针对加噪型的社交网络隐私保护强度评估模型和算法以解决上述问题.

2 相关知识和理论

本文我们将社交网络抽象成一个无向无权图G(V,E),其中V表示网络中所有节点的集合,E表示网络中所有边的集合.

2.1 高斯噪声

高斯噪声是指它的概率密度函数服从高斯分布的一类噪声.

高斯分布即正态分布,若随机变量X服从一个数学期望为μ、方差为σ2的正态分布,记为N(μ,σ2).其概率密度函数为正态分布的期望值μ决定了其位置,其标准差σ决定了分布的幅度.当μ=0,σ=1时的正态分布是标准正态分布.

2.2 维纳滤波

1)滤波

从连续的(或离散的)输入数据中滤除噪声和干扰,以提取有用信息的过程称为滤波,这是信号处理中经常采用的主要方法之一,具有十分重要的应用价值.

2)维纳滤波

维纳滤波是一种基于最小均方误差准则、对平稳过程的最优估计器.这种滤波器的输出与期望输出之间的均方误差为最小,因此,它是一个最佳滤波系统,它可用于提取被平稳噪声所污染的信号.

2.3 平均度

一个图(或网络)由一些顶点和连接它们的边构成.每个顶点连出的所有边的数量就是这个顶点的度,即指此节点的邻边数量.对网络中所有节点的度求平均可得到网络的平均度[16].

2.4 平均聚集系数

复杂网络中的聚集系数是用来衡量网络集团化程度的重要参数,例如在人际关系网络中你朋友的朋友很可能也是你的朋友,你的2个朋友彼此也可能是朋友,聚集系数就是用来度量网络的这种性质的参数[16].

1)聚集系数

聚集系数是表示一个图形中节点聚集程度的系数.在现实世界的网络,这种可能性往往比2个节点之间随机设立一个连接的平均概率更大.

在无向网络中,可以用聚集系数Ci来表示节点v i的聚集系数,如式(1)[16]:

其中,N表示节点个数;Mi表示实际存在的边数.

2)平均聚集系数

将聚集系数对整个网络作平均,可得到网络的平均聚集系数C,如式(2)[16]:

2.5 介数中心性

在一些大型的实际网络中,每个节点的地位是不同的.要衡量一个节点的重要性其度值可以作为一个衡量指标,但有的节点度虽然小,但它可能是2个集团的中间联络人,如果去掉该节点,会导致2个社团的联系中断,因此该节点在网络中起到极其重要的作用.因此引入介数,反映节点或边在整个网络中的作用和影响力.

节点vi的介数中心性就是节点v i的归一化介数,设节点vi的介数为Bi,则其介数中心性CB(vi)可以定义为式(3)[16]:

2.6 度分布

度分布是图论和网络理论中的概念,度为k的节点在整个网络中所占的比例就是度分布P(k).度分布满足式(4)[16]:

3 基于滤波的一种社交网络隐私保护强度评估方法

由于现有的社交网络隐私保护方法大都是基于加噪的方式提出的,而在信号处理中可以利用滤波对图像去噪.而常用的图像去噪方法有:平滑滤波法、中值滤波法、均值滤波法、维纳滤波等.由于维纳滤波器能够自动抑制噪声的放大,对含噪图像的复原效果较好,可使具有噪声干扰图像的客观复原性能达到全局意义上的最佳[17].因此,本文在不考虑一定的背景知识情况下,采用维纳滤波方法从隐私挖掘的角度评价隐私保护的强度.

本文首先将社交网络隐私保护强度评估抽象成一个模型,然后在该模型下提出一种基于社交网络隐私保护强度评估算法PPIE,并对该模型进行说明;然后给出PPIE算法的伪代码并进行分析;最后,实验结果表明我们的方法能够滤除邻近图中的部分噪声,可以达到对隐私保护强度评价的目的.

3.1 社交网络隐私保护强度评估模型

整体模型(如图1所示)包括3个部分:第1部分是原图;中间部分是邻近图,即隐私保护后的图,这里加入的是高斯噪声,研究者可以根据不同的需求加入不同的噪声来进行隐私保护;第3部分是去噪图,在得到邻近图后,对邻近图进行滤波得到去噪图,研究者可以根据不同的需求提出不同的隐私保护强度评估算法,具体的隐私保护强度评估模型如图2所示.在该模型下,我们提出了一种基于社交网络隐私保护强度评估算法PPIE.

图1 整体模型

图2 隐私保护强度评估模型

3.2 PPIE算法

PPIE算法是利用维纳滤波来实现社交网络隐私保护强度的评价,实验步骤主要由以下5步组成:

1)将图G(V,E)转换成邻接矩阵Matrix;

2)改变高斯噪声中的σ值,得到带高斯噪声的矩阵NoiseMatrix;

3)采用维纳滤波对带噪矩阵NoiseMatrix中的噪音进行滤除,得到矩阵Matrix′;

4)将滤除后的矩阵Matrix′转换成稀疏矩阵S;

5)将稀疏矩阵S转换成图G′.

详细算法如算法1.

算法1.PPIE算法.

输入:G=(V,E);

输出:G′=(V′,E′).

3.3 隐私保护强度评估

为了对隐私保护的强度进行评价,利用维纳滤波的方法滤除邻近图中的噪声,并且利用无向图中的平均度、平均聚集系数、介数中心性和度分布等度量指标来评价隐私保护的强度.若度量指标相等或接近,则说明达到了隐私保护强度评估的目的.同时利用Matlab、Python语言及第三方功能包Network X对本文算法进行程序编程和仿真实验.实验数据分为2部分:真实数据集和合成数据集.真实数据集来自于karate和dolphin俱乐部,合成数据集分别为300和500个节点,连接概率是0.3的随机网络图.为了减少实验数据的随机性,实验分别进行了10次模拟取平均值.其中表1为节点个数N分别为34,61,300,500时,原图与去噪图的度量指标.AD(average degree)表示图中节点的平均度,ACC(average clustering cofficient)表示图中节点的平均聚集系数,BC(betweenness centrality)表示图中节点的介数中心性.

表1 原图与去噪图度量指标比较

图3 N=34,σ=0.1和0.9时度分布图

不同的σ值下,节点个数N为34,61,300,500时对应的度分布图如图3～6所示;其中t代表原图,w代表去噪图.由于度分布图的大体趋势一样,这里只列出了当σ=0.1和0.9时各节点对应的度分布图.

通过观察表1中的度量指标发现,当节点个数较少时,原图与去噪图AD的绝对误差值较小;而无论节点多少,原图与去噪图的ACC,BC的绝对误差值都较小.由此可以看出,经过维纳滤波之后得到的去噪图与原图的AD,ACC,BC的值与原始图比较接近;另外,由分布图可以看出,当σ在(0,1)的范围内,比较原图t和去噪图w,发现两者

图4 N=61,σ=0.1和0.9时度分布图

在变化趋势上非常接近.当N=34时,随着节点度数的变化,节点度分布趋势都是先升后降;当N=61时,随着节点度数的变化,节点度分布总体趋势在降;当N=300时,随着节点度数的变化,节点度分布趋势都是先升后降,但升到最高点后开始下降,不再上升;当N=500时,随着节点度数的变化,节点度分布趋势都是先升后降,与N=300的变化趋势很接近;通过比较4个数据集的原图与去噪图的度量指标发现,经过维纳滤波时之后得到的去噪图与原图的平均度、平均聚集系数、介数中心性和度分布与原始图比较接近,达到了隐私保护强度评估的目的.

图5 N=300,σ=0.1和0.9时度分布图

图6 N=500,σ=0.1和0.9时度分布图

4 结束语

本文针对加噪型的社交网络隐私保护方法缺乏统一性评价的问题,在不考虑一定背景知识的前提下,从隐私挖掘的角度,借鉴信号处理中能够自动抑制噪声的维纳滤波,提出了一种基于滤波的社交网络隐私保护强度评估模型,并且在该模型下设计了隐私保护强度评估(PPIE)算法.为了验证该算法的可行性,将算法应用到2个合成数据集和2个真实的数据集中,并比较原图和经过维纳滤波后的去噪图的度量指标.Matlab和Python仿真实验结果表明,滤波后的去噪图和原图的度量指标基本相似,说明我们的方法达到了评价隐私保护强度的目的,为社交网络隐私保护的理论研究提供了指导.在接下来的工作中,我们将对滤波的方法再进一步地改进,必要时可以加入相应的背景知识来提高隐私挖掘的效果,从而更好地评价隐私保护的强度.

[1]天下数据IDC.盘点2017全球十大数据泄露事件:一件比一件重量级[EB/OL].[2018-03-20].http://www.sohu.com/a/207652321-99931348

[2]Backstrom L,Dwork C,Kleinberg J.Wherefore art thou r3579x?:Anonymized social networks,hidden patterns,and structural steganography[C]//Proc of the 16th Int Conf on World Wide Web.New York:ACM,2007:181-190

[3]Hay M,Li C,Miklau G,et al.Accurate estimation of the degree distribution of private networks[C]//Proc of IEEE Int Conf on Data Mining.Piscataway,NJ:IEEE,2009:169-178

[4]Zheleva E,Getoor L.Preserving the privacy of sensitive relationships in graph data[C]//Proc of ACM SIGKDD Int Conf on Privacy,Security,and Trust in KDD.Berlin:Springer,2007:153-171

[5]Hay M,Miklau G,Jensen D,et al.Anonymizing social networks[OL].[2018-03-15].https://www.research.gate.net/publication/49250847-Anonymizing-Social-Networks

[6]Boldi P,Bonchi F,Gionis A,et al.Injecting uncertainty in graphs for identity obfuscation[J].Proceeding of the VLDB Endowment,2012,5(11):1376-1387

[7]熊文君,徐正全,王豪.基于滤波原理的时间序列差分隐私保护强度评估[J].通信学报,2017,38(5):172-181

[8]Narayanan A,Shmatikov V.Robust de-anonymization of large sparse datasets[C]//Proc of IEEE Symp on Security and Privacy.Piscataway,NJ:IEEE,2008:111-125

[9]Narayanan A,Shmatikov V.De-anonymizing social networks[C]//Proc of IEEE Symp on Security and Privacy.Piscataway,NJ:IEEE,2009:173-187

[10]Abawajy J,Ninggal M I H,Herawan T.Vertex reidentification attack using neighbourhood-pair properties[J].Concurrency and Computation:Practice and Experience,2016,28(10):2906-2919

[11]Zheleva E,Getoor L.To join or not to join:Theillusion of privacy in social networks with mixed public and private user profiles[C]//Proc of Int Conf on World Wide Web.New York:ACM,2008

[12]Mislove A,Viswanath B,Gummadi K P,et al.You are who you know:Inferring user profiles in online social networks[C]//Proc of the 3rd Int Conf on Web Search and Web Data Mining.New York:DBLP,2010:251-260

[13]Zhou Tao,LüLinyuan,Zhang Yicheng.Predicting missing links via local information[J].European Physical Journal B,2009,71(4):623-630

[14]Huo Zheng,Meng Xiaofeng,Zhang Rui.Feel free to check-in:Privacy alert against hidden location inference attacks in GeoSNs[C]//Proc of Int Conf on Database Systems for Advanced Applications.Berlin:Springer,2013:377-391

[15]王璐,孟小峰.位置大数据隐私保护研究综述[J].软件学报,2014,25(4):693-712

[16]郭世泽,陆哲明.复杂网络基础理论[M].北京:科学出版社,2012

[17]卢虹冰.医学成像及处理技术[M].北京:高等教育出版社,2013