袁 泉，晏飛揚，文志云，張振康

(1.重慶郵電大學通信與信息工程學院,重慶 400065；2.重慶郵電大學通信新技術(shù)應用研究中心，重慶 400065；3.重慶信科設計有限公司，重慶 401121)

1 引言

在大數(shù)據(jù)時代的各種社交網(wǎng)絡應用所產(chǎn)生的網(wǎng)絡數(shù)據(jù)中，蘊含著大量用戶的隱私數(shù)據(jù)，如果不對這些數(shù)據(jù)加以保護，用戶的隱私信息將極易被竊取，造成難以估量的損失。如2018年發(fā)生的Facebook“泄密門”事件，導致5 000多萬用戶的個人信息被數(shù)據(jù)分析公司用于分析和干預選民的投票意向。該事件被曝光后，掀起巨大的輿論風波，同時也再一次凸顯出個人的數(shù)據(jù)隱私保護面臨著巨大的挑戰(zhàn)[1]。

在保護隱私數(shù)據(jù)的方法中，差分隱私保護方法[2]通過一種嚴格的數(shù)學模型，可有效防止攻擊者在擁有背景知識的前提下對數(shù)據(jù)進行差分攻擊。但是，傳統(tǒng)的權(quán)重社交網(wǎng)絡差分隱私保護方法還存在以下問題：

(1)直接對邊權(quán)重添加噪聲擾動，會導致添加的噪聲量過大，從而使得數(shù)據(jù)可用性急劇下降，該舉措雖然提高了數(shù)據(jù)安全性卻降低了可用性；

(2)因使用統(tǒng)一的隱私預算參數(shù)ε，使得不同權(quán)重的邊添加的噪聲量一致，造成了隱私保護不均衡問題。

本文針對上述權(quán)重社交網(wǎng)絡隱私保護存在的問題，提出了一種基于譜聚類的差分隱私保護算法SCDP(Differential Privacy protection based on Spectral Clustering)，該算法可在減少噪聲添加量的同時均衡隱私保護程度，提高經(jīng)過隱私保護算法處理后的數(shù)據(jù)可用性。

2 相關工作及基本概念

2.1 相關工作

在隱私保護領域，許多學者對社交網(wǎng)絡差分隱私保護、個性化差分隱私保護和直方圖發(fā)布差分隱私保護等方面進行了研究。其中，蘭麗輝等[3]設計了一種基于差分隱私模型的LWSPA(Less Weighted Social Privacy Algorithm)算法，實現(xiàn)了邊權(quán)重的強保護。但是，直接添加噪聲的方式使得數(shù)據(jù)可用性下降。Li等[4]提出了合并桶和一致性推理策略來保護加權(quán)社交網(wǎng)絡圖。Huang等[5]在差分隱私模型的基礎上，結(jié)合聚類和隨機化算法，提出了一種差分隱私保護算法PBCN(Privacy preserving approach Based on Clustering and Noise)。該方法有效提高了處理后的數(shù)據(jù)可用性。Qin等[6]則提出了基于用戶與整個人群不同分區(qū)之間的聯(lián)系來逐步聚集用戶的LDPGen(Local Differential Privacy Generation)模型，該模型采用現(xiàn)有的社交網(wǎng)絡圖生成模型來構(gòu)建綜合社交網(wǎng)絡圖。這些方法均使用統(tǒng)一的隱私預算參數(shù)ε，導致隱私保護程度不夠均衡。在個性化隱私保護領域，Chen等[7]提出的發(fā)布差分私有綜合屬性圖的方法能夠在不以犧牲原始圖全局結(jié)構(gòu)屬性為代價的同時保留原始圖的社團結(jié)構(gòu)。在Sun等[8]制定的差分隱私方案中，要求每個參與者不僅考慮自己的隱私，還需考慮與其有關聯(lián)的鄰居的隱私。針對直方圖隱私發(fā)布問題，Qian等[9]提出了2種基于序列感知和局部密度的聚類方法來聚集直方圖，通過加權(quán)圖的權(quán)分布來研究發(fā)布拓撲信息的問題。這些方法依然存在數(shù)據(jù)可用性低、隱私保護不均衡等問題。

2.2 基本概念

(1)權(quán)重社交網(wǎng)絡。

設無向權(quán)重圖G=(V，E，W) 是一個表示權(quán)重社交網(wǎng)絡的三元組，其中V={v1,v2,…,vn}表示圖G中n個節(jié)點的集合，E={e=(vi,vj)|vi,vj∈V,i≠j}表示圖G中n個節(jié)點間邊的集合，W表示邊權(quán)重值的集合。在對數(shù)據(jù)處理時，權(quán)重社交網(wǎng)絡圖可以用鄰接矩陣來表示。

