劉振鵬， 王 爍， 張 彬， 孫靜薇

(1. 河北大學(xué) 網(wǎng)絡(luò)空間安全與計(jì)算機(jī)學(xué)院 河北 保定 071002； 2. 河北大學(xué) 信息技術(shù)中心 河北 保定 071002； 3. 河北大學(xué) 電子信息工程學(xué)院 河北 保定 071002)

0 引言

隱私保護(hù)中的主要問(wèn)題是如何對(duì)數(shù)據(jù)進(jìn)行適度的保護(hù)，同時(shí)又能獲得最大的數(shù)據(jù)效用性，以滿足科學(xué)研究和數(shù)據(jù)共享的需求．已有的社會(huì)網(wǎng)絡(luò)隱私保護(hù)方法分為兩大類[1-2]：一種是基于聚類的匿名保護(hù)方法，用聚類算法把圖劃分成若干個(gè)子圖，把各個(gè)子圖匿名為一個(gè)超級(jí)節(jié)點(diǎn)，該類方法把子圖內(nèi)部的所有信息隱藏起來(lái)，造成的數(shù)據(jù)缺損過(guò)大，不利于數(shù)據(jù)的共享和研究；另一種是對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行改動(dòng)，通過(guò)對(duì)邊的添加、刪除和修改操作，使發(fā)布后的圖在結(jié)構(gòu)上和原始圖存在一些差異，這類方法數(shù)據(jù)缺損比較小，數(shù)據(jù)的效用性較高．上述兩大類方法都是在攻擊者對(duì)背景知識(shí)掌握受限的基礎(chǔ)上，實(shí)現(xiàn)對(duì)數(shù)據(jù)的弱保護(hù)．差分隱私保護(hù)技術(shù)[3]假定攻擊者已掌握所有背景知識(shí)的前提下，用數(shù)學(xué)方法進(jìn)行嚴(yán)格定義，是一種基于數(shù)據(jù)失真的強(qiáng)保護(hù)模型．

在社會(huì)網(wǎng)絡(luò)隱私保護(hù)領(lǐng)域中，Liu等[4]把節(jié)點(diǎn)的度作為攻擊者的背景知識(shí)，采用貪心算法構(gòu)建k-鄰域匿名結(jié)構(gòu)防止攻擊． Cheng等[5]提出了k-同構(gòu)隱私保護(hù)模型．Zou等[6]提出k-自同構(gòu)的匿名方法.Wang等[7]把帶權(quán)網(wǎng)絡(luò)圖的最短路徑作為隱私保護(hù)的重點(diǎn)，設(shè)計(jì)了一種k-路徑匿名保護(hù)模型，對(duì)最短路徑的隱私進(jìn)行保護(hù)．蘭麗輝等[8]提出了一種基于差分隱私模型的隨機(jī)擾動(dòng)方法，設(shè)計(jì)了LWSPA(less weighted social privacy algorithm)算法，對(duì)查詢結(jié)果集中的三元組進(jìn)行劃分，實(shí)現(xiàn)基于邊權(quán)重的隱私保護(hù)．張偉等[9]提出一種基于層次的隨機(jī)圖，并且滿足ε-差分隱私的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)發(fā)布算法(differential privacy-hierarchical random graph publishing,DP-HRGP)，利用馬爾可夫蒙特卡洛方法得到HRG結(jié)構(gòu)樹候選集合，對(duì)集合中的內(nèi)部節(jié)點(diǎn)加噪，生成滿足ε-差分隱私的社會(huì)網(wǎng)絡(luò)發(fā)布圖．劉曉遷等[10]對(duì)數(shù)據(jù)進(jìn)行聚類劃分，實(shí)現(xiàn)將同一簇中的個(gè)體記錄匿名化隱藏，以實(shí)現(xiàn)聚類匿名化差分隱私．Qian等[11]提出了一種方案，即保護(hù)私有信息的統(tǒng)計(jì)分析(privacy preserving statistical analysis,PPSA)，把同態(tài)加密和差分隱私機(jī)制結(jié)合起來(lái)對(duì)用戶的敏感數(shù)據(jù)加密，保證用戶的敏感信息不被發(fā)現(xiàn)．以上技術(shù)都是為所有數(shù)據(jù)分配一個(gè)隱私預(yù)算ε，這就導(dǎo)致所有數(shù)據(jù)的保護(hù)程度是相同的．

