社交网络链路预测的个性化隐私保护方法

孟绪颖1,2 张琦佳1,2 张瀚文1,2 张玉军1,2 赵庆林3

1(中国科学院计算技术研究所 北京 100190)2(中国科学院大学 北京 100049)3(澳门科技大学 澳门 519020)

摘 要 链路预测(link prediction)是社交网络中社交关系预测和推荐的重要手段,然而链路预测过程中需要大量用户个人信息,带来了极大的隐私泄露的危险.用户很可能拒绝提供链路预测需要的信息,这将导致链路预测效果的下降,从而会进一步伤害用户体验.为了打消用户隐私泄露的顾虑,激励用户为链路预测提供更多的数据,提出了一种社交网络链路预测的个性化隐私保护方法.摆脱了对服务商的完全依赖,让用户和服务商共同合作来完成链路预测;为敏感信息和非敏感信息添加不同强度的噪声干扰,保护敏感链路不被泄露的同时维持较好的链路预测效果;并根据用户个性化的隐私设置,保证用户的敏感链路不会被公开的非敏感链路反推.最后,理论证明了提出的方法可以满足ε-差分隐私,并在真实数据集上验证了PrivLP能够在维持较高的链路预测准确性的前提下有效提升隐私保护效果.

关键词 链路预测;社交网络;隐私保护;个性化;差分隐私

链路预测(link prediction)是一种预测节点间关系的重要技术,在社交关系预测[1]、商品推荐[2]等领域得到了学术界和工业界的广泛关注.然而,链路预测过程需要用户社交关系、用户属性等信息,这些信息涉及用户隐私,比如通过用户关注的对象可以分析出用户的宗教信仰等敏感信息.用户为了避免隐私泄露,可能不愿意提供这些信息,这将带来链路预测效果的下降,进一步伤害用户体验.

已有研究提出了在链路预测的过程中为用户提供隐私保护的方法,但目前还存在较多的不足:1)大多数的隐私保护完全依赖于服务商[3].2)有些研究考虑了不可信的服务商,却忽视了不可信的朋友[4].3)为了解决不可信服务商和不可信朋友的问题,部分研究利用加密技术来保证不可信的服务商和朋友不能获取单个用户的个人信息[5].但是,除了加密解密过程带来的计算开销的增加,攻击者仍然可以分析收到的准确计算结果来推断出用户隐私[6].4)社交网络中,用户常常会公开大量非隐私信息,这些信息被攻击者用来反推出用户的隐私信息(即重构攻击[7]),而已有研究都还无法抵御此类攻击.

为了解决现有隐私保护机制的问题和不足,本文设计了一种社交网络链路预测的个性化隐私保护方法,避免不可信的服务商和不可信的朋友对用户敏感链路的推测,并在维持链路预测准确性的前提下提升了隐私保护效果.本文主要的贡献包括3个方面:

1) 提出了一种半集中式的框架.由用户和服务商共同合作完成整个链路预测过程.

2) 提出了一种个性化隐私保护的方法.为了避免不可信服务商和不可信朋友的攻击,将噪声干扰分解为每个用户可独立处理的分量.同时,为敏感信息和非敏感信息添加不同强度的噪声干扰,有效抵御重构攻击的同时保证链路预测的准确度.

3) 从理论上证明我们的个性化的分布式隐私保护机制满足ε-差分隐私,并在真实数据集上验证了其有效性.实验结果表明本文提出的机制实现了隐私保护和链路预测准确性之间的有效平衡.

1 相关工作

本节主要介绍了2类典型的链路预测算法,以及现有的面向链路预测的隐私保护算法.

1.1 链路预测算法

链路预测作为数据挖掘方向的经典问题,在学术界和工业界都受到了广泛关注和重视[1-2].目前链路预测方法主要分为2类:1)基于pointwise的链路预测方法[8].该类方法将训练集中的每对节点作为一个训练数据,将节点间是否建立链路作为分类问题来解决.2)基于pairwise的链路预测方法[1].该类方法的训练数据是2个节点对,通过对这2个节点对的偏序关系来学习一个链路预测模型,使得学习后得到的偏序关系和真实节点间的偏序关系一致.相对于pointwise的方法,基于pairwise的链路预测考虑了节点对之间的相对关系,因而在实际排序中能取得更高的准确性,目前基于pairwise的链路预测方法得到了广泛关注[1,9].