(2)譜聚類。

譜聚類算法將聚類問題轉(zhuǎn)化為圖的最佳分割問題[10]。相比傳統(tǒng)的k-means聚類算法，譜聚類具有更高效、聚類效果更均勻的優(yōu)點。根據(jù)不同的準則函數(shù)和譜映射方法，譜聚類算法有很多不同的具體實現(xiàn)方法，但都可以歸納為以下4個主要步驟：

步驟1構(gòu)建相似度矩陣T；

步驟2構(gòu)建度矩陣D，求出拉普拉斯矩陣L；

步驟3計算L的前l(fā)個特征向量；

步驟4通過一些經(jīng)典聚類算法對特征向量進行聚類。

本文利用譜聚類算法更高效、聚類效果更均勻的特點，將其用作SCDP算法中處理社交網(wǎng)絡圖聚類的算法，目的是提高算法效率和數(shù)據(jù)可用性。

定義1(相似度矩陣T) 權(quán)重wij為T第i行第j列對應的值。wij使用全連接法來構(gòu)建,本文使用高斯核函數(shù)定義邊權(quán)重。如式(1)所示：

(1)

其中，σ為高斯核函數(shù)的尺度參數(shù)。

則相似度矩陣T如式(2)所示：

(2)

定義2(度矩陣D) 無向權(quán)重圖中任意一點vi的度di的定義如式(3)所示：

(3)

則度矩陣D如式(4)所示：

(4)

定義3(拉普拉斯矩陣L) 拉普拉斯矩陣是譜聚類算法的重要工具，其計算方法如式(5)所示：

L=D-T

(5)

本文通過譜聚類算法將較大的權(quán)重社交網(wǎng)絡圖聚類形成不同的簇，再對聚類后具有相似特征的簇進行隨機噪聲添加，通過這樣的噪聲添加方式，能夠減少添加的噪聲，有效提高數(shù)據(jù)的可用性。

(3)ε-差分隱私模型。

定義4(差分隱私) 假設存在隨機算法K，對于任意2個鄰近數(shù)據(jù)集D和D′，若算法K滿足ε-差分隱私保護，用range(K)表示K的取值范圍，則對于所有的S∈range(K)，有：

P[K(D)∈S]≤exp(ε)×P[K(D′)∈S]

(6)

其中，P[E]表示事件E的泄露概率，其值與隨機算法K相關;ε表示差分隱私預算，決定了噪聲添加量,ε越小，噪聲添加量越大。

定義5(全局敏感度) 對于任意函數(shù)q:D→Rd，q的全局敏感度(簡稱為敏感度)定義如式(7)所示：

(7)

其中，D表示輸入數(shù)據(jù)集，D與D′為鄰近數(shù)據(jù)集，至多相差一條記錄即至多有一條邊不同。本文將全局敏感度設為Δq=Wmax，Wmax為差異邊最大差異權(quán)重值。d表示輸出實數(shù)向量的維度。

定義6(拉普拉斯機制) 給定數(shù)據(jù)集D，設有敏感度為Δq的函數(shù)q:D→Rd，若隨機算法K的輸出滿足：

K(D)=q(D)+Lap(Δq/ε)

(8)

則稱算法K滿足ε-差分隱私保護。差分隱私添加噪聲的大小跟ε成反比，簇中節(jié)點間的邊權(quán)重越大，理論上需要更強的保護，因此應該分配的ε值越小。由于全局的ε值不統(tǒng)一，本文使用組合差分隱私策略。

定義7(組合差分隱私) 已知數(shù)據(jù)集D={c1,c2,…,ci},D′={c′1,c′2,…,c′i}，給定隱私算法K，D和D′中都包含有i個簇，相對應的簇ci和c′i只相差一條記錄邊，每個簇的ε值不同。range(K)表示K的取值范圍，若K在ci和c′i上的任意輸出結(jié)果Ci(Ci∈range(K))滿足不等式P[K(ci)∈Ci]≤eεiP[K(c′i)∈Ci]，則稱K滿足組合差分隱私，如式(9)所示：

(9)

其中,εi是簇ci對應的隱私預算，Lap(Δqi/εi)是為ci生成的Laplace噪聲。

3 基于譜聚類的權(quán)重社交網(wǎng)絡差分隱私保護算法

3.1 基本思想

