基于譜聚類的社交網(wǎng)絡(luò)差分隱私保護(hù)算法研究*

袁 泉，晏飛揚(yáng)，文志云，張振康

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

1 引言

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

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

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

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

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

2 相關(guān)工作及基本概念

2.1 相關(guān)工作

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

2.2 基本概念

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

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

(2)譜聚類。

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

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

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

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

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

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

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

(1)

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

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

(2)

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

(3)

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

(4)

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

L=D-T

(5)

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

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

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

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

(6)

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

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

(7)

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

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

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

(8)

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

定義7(組合差分隱私) 已知數(shù)據(jù)集D={c1,c2,…,ci},D′={c′1,c′2,…,c′i}，給定隱私算法K，D和D′中都包含有i個(gè)簇，相對(duì)應(yīng)的簇ci和c′i只相差一條記錄邊，每個(gè)簇的ε值不同。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對(duì)應(yīng)的隱私預(yù)算，Lap(Δqi/εi)是為ci生成的Laplace噪聲。

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

3.1 基本思想

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

3.2 抽樣頻率Si

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

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

(10)

3.3 差分隱私預(yù)算ε′

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

(11)

3.4 SCDP算法基本流程

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

算法1SCDP算法

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

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

步驟1計(jì)算n×n的相似度矩陣T;

步驟2計(jì)算度矩陣D;

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

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

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

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

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

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

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

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

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

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

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

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

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

3.5 算法的隱私性分析

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

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

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

(12)

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

(13)

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

(14)

□

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置

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

Table 1 Experimental data

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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