1.2 社交网络中链路预测的隐私保护算法

现有的隐私保护研究都是针对基于pointwise的链路预测的隐私保护方法,包括基于非加密和基于加密2类.1)基于非加密的隐私保护方法主要是由服务商来保护用户的隐私,服务商利用k-匿名[10]等以组为单位进行链路预测,从而使得攻击者无法通过链路预测结果推测目标用户的敏感链路信息.然而,完全依靠服务商存在极大的安全隐患.2)基于加密的隐私保护方法能一定程度上解决不可信服务商的问题,通过设计加密算法对用户的特征信息进行加密,使得服务商无法获知用户的具体隐私信息[5].但这类方法计算开销较大,而且服务商利用获取的最终真实计算值仍然可以推断出用户的隐私信息(即推断攻击[6]).

由于目前基于pointwise的链路预测的隐私保护机制不能直接应用于基于pointwise的链路预测方法,因此结合现有隐私保护机制的问题和不足,以及用户个性化的需求,针对基于pairwise的链路预测方法,还需要提出新的链路预测隐私保护方法.

2 理论基础

2.1 ε-差分隐私

差分隐私是一种常用的隐私保护方法,具有坚实的理论基础.通过在原始数据集中加入噪声干扰,确保数据集中单个数据的变化不会对最终输出结果产生显著影响,能较好地抵御推断攻击[11].

定义1. ε-差分隐私[11].设有随机算法MRange(M)为所有可能的输出结果构成的集合,对于任意2个最多只有1个元素不同的数据集D1D2以及SRange(M),如果算法M满足

P[M(D1)∈S]≤eε×P[M(D2)∈S],

则称算法M满足ε-差分隐私要求,概率P表示隐私泄露的风险,隐私预算ε用于衡量隐私保护强度.

定理1. Laplace机制[11].对于任意一个函数f:D→RK,若算法M的输出结果满足等式M(D)=f(D)+[Lap1(GS(D)ε),Lap2(GS(D)ε),…,LapK(GS(D)ε)],则算法M满足ε-差分隐私.其中Lapi(GS(D)ε),(1≤iK)是相互独立的Laplace随机数,且对于任意2个最多只有1个元素不同的数据集D1

为了利用Laplace机制实现差分隐私,我们结合Laplace分布的性质,将其分解为服从高斯分布和指数分布的2个随机数的计算值.

定理2. 如果有一个随机数h服从指数分布Exp(1)、一个随机数c服从高斯分布N(0,1),那么对于任意实数b>0,存在服从Laplace分布.

2.2 推断攻击与重构攻击

推断攻击常常用于推测数据集中是否包含目标用户的某条信息[6],而差分隐私可以通过噪声干扰来降低对目标用户的单条信息对最终结果的影响,因而被广泛应用于抵御推断攻击[5,11].

重构攻击则利用公开的信息来重新构建模型,进而推断出用户的隐私信息[7,12].为了抵御重构攻击,Fredrikson 等人[7]证实可以通过极低隐私预算的差分隐私机制来抵御重构攻击,但是极低的隐私预算将严重影响模型的性能.目前还无法在链路预测中抵御重构攻击的同时保障链路预测的准确度.

3 问题描述

社交网络中包含n个用户,这些用户间的关系构成邻接矩阵X∈Rn×n.将用户对(i,j)的关系表示为Xij∈{1,?},1表示已建立有向社交关系(即用户i已关注用户j),?表示用户间目前还未建立社交关系,这里我们可以把?当作0.令用户对建立链路的预

测值为链路预测的目标为:使得Xij=1的用户对的预测值高于Xik=0的用户对的预测值