權(quán)重社交網(wǎng)絡隱私保護面臨著隱私保護不均衡、噪聲添加量過大等問題。針對這些問題，本文在差分隱私模型的基礎上，結(jié)合經(jīng)典的譜聚類算法，將權(quán)重社交網(wǎng)絡圖聚類成為擁有相似特征的不同的簇，再以Si為抽樣頻率向簇中的邊權(quán)重隨機添加拉普拉斯噪聲，以達到減少噪聲添加量的目的，進而提高數(shù)據(jù)的可用性。同時，本文算法設計了新的隱私預算參數(shù)ε′，使得噪聲添加更加均衡。再利用差分隱私模型中的組合定律證明所提算法滿足ε-差分隱私模型。

3.2 抽樣頻率Si

傳統(tǒng)的差分隱私保護對權(quán)重社交網(wǎng)絡直接添加拉普拉斯噪聲會造成噪聲添加量過大，數(shù)據(jù)可用性將會降低，為了盡可能地提高數(shù)據(jù)的可用性，本文提出的SCDP算法將采用隨機添加噪聲的方式，以Si為抽樣頻率，對聚類后網(wǎng)絡邊權(quán)重添加噪聲。Si的定義如式(10)所示：

Si=簇邊向量總數(shù)/邊向量總數(shù)

(10)

3.3 差分隱私預算ε′

針對權(quán)重社交網(wǎng)絡，添加噪聲時邊權(quán)重越大表示節(jié)點之間的關系越緊密，說明該邊需要強保護，需將隱私預算參數(shù)設定為一個較小的值。反之，隱私預算參數(shù)設定為一個較大的值。因此，在本文提出的SCDP算法中，為了提高隱私保護的均衡性，進而提高數(shù)據(jù)可用性，將隱私預算參數(shù)設計為ε′。ε′的定義如式(11)所示：

(11)

3.4 SCDP算法基本流程

本文所提出的SCDP算法的基本流程如算法1所示。

算法1SCDP算法

輸入：原始權(quán)重社交網(wǎng)絡圖G，初始隱私保護預算ε，聚類系數(shù)k。

輸出：隱私保護后的權(quán)重社交網(wǎng)絡圖G*。

步驟1計算n×n的相似度矩陣T;

步驟2計算度矩陣D;

步驟3計算拉普拉斯矩陣Lrw=D-1L=D-1(D-T);

步驟4計算Lrw的特征值，將特征值排序，取前l(fā)個特征值，并計算前l(fā)個特征值的特征向量u1,u2,…,ul;

步驟5由步驟4的l個列向量組成矩陣U={u1,u2,…,ul};

步驟6令yi∈Rk為U的第i行向量，其中i=1,2,…,n;

步驟7使用k-means算法將新樣本點Y={y1,y2,…,yn}聚類成簇C1,C2,…,Ck;

步驟8將C={C1,C2,…,Ck}中每個簇的節(jié)點和邊權(quán)重信息構(gòu)成三元組(i，j，x)，把所有簇間的邊的三元組單獨記錄下來，i、j是節(jié)點編號，x代表權(quán)重，當節(jié)點之間無連接時，x設置為0;

步驟9根據(jù)每個簇的三元組信息生成邊向量X=[X1,X2,…,Xk]，其中簇的邊權(quán)重集合表示為Xi={x1,x2,…,xi(i-1)/2};

步驟10根據(jù)每個簇的邊權(quán)重信息，得到k個簇的隱私預算ε′={ε′1,ε′2,…,ε′k};

步驟11對X以Si為頻率進行隨機抽樣，根據(jù)每個簇的ε′k值，生成拉普拉斯噪聲Lap=Lap(Δqk/ε′k);

步驟12為每個簇構(gòu)造服從Laplace分布的向量組〈Lap(Δqk/ε′k)〉X;

步驟13生成滿足ε-差分隱私的簇向量組P=X+〈Lap(Δqk/ε′k)〉X;

步驟14生成滿足ε-差分隱私的權(quán)重社交網(wǎng)絡圖G*={P1,P2,…,Pk};

步驟15輸出隱私保護后權(quán)重社交網(wǎng)絡圖G*。

3.5 算法的隱私性分析

由于每個簇使用的隱私預算ε′不同，無法直接對全局的隱私性進行分析。因此，本文通過差分隱私中的組合定律來進行間接分析。根據(jù)定義7給出的組合差分隱私需要滿足的不等式來分析算法的隱私性。如果所有的簇都滿足ε-差分隱私，則全局也滿足ε-差分隱私。

設G和G*只相差一條邊，隱私算法為K，range(K)表示K的取值范圍，若K在G和G*上的任意輸出結(jié)果M(M?range(K))滿足不等式P[K(G)∈M]≤eεkP[K(G*)∈M]，則本文隱私算法K滿足ε-差分隱私。

