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

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

(1.重慶郵電大學通信與信息工程學院,重慶 400065；2.重慶郵電大學通信新技術應用研究中心，重慶 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)的權重社交網(wǎng)絡差分隱私保護方法還存在以下問題：

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

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

本文針對上述權重社交網(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)了邊權重的強保護。但是，直接添加噪聲的方式使得數(shù)據(jù)可用性下降。Li等[4]提出了合并桶和一致性推理策略來保護加權社交網(wǎng)絡圖。Huang等[5]在差分隱私模型的基礎上，結合聚類和隨機化算法，提出了一種差分隱私保護算法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)絡圖生成模型來構建綜合社交網(wǎng)絡圖。這些方法均使用統(tǒng)一的隱私預算參數(shù)ε，導致隱私保護程度不夠均衡。在個性化隱私保護領域，Chen等[7]提出的發(fā)布差分私有綜合屬性圖的方法能夠在不以犧牲原始圖全局結構屬性為代價的同時保留原始圖的社團結構。在Sun等[8]制定的差分隱私方案中，要求每個參與者不僅考慮自己的隱私，還需考慮與其有關聯(lián)的鄰居的隱私。針對直方圖隱私發(fā)布問題，Qian等[9]提出了2種基于序列感知和局部密度的聚類方法來聚集直方圖，通過加權圖的權分布來研究發(fā)布拓撲信息的問題。這些方法依然存在數(shù)據(jù)可用性低、隱私保護不均衡等問題。

2.2 基本概念

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

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

(2)譜聚類。

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

步驟1構建相似度矩陣T；

步驟2構建度矩陣D，求出拉普拉斯矩陣L；

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

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

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

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

(1)

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

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

(2)

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

(3)

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

(4)

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

L=D-T

(5)

本文通過譜聚類算法將較大的權重社交網(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為差異邊最大差異權重值。d表示輸出實數(shù)向量的維度。

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

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

(8)

則稱算法K滿足ε-差分隱私保護。差分隱私添加噪聲的大小跟ε成反比，簇中節(jié)點間的邊權重越大，理論上需要更強的保護，因此應該分配的ε值越小。由于全局的ε值不統(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上的任意輸出結果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 基于譜聚類的權重社交網(wǎng)絡差分隱私保護算法

3.1 基本思想

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

3.2 抽樣頻率Si

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

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

(10)

3.3 差分隱私預算ε′

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

(11)

3.4 SCDP算法基本流程

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

算法1SCDP算法

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

輸出：隱私保護后的權重社交網(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é)點和邊權重信息構成三元組(i，j，x)，把所有簇間的邊的三元組單獨記錄下來，i、j是節(jié)點編號，x代表權重，當節(jié)點之間無連接時，x設置為0;

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

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

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

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

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

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

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

3.5 算法的隱私性分析

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

設G和G*只相差一條邊，隱私算法為K，range(K)表示K的取值范圍，若K在G和G*上的任意輸出結果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上的輸出結果為m，σ=Δqi/ε′i是服從Laplace分布的尺度參數(shù)，由定義5可知，Δqi=Wmax。得：

(13)

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

(14)

□

4 實驗與結果分析

4.1 實驗設置

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

Table 1 Experimental data

4.2 實驗結果分析

在參數(shù)的選取上，本文選擇了算法執(zhí)行時間，以及常用于反映網(wǎng)絡特征的平均聚類系數(shù)和平均最短路徑作為測試SCDP算法數(shù)據(jù)可用性的參數(shù)。將算法處理后的參數(shù)與原始網(wǎng)絡參數(shù)進行對比，若結果與原始網(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ù)集上進行。其實驗結果分別如圖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的實驗結果均逐漸呈現(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 結束語

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