在實(shí)際應(yīng)用中，一個(gè)數(shù)據(jù)集中同時(shí)存在著重要和次要的數(shù)據(jù)，使用一個(gè)隱私預(yù)算ε會(huì)導(dǎo)致數(shù)據(jù)的隱私保護(hù)不均衡，數(shù)據(jù)的效用性會(huì)受到一定的限制．本文的主要貢獻(xiàn)為：

1) 針對(duì)權(quán)重社會(huì)網(wǎng)絡(luò)中隱私保護(hù)不均衡的問(wèn)題，設(shè)計(jì)了一種使用ε函數(shù)為社會(huì)網(wǎng)絡(luò)中的邊動(dòng)態(tài)分配隱私預(yù)算ε的差分隱私保護(hù)方法．

2) 使用MCL和Chameleon混合聚類對(duì)社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊進(jìn)行劃分，根據(jù)簇中邊的權(quán)重信息，為每個(gè)簇分配合適的ε值．

3) 使用真實(shí)的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果驗(yàn)證本文的方法有效解決了數(shù)據(jù)隱私保護(hù)不均衡的問(wèn)題，并且滿足用戶在社會(huì)網(wǎng)絡(luò)中的數(shù)據(jù)共享需求．

1 基本概念

1.1 MCL&Chameleon混合聚類

馬爾科夫聚類算法(MCL)[12]是由Dongen提出的一種經(jīng)典的網(wǎng)絡(luò)圖形聚類算法．Chameleon算法是一種層次聚類算法[13]，算法為兩個(gè)階段：第一階段為k-近鄰聚類；第二階段對(duì)聚類結(jié)果合并優(yōu)化．MCL聚類的結(jié)果非常零散，大多數(shù)的簇只有一個(gè)或幾個(gè)節(jié)點(diǎn)，不能有效地把關(guān)系近的節(jié)點(diǎn)和大權(quán)重的邊聚到一塊．采用Chameleon算法的第二階段對(duì)MCL聚類的結(jié)果進(jìn)行合并優(yōu)化．下面簡(jiǎn)單介紹MCL&Chameleon混合聚類．

1) 使用MCL算法對(duì)網(wǎng)絡(luò)圖的鄰接矩陣進(jìn)行l(wèi)次冪擴(kuò)展和r次方膨脹操作；

2) 重復(fù)1)過(guò)程，直到算法收斂為止；

3) 把每一行的非0值所對(duì)應(yīng)的列節(jié)點(diǎn)歸為一簇，得到聚類結(jié)果V；

4) 根據(jù)簇間的相互對(duì)連度RI和相對(duì)近似度RC計(jì)算兩兩簇之間的相似度sim；

5) 找出最大相似度值，若超過(guò)設(shè)定的閾值將對(duì)應(yīng)的兩個(gè)簇合并，否則說(shuō)明兩個(gè)簇?zé)o法合并，放到結(jié)果簇集合中；

6) 重復(fù)4)和5)過(guò)程，直到待合并簇集合為空，得到新的聚類結(jié)果V*．

1.2 差分隱私