为了获取更准确的链路预测值除了需要用户间已有的社交关系X,还需要用户间的特征(如用户间的共同朋友数、用户地理位置间距离等),我们将用户i,j间的特征向量定义为fij∈Rd,其中d为用户间特征的数目.由于每个用户对隐私的设置不同,这里我们交由用户来决定信息敏感与否.首先,我们定义Fij=1来表示用户i认为自己对j的关注是敏感关注,否则Fij=0.注意,对Fij=1和Fij=0的(i,j)都存在着Xij=1.在此基础上,令集合Xsen={Xij|∀(i,j) s.t. Fij=1},Xnon={Xij|∀(i,j) s.t. Fij=0}为敏感和非敏感有向链路集合.类似地,Gijl=1表示用户i认为自己与j间的特征l是敏感特征,否则Gijl=0.接着,令Ysen={fijl|∀(i,j,l) s.t. Gijl=1},Ynon={fijl|∀(i,j,l) s.t. Gijl=0}为敏感和非敏感有向链路集合.最终,结合已有的定义,我们将社交网络链路预测的隐私保护目标表示为:在不泄露Xsen,Ysen的前提下,构建来学习预测用户间的社交关系.

4 社交网络链路预测的个性化隐私保护方法

4.1 基本模型

以目前最常用的贝叶斯个性化排序模型(Bayesian personalized ranking, BPR)[13]作为基本模型,来实现基于pairwise的链路预测:

(1)

这里定义三元集oijk={(i,j,k)|Xij=1∧Xik=0},σ(x)=1(1+e-x)为可将任何值归一化到区间(0,1)的函数,ψ是避免过拟合的正则项,λ为控制正则项范围的超参数.

我们将链路预测值定义为这主要是由于:1)现实中社交网络往往是非常稀疏的,所以矩阵分解模型[9]能提高存储效率,即将对的计算拆分为对Ui,Vj的计算,通过隐特征矩阵(latent matrix) U=[Ui]i∈[n]∈RK×n,V=[Vj]j∈[n]∈RK×n,来学习、存储并表达用户i和用户j的潜在的关注与被关注的特征,其中Ui∈RK为用户i的关注隐特征向量(latent vector),Vj∈RK是用户j的被关注隐特征向量,K是矩阵分解中的隐因子(latent factor).2)除了已知的链路关系Xij,用户对(i,j)的特征fij能够提供更多用户信息,所以结合用户对特征向量fij和各特征权重θi∈Rd来进一步辅助预测链路,以得到更准确的链路预测值正则项可表示为ψ=++.

4.2 社交网络链路预测的隐私保护框架

在学习链路预测模型时,服务器需要根据所有已知链路关系Xij和用户对特征向量fij(包括Xsen,Ysen),来学习、计算出其他变量(即U,V,θ).显然,U,V,θ的整个计算过程都集中在服务器端,这将导致服务商能轻易获取用户的敏感隐私信息.

为了解决这个问题,我们考虑去除对服务商的完全依赖,提出一种半集中式的链路预测框架.首先,将用户i的敏感关注集合以及敏感特征集合只存放于用户i本地.同时,由于用户关注特征Ui体现了用户对哪些用户感兴趣、可能会关注哪些用户,能够反映出用户喜好,因而能够泄露用户隐私.因此,我们将Ui的计算和存储仅放在每个用户i本地,而将V的学习计算放在服务器端进行,并由服务器将计算出的V共享给每个用户.用户对的特征向量fij也能够直接反映用户i的敏感信息,所以我们将θi的学习计算也放到每个用户i本地进行.

最终,用户i结合在本地计算出的Ui,θi以及从服务器端接收到的V,就可以在不暴露隐私的前提下得到对任意其他用户的链路预测值但是,由于Xsen,Ysen的缺乏,目前在求取Ui,θi,V最优解的过程中还存在着三大难点:

1) 用户对的特征向量fij不仅能够体现用户i的敏感信息,也能反映用户j的敏感信息,所以用户j并不应该将个人敏感信息分享给用户i,这为计算fij,θi带来难题;

2) 由于关注与被关注的链路关系是成对出现的,服务器端V的计算需要U的参与,而每个Ui仅保存在每个用户i本地,所以难以在不伤害用户隐私的前提下完成V的计算;

3) 每个用户的隐私设置不同,用户对相同的关注或特征的敏感与否的判断不同.

为了解决这些难题,我们将介绍求得变量Ui,V,θi最优解的具体算法.

4.3 面向链路预测的隐私保护方法

首先采用梯度下降[9]的方式来学习求得满足式(1)的最优解,迭代更新Ui,Vj,θi直至收敛,在第t次的迭代公式为

(4)

