基于動態(tài)ε的社會網(wǎng)絡差分隱私保護

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

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

0 引言

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

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

在實際應用中，一個數(shù)據(jù)集中同時存在著重要和次要的數(shù)據(jù)，使用一個隱私預算ε會導致數(shù)據(jù)的隱私保護不均衡，數(shù)據(jù)的效用性會受到一定的限制．本文的主要貢獻為：

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

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

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

1 基本概念

1.1 MCL&Chameleon混合聚類

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

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

2) 重復1)過程，直到算法收斂為止；

3) 把每一行的非0值所對應的列節(jié)點歸為一簇，得到聚類結(jié)果V；

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

5) 找出最大相似度值，若超過設定的閾值將對應的兩個簇合并，否則說明兩個簇無法合并，放到結(jié)果簇集合中；

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

1.2 差分隱私

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

定義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′只有一個元素不同．設兩個社會網(wǎng)絡數(shù)據(jù)集G1和G2所有的節(jié)點相同，只有一條邊不同，即全局敏感度設為最大差異權(quán)重Δq=Wmax．

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

(1)

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

在社交網(wǎng)絡圖中，邊的權(quán)重越大，表明兩節(jié)點之間的關(guān)系越親密，兩節(jié)點之間的隱私越為重要，則需要更強的保護．差分隱私添加噪聲的大小跟ε成反比，簇中節(jié)點間的邊權(quán)重越大，應該分配的ε值就越小．由于全局的ε值不統(tǒng)一，本文使用組合差分隱私策略．

定義3組合差分隱私．已知數(shù)據(jù)集D={clu1，clu2，…，clucluster}，D′={clu′1，clu′2，…，clu′cluster}，給定隱私算法M，D和D′中都包含有cluster個簇，相對應的簇clui和clu′i只相差一條記錄邊，每個簇的ε值不同．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對應的隱私預算，Lap(Δqi/εi)(1≤i≤cluster)是為clui生成的Laplace噪聲向量．

2 動態(tài)ε社會網(wǎng)絡差分隱私保護方法

2.1 基本思想

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

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

在不同的應用場景，對ε函數(shù)f(x)所需要的表達式可能會不同，在實際應用場景中f(x)也是因情況而定．本文只是使用一個例子驗證動態(tài)ε的可行性．

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

2.3 算法流程

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

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

輸出：隱私保護后的社會網(wǎng)絡圖G*．

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

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

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

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

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

6) 為每個簇構(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)絡圖G*={S-1，S1，S2，…，SnewCluster}．

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

2.4 算法的隱私性分析

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

設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滿足ε-差分隱私．

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

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

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

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

3 實驗結(jié)果及分析

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

實驗所使用的環(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家庭版，編程語言是C++．

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

表1 實驗數(shù)據(jù)Tab.1 Experimental data

3.2 實驗結(jié)果

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

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

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

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

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

圖3 實驗對比結(jié)果Fig.3 Experimental comparison result

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

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

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

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

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

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

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

4 結(jié)論

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