差分隱私保護(hù)技術(shù)假定攻擊者已經(jīng)掌握所有關(guān)于數(shù)據(jù)的背景知識(shí)，并在數(shù)學(xué)的基礎(chǔ)上定義了嚴(yán)格的保護(hù)模型．目的是在對(duì)數(shù)據(jù)查詢時(shí)，既能最大限度地提高查詢的準(zhǔn)確性，又能最大限度地減少識(shí)別數(shù)據(jù)記錄的機(jī)會(huì)．差分隱私保護(hù)的基本思想是對(duì)查詢結(jié)果添加服從拉普拉斯分布的噪聲，使數(shù)據(jù)失真，達(dá)到隱私保護(hù)的目的．

定義1ε-差分隱私．已知數(shù)據(jù)集D和D′，給定隱私算法M，D和D′只有一條記錄不相同，range(M)表示M的定義域，若M在D和D′上的任意輸出結(jié)果S(S∈range(M))滿足不等式Pr[M(D)∈S]≤eεPr[M(D′)∈S]，則M滿足ε-差分隱私．

數(shù)據(jù)集D和D′只有一個(gè)元素不同．設(shè)兩個(gè)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集G1和G2所有的節(jié)點(diǎn)相同，只有一條邊不同，即全局敏感度設(shè)為最大差異權(quán)重Δq=Wmax．

使用拉普拉斯分布[14]為數(shù)據(jù)添加噪聲，

(1)

其中：〈Lap(Δq/ε)〉d是服從Δq/ε尺度參數(shù)的Laplace分布的噪聲向量．Laplace機(jī)制是對(duì)于任何函數(shù)Q:D→Rd，如果算法M的輸出結(jié)果滿足式(1)，表明M滿足ε-差分隱私．

在社交網(wǎng)絡(luò)圖中，邊的權(quán)重越大，表明兩節(jié)點(diǎn)之間的關(guān)系越親密，兩節(jié)點(diǎn)之間的隱私越為重要，則需要更強(qiáng)的保護(hù)．差分隱私添加噪聲的大小跟ε成反比，簇中節(jié)點(diǎn)間的邊權(quán)重越大，應(yīng)該分配的ε值就越?。捎谌值摩胖挡唤y(tǒng)一，本文使用組合差分隱私策略．

定義3組合差分隱私．已知數(shù)據(jù)集D={clu1，clu2，…，clucluster}，D′={clu′1，clu′2，…，clu′cluster}，給定隱私算法M，D和D′中都包含有cluster個(gè)簇，相對(duì)應(yīng)的簇clui和clu′i只相差一條記錄邊，每個(gè)簇的ε值不同．range(M)表示M的定義域，若M在clui和clu′i上的任意輸出結(jié)果Si(Si∈range(M))滿足不等式Pr[M(clui)∈Si]≤eεiPr[M(clu′i)∈Si]，則M滿足組合差分隱私，

(2)

其中：εi是簇clui對(duì)應(yīng)的隱私預(yù)算，Lap(Δqi/εi)(1≤i≤cluster)是為clui生成的Laplace噪聲向量．

2 動(dòng)態(tài)ε社會(huì)網(wǎng)絡(luò)差分隱私保護(hù)方法

2.1 基本思想

針對(duì)社會(huì)網(wǎng)絡(luò)發(fā)布算法中使用全局統(tǒng)一的ε值而導(dǎo)致隱私保護(hù)不均衡的問(wèn)題，提出一種動(dòng)態(tài)ε社會(huì)網(wǎng)絡(luò)差分隱私保護(hù)方法．使用MCL和Chameleon混合聚類把社會(huì)網(wǎng)絡(luò)圖劃分成若干個(gè)簇，根據(jù)每個(gè)簇中邊的權(quán)重信息，使用ε函數(shù)f(x)來(lái)確定每個(gè)簇的ε值，對(duì)帶有大權(quán)重邊的簇分配較小的ε值，添加較多的Laplace噪聲，提高隱私保護(hù)的程度，該方法滿足ε-差分隱私模型．

2.2 ε函數(shù)f(x)