其中,γ为学习步长(learning rate),目标函数J1关于Ui,Vj,θi的偏导数为

(7)

可以看出,式(2)和式(5)中J1关于Ui的偏导数除了服务器共享的V,只包含与用户i相关的Ui.同理,式(4)和式(7)中J1关于θi的偏导数除了共享的V,只包含与用户jk相关的fij-fik.我们将涉及到用户j的特征计算都基于公开的数据,比如对于(i,j)共同好友数目的计算基于这样,fij,θi的计算和更新完全依赖于用户i,每个用户可以根据喜好选择不同d的特征向量,且不会影响其他用户的计算,解决了4.2节中的第1个难点.

另一方面,式(3)和式(6)中被关注特征矩阵Vj的学习过程中包含多个用户的关注隐特征矩阵Ui,而用户的被关注特征矩阵V的学习是在服务器端进行的,一旦不可信的服务商能够获取Ui,服务商可能通过获取用户i的敏感链路.为了解决这个问题,我们采取基于差分隐私的目标干扰方法(objective perturbation[14]),目标函数J2

(8)

这里我们定义集合oijk,sen={(i,j,k)|Fij=1∧Xik=0},oijk,non={(i,j,k)|Fij=0∧Xik=0},I(·)为指示函数.另外,RK×1是指用于保护敏感链路的噪声干扰,可以避免推断攻击和重构攻击;RK×1表示用于保护非敏感链路的噪声干扰,可以避免推断攻击.通过基于差分隐私的目标干扰方法,我们解决了4.2节中的第2个难点.

此外,我们分别为Pj,Qj赋予不同大小的隐私预算εsenεnon,其中εsen=β εnonβ∈(0,1),并定义ε=β εnon(1+β).对于不同情况的链路,提供不同幅度的噪声干扰,在涉及敏感链路的计算提供较强的隐私保护,且保证不会大幅削弱整体链路预测效果:

1) 对于某条敏感链路XijVj的偏导数即为

2)对于不敏感链路XijVj的偏导数为

3)对于未知链路Xij=0,Vj的偏导数为

为了实现分布式的基于Laplace机制的噪声干扰,我们利用了定理1和定理2来进行噪声选择.首先,服务器端生成服从Exp(1)分布的随机数hj∈RK,并分享给每个用户.接着,对于将(i,j)链路设为敏感的用户i,在本地生成服从的随机数cij∈RK,并计算出εsen;对于没有将(i,j)链路设为敏感的其他用户,也采取类似的步骤,在本地生成服从的随机数cij∈RK,并计算出εnon.最终,我们解决了4.2节中的第3个难点,具体的算法如下:

算法1. 链路预测隐私保护算法(PrivLP).

输入:隐私预算εsenεnon、学习步长γ、链路矩阵X、正则项权重λ、敏感矩阵F、用户对的特征f

输出:U,V,θ.

① 初始化U,V,θ

② for max iterations

③ for j=1,2,…,n

④ for i where Fij=1

⑤ 从用户i获取φ1

⑥ end for

⑦ for i where Fij=0

⑧ 从用户i获取φ2

⑨ end for

⑩ for i where Xij=0

从用户i获取φ3

end for

通过Vj=Vj+γ∂J2Vj更新Vj

end for

for i=1,2,…,n

通过Ui=Ui+γ∂J2Ui更新Ui

通过θi=θi+γ∂J2θi更新θi

end for

end for

在算法1的行④~Vj在服务器端更新,其中,在行④~,每个用户i根据与j的链路情况提交不同的噪声干扰结果,在行,服务商统计来自不同用户的计算结果并更新Vj.行中,每个用户i结合服务商公开的最新V,根据式(5)和式(7)计算、更新Ui,θi.

4.4 隐私保护步骤及理论分析

由于每个用户对链路敏感与否的设置是不同的,且服从Laplace分布的随机数之和并不服从Laplace分布,这为满足差分隐私带来了挑战.

定理3. 如果PjQj中的每1个元素(共K个)都是从εsen)和εnon)独立、随机地抽取的,那么算法PrivLP满足ε-差分隐私.

证明. 令εsen=(1+β)ε,εnon=(1+1β)ε.同时,根据高斯分布特征,显然c服从N(0,1).式(6)涉及到的噪声为