證明設m∈M，M與X維度相同，設其維度為X，由條件概率知：

(12)

其中,K(G)=m表示算法K在G上的輸出結(jié)果為m，σ=Δqi/ε′i是服從Laplace分布的尺度參數(shù)，由定義5可知，Δqi=Wmax。得：

(13)

由K(G)-K(G*)≤Wmax知，

(14)

□

4 實驗與結(jié)果分析

4.1 實驗設置

實驗數(shù)據(jù)如表1所示。其中，Lesmis[11]是帶權(quán)社交網(wǎng)絡圖，F(xiàn)ootball[12]是無權(quán)圖，利用隨機數(shù)生成器為其隨機生成[1，20]的整數(shù)作為無權(quán)圖中邊的權(quán)重值。

Table 1 Experimental data

4.2 實驗結(jié)果分析

在參數(shù)的選取上，本文選擇了算法執(zhí)行時間，以及常用于反映網(wǎng)絡特征的平均聚類系數(shù)和平均最短路徑作為測試SCDP算法數(shù)據(jù)可用性的參數(shù)。將算法處理后的參數(shù)與原始網(wǎng)絡參數(shù)進行對比，若結(jié)果與原始網(wǎng)絡參數(shù)越接近則說明算法處理后的數(shù)據(jù)可用性越高。

為驗證本文所提算法對社交網(wǎng)絡隱私保護的改進，實驗選取不同聚類系數(shù)k值下的SCDP算法與直接添加Laplace噪聲的傳統(tǒng)社交網(wǎng)絡差分隱私保護算法的執(zhí)行時間進行對比。為驗證本文算法的有效性，實驗選取不同聚類系數(shù)k值下的SCDP算法、LWSPA算法[3]和PBCN[5]算法進行對比，主要比較3種算法在平均聚類系數(shù)和平均最短路徑2個方面的表現(xiàn)。實驗均在Lesmis和Football網(wǎng)絡數(shù)據(jù)集上進行。其實驗結(jié)果分別如圖1～圖3所示。

Figure 1 Comparison of execution time 圖1 執(zhí)行時間對比

Figure 2 Comparison of average clustering coefficient圖2 平均聚類系數(shù)對比

Figure 3 Comparison of average shortest path圖3 平均最短路徑對比

由圖1可知，隨著聚類系數(shù)k值的增大，SCDP算法與直接添加Laplace噪聲的傳統(tǒng)算法的執(zhí)行時間均隨之增加。但是，SCDP算法的執(zhí)行時間明顯少于傳統(tǒng)算法，算法執(zhí)行效率更高。因此，可以證明本文所提的算法提高了社交網(wǎng)絡差分隱私保護的效率。

由圖2可知，隨著隱私預算ε增大，SCDP算法與對比算法LWSPA、PBCN的實驗結(jié)果均逐漸呈現(xiàn)接近原始值的趨勢，數(shù)據(jù)可用性逐漸提高。當k值為6,9時，由于本文提出的SCDP算法隨著ε值的增大，添加的噪聲量更少，使得數(shù)據(jù)的可用性提高，SCDP算法的平均聚類系數(shù)更接近原始值，因此表現(xiàn)優(yōu)于LWSPA和PBCN算法。

由圖3可知，隨著ε值的增大，噪聲的添加量下降，SCDP算法與對比算法均呈現(xiàn)出與原始值逐漸接近的趨勢。當k值為3時，因聚類數(shù)目較少，SCDP算法在聚類時的效果不佳，導致SCDP算法比LWSPA、PBCN表現(xiàn)較差。當k值為6,9時，SCDP算法的平均最短路徑值更加接近原始值，數(shù)據(jù)可用性高于對比算法。此時聚類劃分更多，聚類效果提升。并且，隨著ε值的增大，隨機添加的噪聲量下降，而新的隱私預算參數(shù)使得噪聲添加更加均衡，因此SCDP算法的表現(xiàn)優(yōu)于對比算法LWSPA和PBCN。這證明了本文算法的有效性。

5 結(jié)束語

本文針對現(xiàn)有的差分隱私保護算法存在的數(shù)據(jù)可用性低和隱私保護程度不均衡問題，提出了一種基于譜聚類算法的權(quán)重社交網(wǎng)絡差分隱私數(shù)據(jù)保護SCDP算法，并通過理論分析證明了SCDP算法滿足ε-差分隱私模型。在真實數(shù)據(jù)集上的仿真結(jié)果表明，本文提出的SCDP算法可有效提高數(shù)據(jù)的可用性。