在不同的應(yīng)用場(chǎng)景，對(duì)ε函數(shù)f(x)所需要的表達(dá)式可能會(huì)不同，在實(shí)際應(yīng)用場(chǎng)景中f(x)也是因情況而定．本文只是使用一個(gè)例子驗(yàn)證動(dòng)態(tài)ε的可行性．

為了給簇分配合適的ε值，在選取函數(shù)f(x)上要從多方面考慮．大權(quán)重的邊需要強(qiáng)保護(hù)，則簇中最大權(quán)重的邊作為一個(gè)因子；均值反映數(shù)據(jù)的集中趨勢(shì)，需要分析簇中邊權(quán)重的平均值；標(biāo)準(zhǔn)差是評(píng)價(jià)數(shù)據(jù)的離散程度，標(biāo)準(zhǔn)差越小，表明數(shù)據(jù)越均勻，數(shù)據(jù)會(huì)集中在均值附近．本文實(shí)驗(yàn)使用的函數(shù)f(x)實(shí)例是

2.3 算法流程

動(dòng)態(tài)ε社會(huì)網(wǎng)絡(luò)差分隱私保護(hù)方法的基本流程如下．

輸入：原始社會(huì)網(wǎng)絡(luò)圖G．

輸出：隱私保護(hù)后的社會(huì)網(wǎng)絡(luò)圖G*．

1) 使用1.1節(jié)介紹的MCL & Chameleon混合聚類對(duì)圖G聚類，得到聚類結(jié)果V*和聚類個(gè)數(shù)newCluster，以及每個(gè)簇節(jié)點(diǎn)的個(gè)數(shù)m1，m2，…，mnewCluster．

2) 把V*中每個(gè)簇的節(jié)點(diǎn)和邊的信息構(gòu)成三元組(i，j，k)，把所有簇間的邊的三元組單獨(dú)記錄下來(lái)，i、j是節(jié)點(diǎn)編號(hào)，k代表權(quán)重，當(dāng)節(jié)點(diǎn)之間無(wú)連接時(shí)，k設(shè)置為0．

3) 根據(jù)每個(gè)簇的三元組生成邊向量X-1，X1，…，XnewCluster．其中簇的邊向量表示為Xi={x1，x2，…，xmi·(mi-1)/2}，i=1，2，…，newCluster．X-1是所有簇間的邊組成的向量．

4) 根據(jù)每個(gè)簇的邊向量Xi，使用ε函數(shù)f(x)得到ε={ε-1，ε1，ε2，…，εnewCluster}，其中ε-1表示X-1向量的ε值．

5) 根據(jù)每個(gè)簇的ε值，生成滿足ε-差分隱私的拉普拉斯噪聲，Lap=Lap(Δqi/εi)．

6) 為每個(gè)簇構(gòu)造服從Laplace分布的向量組〈Lap(Δqi/εi)〉Xi，其中i=-1，1，…，newCluster．

7) 生成滿足ε-差分隱私的簇向量組Si=Xi+〈Lap(Δqi/εi)〉Xi，其中i=-1，1，…，newCluster．

8) 生成滿足ε-差分隱私的網(wǎng)絡(luò)圖G*={S-1，S1，S2，…，SnewCluster}．

9) 輸出隱私保護(hù)后網(wǎng)絡(luò)圖G*．

2.4 算法的隱私性分析

由于每個(gè)簇使用的隱私預(yù)算ε不同，無(wú)法直接對(duì)全局的隱私性進(jìn)行分析．在此通過(guò)組合差分隱私進(jìn)行間接分析，當(dāng)所有的簇都滿足ε-差分隱私，全局也會(huì)滿足ε-差分隱私．根據(jù)定義3中組合差分隱私需要滿足的不等式Pr[M(clui)∈Si]≤eεiPr[M(clu′i)∈Si]來(lái)分析算法的隱私性．