(9)

可以看出服务器端将每个用户的噪声干扰累加后得到Pj,Qj,相当于Pj,Qj是直接从εnon)抽取的随机数.最终,总噪声干扰相当于直接从ε)抽取的随机数.

sj=(sj1,sj2,…,sjl,…,sjK)中每个元素sjl为从ε)抽取的随机数,其概率密度函数为假设D1,D2为只有1个链路不同的数据集,由于需要算法得到收敛后的相同的最优输出解V,我们需要保证假设唯一不同的链路为敏感链路,将Ui表示为ξijk,可以得到:

(10)

由于D1,D2只有1个链路不同,假设这是条敏

感链路,即输出差距体现在那么可知

(11)

由于1可知同理,对于其他链路敏感、非敏感链路或暂未建立链路关系的链路,都存在的情况,即都存在则对于每个被关注隐特征向量Vj,可知

(12)

综上所述,定理3得证.

证毕.

5 实验与结果

为了验证社交网络链路预测的个性化隐私保护算法的链路预测和隐私保护效果,本文选择购物网站Ciao的数据集验证本文提出的PrivLP算法的链路预测和隐私保护效果.Ciao数据集[14]中,一共包括18 998个用户及145 826条有向社交关系,用户-用户链路矩阵的稀疏度为99.96%,适用于基于矩阵分解的方法.我们为每个用户随机抽取了80%的数据加入作为训练集Dtrain,剩余20%加入测试集Dtest,即训练集中,在服务器端学习V、在用户端学习Ui,θi,然后根据学习到的变量计算出用户对间的链路预测值,并在测试集中检验链路预测及隐私保护效果.在这个过程中,用户敏感特征Ysen不需要参与服务器端V的计算,仅参与用户本地的θi的计算.另外,由于每个用户的个性化隐私设置数据难以获取,而对于某些用户的关注更可能被设置敏感链路,所以我们随机抽取用户,对这些用户的被关注链路(即这些用户在链路中是被关注用户)中80%为敏感链路,不断抽取用户直至训练集Dtrain和测试集Dtest中敏感链路的比例为x%,这里x∈{10,30,50}.

我们采取了曲线下面积[13](area under curve, AUC)来衡量链路预测和隐私保护效果,并将基于AUC的衡量指标LAUC定义为

(13)

其中,E(i)={(j,k)|(i,j)∈Dtest∧(i,k)∉(DtestDtrain)}.对链路预测而言,较高的LAUC意味较好的链路预测效果;对隐私保护而言,较低的LAUC表示提供了较高的隐私保护.

我们选择了目前最具代表性的链路预测隐私保护方法PPLR[4]以及基本模型BPR[13]作为对比.为了简化实验过程,为每个用户统一选择了3个特征用于PrivLP:用户i的好友个数、用户j的好友个数、用户ij的共同好友个数.ε=0.1,β=0.1.

5.1 链路预测效果对比

由于BPR没有提供隐私保护,所以我们没有将Dtrain中的Xsen加入链路预测的训练中.

随着敏感链路比例的变化,与PPLR及BPR的实验对比结果如图1所示.由于我们是基于BPR的模型,所以在敏感链路较少时噪声干扰导致我们链路预测效果明显低于BPR,这说明噪声干扰和隐私保护确实存在着博弈关系.而随着敏感链路的增加,由于隐私保护机制激励用户将更多的敏感链路加入链路预测的过程,所以链路预测效果反而超过了没有噪声干扰的BPR.总的来说,随着敏感链路数目的增长,虽然我们为每个用户都添加了较大的噪声,我们仍然能够维持较高的链路预测准确度.

Fig. 1 Link prediction comparison on LAUC with different percentages of sensitive links
图1 随着隐私链路数目变化的链路预测LAUC比较

Fig. 2 Privacy protection comparison on LAUC with different percentages of sensitive links
图2 随着隐私链路数目变化的隐私保护LAUC比较

5.2 隐私保护效果对比

链路预测的过程中,由于用户i的敏感特征Yisen仅需要在本地参与θi的计算,而不会泄露给服务商或其他用户,所以仅需要考虑对敏感链路的隐私保护效果.由于BPR没有提供隐私保护,所以服务器端能够直接得到Dtrain中的所有数据,并可以根据训练出的变量值预测Dtest中的敏感链路.对于PPLR,所有的参数都存在于每个用户本地,所以仅利用Dtrain中的Xnon,Ynon进行训练,并将学习出的变量用于预测Dtest中的敏感链路.最后,对于PrivLP,由于每个用户的特征选择数目和种类都各不相同,所以攻击者对模型的重构不考虑fij,θi,通过利用共享的V以及训练集中的非敏感数据Xnon重新训练模型

得到近似值并最终结合V和近似值计算来预估Dtest中的敏感链路[14].

从图2可以看出,PrivLP的隐私保护效果始终处于领先地位.同时,结合图1和图2的结果,我们可以得出结论:我们的方法能够在维持较高链路预测效果的同时有效保护用户隐私.

5.3 参数ε的影响

为了衡量PrivLP随参数ε的变化,我们将x固定为10,β固定为0.01.观察随着ε={0.001,0.05,0.01,0.1,0.5,1,10}的变化对PrivLP效果的影响.从理论来说,隐私预算ε越低,数据干扰强度越高,隐私保护效果越好.从图3可见,随着ε的增长,链路预测和隐私保护的LAUC值处于增长趋势,实验验证了ε的增长能提高链路预测效果,降低隐私保护效果.

Fig. 3 The impact of ε
图3 ε的影响

5.4 参数β的影响

为了衡量PrivLP随参数ε的变化,我们将x固定为10,ε固定为0.01.由于β∈(0,1),所以我们观察随着β={0.001,0.05,0.01,0.1,0.5,1}的变化对PrivLP效果的影响.从理论来说,敏感预算与非敏感预算的比例β越高,对于敏感链路数据干扰强度越高,隐私保护效果越好.从图4可见,随着β的增长,链路预测和隐私保护的LAUC值都处于下降趋势,实验验证了β的增长将降低链路预测效果,提高隐私保护效果.

Fig. 4 The impact of β
图4 β的影响

6 总 结

为了打消用户隐私泄露的顾虑,我们提出了一种社交网络链路预测的个性化隐私保护方法.摆脱对服务商的完全依赖,让用户和服务商共同合作来完成链路预测;并为敏感信息和非敏感信息添加不同强度的噪声干扰,保护敏感链路不被泄露的同时维持较好的链路预测效果;根据用户个性化的隐私设置,为用户提供个性化的隐私保护.最后,理论证明了提出的方法满足ε-差分隐私,并在真实数据集上验证了隐私保护和链路预测准确性之间的有效平衡.下一步工作将研究如何在动态的链路预测中实现隐私保护.

参考文献

[1]Song Dongjin, Meyer D. Recommending positive links in signed social networks by optimizing a generalized AUC[C] //Proc of the 29th AAAI Conf on Artificial Intelligence. Menlo Park: AAAI, 2015: 290-296

[2]Tiroshi A, Berkovsky S, Kaafar M, et al. Improving business rating predictions using graph based features[C] //Proc of the 19th Int Conf on Intelligent User Interfaces. New York: ACM, 2014: 17-26

[3]Machanavajjhala A, Korolova A, Sarma A. Personalized social recommendations: Accurate or private[J]. Proceedings of the VLDB Endowment, 2011, 4(7): 440-450

[4]Zheng Yao, Wang Bing, Lou Wenjing, et al. Privacy-preserving link prediction in decentralized online social networks[C] //Proc of the 20th European Symp on Research in Computer Security. Berlin: Springer, 2015: 61-80

[5]Tang Qiang, Wang Jun. Privacy-preserving friendship-based recommender systems[J]. IEEE Transactions on Dependable and Secure Computing, 2015, 15(5): 784-796

[6]Shokri R, Stronati M, Song Congzheng, et al. Membership inference attacks against machine learning models[C] //Proc of IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2017: 3-18

[7]Fredrikson M, Lantz E, Jha S, et al. Privacy in pharmacogenetics: An end-to-end case study of personalized warfarin dosing[C] //Proc of the 23rd USENIX Security Symp. Berkeley, CA: USENIX Association, 2014: 17-32

[8]Hu Yifan, Koren Y, Volinsky C. Collaborative filtering for implicit feedback datasets[C] //Proc of the 8th Int Conf on Data Mining. Piscataway, NJ: IEEE, 2008: 263-272