設(shè)clui和clu′i只相差一條邊，隱私算法為M，range(M)表示M的定義域，若M在clui和clu′i上的任意輸出結(jié)果Si(Si∈range(M))滿足不等式Pr[M(clui)∈Si]≤eεiPr[M(clu′i)∈Si]，則本文隱私算法M滿足ε-差分隱私．

證明設(shè)s∈Si，Si與Xi維度相同，由條件概率可知

其中：σ是服從Laplace分布的尺度參數(shù)，σ=Δqi/εi.由定義2可知，Δqi=Wmax．得

由Xi(clui)-Xi(clu′i)≤Wmax知

因?yàn)閟∈Si，所以Pr[M(clui)∈Si]/Pr[M(clu′i)∈Si]≤eεi，算法滿足組合差分隱私，即算法也滿足ε-差分隱私．

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)

實(shí)驗(yàn)所使用的環(huán)境是：Intel? CoreTMi5-7300HQ CPU @2.50 GHz、8 GB內(nèi)存、NVIDIA GeForce GTX 1060 with Max-Q Design，操作系統(tǒng)是Windows 10家庭版，編程語(yǔ)言是C++．

實(shí)驗(yàn)數(shù)據(jù)如表1所示．Lesmis是帶權(quán)重社會(huì)網(wǎng)絡(luò)圖，用于驗(yàn)證實(shí)驗(yàn)數(shù)據(jù)的效用性．隨機(jī)1、隨機(jī)2、隨機(jī)3是隨機(jī)生成的數(shù)據(jù)集，用于測(cè)試算法的執(zhí)行時(shí)間．

表1 實(shí)驗(yàn)數(shù)據(jù)Tab.1 Experimental data

3.2 實(shí)驗(yàn)結(jié)果

3.2.1數(shù)據(jù)效用性分析 實(shí)驗(yàn)測(cè)試了本文算法的不同簇的數(shù)據(jù)效用性，驗(yàn)證不同ε值對(duì)數(shù)據(jù)效用性的影響．實(shí)驗(yàn)從每個(gè)簇的隱私前后權(quán)重分布情況以及平均最短路徑和平均聚類系數(shù)測(cè)試不同簇的數(shù)據(jù)效用性．對(duì)實(shí)驗(yàn)中的5個(gè)簇進(jìn)行數(shù)據(jù)分析．平均聚類系數(shù)如圖1(a)所示，平均最短路徑如圖1(b)所示，分析了隱私后5個(gè)簇的平均聚類系數(shù)和平均最短路徑，與原始圖的值進(jìn)行對(duì)比，簇的隱私預(yù)算ε越小，平均聚類系數(shù)與原始值偏差越大，隱私保護(hù)程度越高，簇的數(shù)據(jù)效用性越低；簇的隱私預(yù)算ε越大，平均最短路徑與原始值越接近，簇的數(shù)據(jù)效用性越高．

圖1 數(shù)據(jù)的效用性Fig.1 Data utility

圖2給出這5個(gè)簇的邊權(quán)重在隱私前后的變化．由圖2的(a)～(e)可知，ε值越小，邊在隱私前后的權(quán)重相差越大，隱私保護(hù)的程度越高；ε值越大，邊在隱私前后的權(quán)重相差越小，數(shù)據(jù)的效用性越高．ε值越小的簇，簇中大權(quán)重的邊所占比例越高．

圖2 隱私前后權(quán)重分布Fig.2 Weight distribution before and after privacy

3.2.2實(shí)驗(yàn)對(duì)比 實(shí)驗(yàn)使用LDRC(less divide randomize and conquer)算法[16]和LWSPA算法[8]與本文的動(dòng)態(tài)ε算法在Lesmis數(shù)據(jù)集上進(jìn)行比較，使用圖2中的(a)～(e)5個(gè)簇與LDRC算法和LWSPA算法在ε等于0.05、0.1、1、10時(shí)對(duì)比，平均最短路徑如圖3(a)所示，平均聚類系數(shù)如圖3(b)所示．