[9]Menon A, Elkan C. Link prediction via matrix factorization[C] //Proc of the European Conf on Machine Learning and Principles and Practice of Knowledge Discovery. Berlin: Springer, 2011: 437-452

[10]Zhang Xiaojiao, Wang Miao, Meng Xiaofeng. An accurate method for mining top-k frequent pattern under differential privacy[J]. Journal of Computer Research and Development, 2014, 51(1): 104-114 (in Chinese)(张啸剑, 王淼, 孟小峰. 差分隐私保护下一种精确挖掘top-k频繁模式方法[J]. 计算机研究与发展, 2014, 51(1): 104-114)

[11]Dwork C, McSherry F, Nissim K, et al. Calibrating noise to sensitivity in private data analysis[C] //Proc of the Theory of Cryptography Conf. Berlin: Springer, 2006: 265-284

[12]Kasiviswanathan S P, Rudelson M, Smith A, et al. The price of privately releasing contingency tables and the spectra of random matrices with correlated rows[C] //Proc of the 42nd Symp on Theory of Computing. New York: ACM, 2010: 775-784

[13]Rendle S, Freudenthaler C, Gantner Z, et al. BPR: Bayesian personalized ranking from implicit feedback[C] //Proc of the 25th Conf on Uncertainty in Artificial Intelligence. New York: AUAI, 2009: 452-461

[14]Meng Xuying, Wang Suhang, Shu Kai, et al. Personalized privacy-preserving social recommendation[C] //Proc of the 32nd Conf on Artificial Intelligence. Menlo Park: AAAI, 2018: 3796-3803

Personalized Privacy Preserving Link Prediction in Social Networks

Meng Xuying1,2, Zhang Qijia1,2, Zhang Hanwen1,2, Zhang Yujun1,2, and Zhao Qinglin3

1 (Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190)2 (University of Chinese Academy of Sciences, Beijing 100049)3 (Macau University of Science and Technology, Macau 519020)

Abstract Link prediction is widely used to predict and recommend social relationships in social networks. However, it requires users’ personal information, leading to great risks to users’ privacy. To prevent privacy leakage, users may refuse to provide needed information to the service provider, which in turn brings in decreases on the effectiveness of link prediction, and further hurts user experience. To eliminate the concerns of privacy disclosure and encourage users to provide more data for link prediction, we propose personalized privacy preserving link prediction in social network. We get rid of the full dependence on the service provider and friends by making users and the service provider cooperate to complete the process of link prediction. Also, we attach different magnitude noise with personalized privacy settings, maintaining the effectiveness of link prediction while protecting sensitive links and sensitive attributes. Finally, theoretical analysis is provided based on differential privacy, and experimental results on real world datasets show that our proposed methods can provide better privacy protection while maintaining the effectiveness of link prediction.

Key words link prediction; social network; privacy protection; personalized; differential privacy

(mengxuying@ict.ac.cn)

DOI:10.7544/issn1000-1239.2019.20180306

收稿日期2018-04-21;修回日期:2018-12-19

基金项目国家自然科学基金项目(61672500,61572474,61872452,61872451);国家国际科技合作专项项目(2016YFE0121500);FDCT-MOST项目(001/2015/AMJ)

This work was supported by the National Natural Science Foundation of China (61672500, 61572474, 61872452, 61872451), the International S&T Cooperation Program of China (2016YFE0121500), and the FDCT-MOST Projects (001/2015/AMJ).

通信作者张玉军(zhmj@ict.ac.cn)

中图法分类号 TP391

Meng Xuying, born in 1992. PhD. Her main research interests include privacy protection and machine learning.

Zhang Qijia, born in 1993. MSc. Her main research interests include privacy protection and data mining.

Zhang Hanwen, born in 1981. PhD, associate professor. Her main research interests include next generation networks, wireless networks and machine learning.

Zhang Yujun, born in 1977. PhD, professor. His main research interests include next generation networks, wireless networks and machine learning.

Zhao Qinglin, born in 1974. PhD, professor. His main research interests include wireless communications and networking, next generation wireless local area networks, software-defined wireless networks, and physical-layermedium access control co-design.