圖3 實(shí)驗(yàn)對(duì)比結(jié)果Fig.3 Experimental comparison result

經(jīng)過(guò)兩種算法與本文算法中選取的5個(gè)簇在ε等于0.05、0.1、1、10時(shí)的平均聚類系數(shù)和平均最短路徑對(duì)比可知，隨著ε值變大，兩種算法的平均聚類系數(shù)和平均最短路徑越來(lái)越接近數(shù)據(jù)的原始值，數(shù)據(jù)的效用性越高；本文算法中選取的5個(gè)簇也有著相似的特性，簇的ε值越大，平均聚類系數(shù)和平均最短路徑越接近數(shù)據(jù)的原始值，數(shù)據(jù)的效用性越高．但LDRC算法和LWSPA算法只能做到全局，而本文算法可以使大權(quán)重的邊得到更強(qiáng)的保護(hù)，同時(shí)小權(quán)重的邊可以提高其數(shù)據(jù)的效用性，因此本文算法與LDRC算法和LWSPA算法相比，有著明顯的優(yōu)越性．

3.2.3執(zhí)行時(shí)間分析 實(shí)驗(yàn)分別測(cè)試了MCL聚類在CPU和GPU下的執(zhí)行時(shí)間并計(jì)算出加速比．執(zhí)行時(shí)間如圖4(a)所示，加速比如圖4(b)所示．

圖4 MCL算法效率Fig.4 MCL algorithm efficiency

通過(guò)實(shí)驗(yàn)數(shù)據(jù)可以看出，隨著實(shí)驗(yàn)數(shù)據(jù)的增加，CPU計(jì)算所需的時(shí)間急劇增加，GPU的加速比也隨著數(shù)據(jù)量的增加而增加．使用GPU對(duì)MCL聚類算法加速非常有必要．

3.2.4Chameleon算法優(yōu)化分析 實(shí)驗(yàn)驗(yàn)證了使用Chameleon算法第二階段對(duì)MCL聚類優(yōu)化的效果，簇的數(shù)量變化如圖5(a)所示，聚到簇中的邊的數(shù)量和權(quán)重的變化如圖5(b)所示．

圖5 聚類優(yōu)化前后對(duì)比Fig.5 Comparison before and after cluster optimization

由圖5可以看出，在優(yōu)化前，簇的數(shù)量很多，并且聚到簇中的邊很少，大權(quán)重的邊更少．簇的個(gè)數(shù)過(guò)多且非常零散，會(huì)導(dǎo)致實(shí)驗(yàn)的效果比較差．通過(guò)Chameleon算法的第二階段優(yōu)化，簇的個(gè)數(shù)減少很多，聚到簇中的邊比優(yōu)化前的數(shù)量提高近10倍，并且更多大權(quán)重的邊聚到簇中，使動(dòng)態(tài)ε隱私保護(hù)方法可以達(dá)到預(yù)期的效果．

4 結(jié)論

針對(duì)社會(huì)網(wǎng)絡(luò)差分隱私保護(hù)對(duì)數(shù)據(jù)保護(hù)不均衡問(wèn)題，在ε-差分隱私模型的基礎(chǔ)上，提出一種動(dòng)態(tài)ε-差分隱私保護(hù)方法．使用MCL和Chameleon混合聚類把網(wǎng)絡(luò)劃分成若干個(gè)簇，根據(jù)每個(gè)簇中邊的權(quán)重信息，使用ε函數(shù)f(x)為每個(gè)簇分配合適的隱私預(yù)算，簇添加服從拉普拉斯分布的噪聲，有效解決了數(shù)據(jù)隱私保護(hù)的不均衡問(wèn)題．使用GPU對(duì)MCL算法加速，提高了運(yùn)行效率，滿足當(dāng)前大數(shù)據(jù)時(shí)代對(duì)運(yùn)算速度的要求．