大型社交網絡的差分隱私保護算法

王婷婷，龍士工,2+，丁紅發

(1.貴州大學 計算機科學與技術學院，貴州 貴陽 550025；2.貴州大學 公共大數據國家重點實驗室，貴州 貴陽 550025；3.貴州財經大學 信息學院，貴州 貴陽 550025)

0 引 言

目前關于社交網絡的差分隱私保護方法較多[1-4]，這些隱私保護方法雖然都能夠抵抗背景知識攻擊實現社交網絡數據的隱私保護，但都只適用于小型社交網絡，數據量不大。隨著用戶量增大、用戶屬性增多，這些方法都需要添加大量噪聲，導致數據可用性變差；且當有n個社交用戶時，需要發布n×n的大型矩陣，導致在計算和存儲空間上的高成本。本文針對大型社交網絡差分隱私保護中數據可用性過低的問題，提出了一種基于隨機投影及差分隱私的大型社交網絡隱私保護算法，該算法利用隨機投影將高維社交網絡數據映射到低維空間，再添加差分隱私噪聲保護用戶隱私。算法通過降低原始數據維度減少噪聲添加，提高了數據可用性并保證了發布數據在基于歐式距離挖掘中數據可用性。

1 相關工作

差分隱私在社會網絡隱私保護的研究主要集中于設計恰當的算法使其滿足差分隱私和減少差分隱私噪聲量兩方面。Li等[1]針對用戶的個人隱私偏好，提出了基于個性化差分隱私保護方法。Yan等[2]提出一種基于差分隱私和關聯挖掘的社交網絡隱私保護算法。Wang等[3]根據組間k-不可區分性將相同邊權重的桶合并，減少了噪聲添加。Karwa等[4]利用隨機響應機制生成合成網絡，利用似然估計推斷丟失數據并將隨機圖模型擬合到生成的合成網絡。Can等[5]提出了出度和分區的隱私保護方法，能有效降低算法敏感度，減少噪聲量。Wang等[6]針對社交網絡中實時數據發布問題提出動態分組機制和自適應預算分配機制，具有較強的隱私保障。Gao等[7]利用層次隨機圖描述原始社交網并通過馬爾可夫鏈構造最佳匹配樹，對節點加噪聲后轉化為下角矩陣。Liu等[8]將社交網絡圖進行劃分，對劃分后的圖根據不同擾動策略和查詢函數添加不同拉普拉斯噪聲。但將這些方法運用到社交網絡分析的主要特點是對計算和存儲空間要求高，且當用戶量大時需添加大量噪聲，影響數據可用性。

鑒于現代社交網絡用戶數量龐大且屬性值多，Wang等[9]提出了LNPP算法，通過計算鄰接矩陣前k個特征值及其對應的特征向量，添加拉普拉斯噪聲得到待發布數據，有效降低了發布矩陣維數并能夠有效保留社交網絡的光譜特征。Lan等[10]通過重構分割后的社交網絡子圖并用向量集來表示，構建滿足Johnson-Lindenstrauss定理的映射函數，利用隨機投影技術對高維向量集進行降維得到待發布向量集。綜上所述，如何能夠有效設計對大型社交網絡隱私保護算法還相對較少，對高維復雜的社交網絡數據進行降維并實現隱私保護，同時保持數據的高可用性，仍然具有挑戰性。

針對上述問題，本文提出能保持數據高可用性的隨機投影差分隱私保護算法。該算法首先利用隨機投影對社交網絡圖的鄰接矩陣進行降維，然后對降維后的矩陣進行差分隱私保護。通過理論和實驗驗證該算法滿足(ε,δ)-差分隱私保護；對比結果表明，該算法比已有算法更加適用大規模社交網絡數據發布的隱私保護，計算復雜度更低，數據效用更高。

2 相關知識

本章主要介紹關于社交網絡圖、隨機投影和差分隱私基本概念及相關知識。

2.1 社交網絡圖

社交網絡圖表示用戶個體以及用戶個體之間的關系，設G=(V,{E})是一個表示社交網絡連通性的二元圖,V在圖中的數據元素稱為頂點V={v1,v2,…,vn},代表社交網絡圖中用戶節點集合,{E}是用戶節點之間邊的集合，社交網絡中用戶節點數目為n=|V|。圖1是簡單的社交網絡圖。

圖1 社交網絡圖G

2.2 隨機投影

數據降維在數據挖掘和分析中有重要作用，隨機投影相比于傳統維數規約方法具有無需考慮原始數據本身固有的結構、計算負載低、運行效率高等特點，目前被廣泛用于解決“維數爆炸”問題。隨機投影技術屬于低失真嵌入，利用矩陣相乘將原始高維空間投影到一個低維子空間，其重要理論依據就是Johnson-Lindenstrauss定理[11](簡稱J-L定理)。

(1)

該定理說明在高維空間中的樣本點可以在保持原始空間兩個元素之間的歐式距離近似相等的情況下嵌入到低維空間中，通過減少數據維度來改變數據的原始形式，但仍能保持其統計特征。高斯隨機矩陣[12]即矩陣中的元素服從高斯分布N(0,σ2)，是最早證明滿足J-L定理的隨機投影矩陣。

2.3 差分隱私

差分隱私保護模型忽略攻擊者的背景知識以及不作任何限制性假設對手，可保障鄰近數據集的查詢輸出具有概率不可區分性[13]。

定義1 (ε,δ)-差分隱私[14,15]：對于任意的兩個數據集D1和D2，它們之間相差最多為一條記錄，若一個隨機函數A滿足(ε,δ)-差分隱私保護，則對于所有的S?Range(K)有

Pr[A(D1)∈S]≤eεPr[A(D2)∈S]+δ

(2)

δ是差分隱私中精確性參數，當δ=0時，則稱隨機函數A滿足ε-差分隱私保護。其中，Pr[E]表示事件E披露風險，ε是預算參數，代表了差分隱私保護水平，其值越小，隱私保護級別越高。

目前有3種噪聲添加機制，分別是拉普拉斯機制(Laplace mechanism)、指數機制(exponential mechanism)和高斯機制(Gaussian mechanism)。其中，高斯機制在原始數據集中加入滿足服從高斯分布的噪聲來擾動原始數據以實現差分隱私保護[14]。拉普拉斯機制和高斯機制適用于數值型，而指數機制適用于非數值型。

定義2 高斯機制[15]:對于給定數據集合D，有查詢函數f:D→R，如果有c2>2ln(1.25/δ),σ≥cΔ2f/ε并且N(0,σ2)獨立同分布，則算法A滿足

A(D)=f(D)+N(0,σ2)

(3)

Δ2f是查詢函數的敏感度，與拉普拉斯機制中敏感度定義不同的是縮放到l2-敏感度而不再是縮放到l1-敏感度，其定義如下。

定義3 敏感度[15]:數據集D1和D2至多相差一條數據集，假設Δ2f是隨機查詢函數f的敏感度，則

(4)

3 基于隨機投影及差分隱私的社交網絡隱私保護方法

本節針對有n個用戶的社交網絡數據，給出隨機投影矩陣的敏感度定義和基于隨機投影的差分隱私保護方法RP-DP(random projection and differential privacy)，并證明該算法能滿足差分隱私需求，且數據保持較高可用性。

3.1 RP-DP算法

算法1：RP-DP算法

輸入：社交網絡圖G，隨機投影數量m，隱私保護水平ε，差分隱私參數δ

(1)建立社交網絡圖的鄰接矩陣A←G，A∈Rn×n

(3)計算矩陣P的敏感度ω2(P)

(4)計算投影后的矩陣AP=A×P

(6)生成噪聲矩陣Δ←Δi,j～N(0,σ2)

3.2 算法的差分隱私保證

本小節構造隨機投影差分隱私定理，證明RP-DP算法滿足(ε,δ)-差分隱私定義。

Pr[X+Δ∈D]≤eεPr[Y+Δ∈D]+δ

(5)

對式(5)的證明如下：

將集合D拆分成D1，D2兩部分

D1=d∈D:X-Y,d-X≤ωR
D2=d∈D:X-Y,d-X>ωR

exp(ε)Pr[Y+Δ∈D1]

(6)

(7)

由定理2可知，在投影后的社交網絡數據中添加服從高斯分布的噪聲矩陣時，噪聲矩陣的方差取決于投影矩陣的敏感度大小和隱私保護水平ε，敏感度越大，隱私預算參數越小方差越大。

3.3 數據可用性保證

本小節分析原始數據集經過RP-DP算法保護后，任意兩用戶間的歐幾里得距離的平方在期望值相對不變，即保證原始社交網絡數據在基于歐式距離分析挖掘中的數據可用性。

(8)

因此，如果對于指定投影維數m與隱私保護水平ε(定理2中σ值取等),那么任意兩用戶之間擾動后距離平方比原始距離平方的期望值多一個定值2mσ2。雖然用戶之間的歐式距離會有一定偏移，但是相對距離基本保持不變，這意味在原始空間上接近的用戶在隱私保護后的空間仍能保持接近。因此在數據挖掘過程中，對于基于歐式距離的算法分析時，數據仍保持可用性。

4 實驗與對比

本節通過對斯坦福大學公開數據集SNAP Social networks中Bitcoin OTC子集(含5881個節點35 592條邊)進行隨機投影差分隱私保護和譜聚類實驗，來驗證RP-DP算法的有效性和數據可用性保持效果。

實驗首先對原始數據集通過隨機投影降至同一低維度并加入不同隱私保護水平的噪聲矩陣，比較用戶間歐氏距離的變化；其次，對原始數據集、差分隱私保護數據集和隨機投影差分隱私數據集進行譜聚類實驗，在不同隱私保護水平下，對比差分隱私算法和RP-DP算法的譜聚類效用NMI值變化；最后，利用RP-DP算法將原始社交網絡數據集降至不同維度并添加不同隱私保護水平噪聲，再對比數據聚類效用NMI值變化。

4.1 實驗結果與分析

實驗1：RP-DP算法在不同隱私預算下對社交網絡用戶間歐式距離的影響

為了驗證RP-DP算法在不同隱私保護水平下，對社交網絡用戶間歐式距離的影響，實驗1從Bitcoin OTC數據集中隨機采樣選取100個用戶，并計算用戶間原始歐式距離、經RP-DP算法在不同隱私保護水平下擾動后的歐式距離。該實驗中，將Bitcoin OTC數據集降維至500維(m=500，即RP-DP算法不添加差分隱私噪聲)及差分隱私保護水平分別設為ε=0.9,ε=0.7,ε=0.5,ε=0.3。為了實驗結果的準確性，在每個隱私預算下進行100次實驗后求平均值。實驗結果如圖2所示。

圖2 用戶間歐式距離變化對比

在圖2中，m是投影數量，即將原始n×n維矩陣降至n×m維矩陣，ε是差分隱私預算參數，其值越小隱私保護水平越高。由圖2可知，只對Bitcoin OTC數據集降至500維時，數據間距離變化不大，這符合J-L定理，高維空間中的數據在歐式距離近似相等的情況下可以嵌入到低維空間中；在隱私保護水平為ε=0.9，ε=0.7時，經RP-DP算法保護后的距離與原始距離偏離較小，隨著隱私保護水平的增加，數據間的距離和原始距離偏差變大。但即使在高水平隱私保護水平下(ε=0.3)，數據間的相對距離也能保持不變，原始空間用戶在轉換后的空間上仍能保持偏序關系。

對實驗1中用戶間原始距離和不同隱私預算下的用戶距離分別計算其均值、方差及相關系數各統計量的值，結果見表1。

由表1可知，對投影后的矩陣加入不同隱私保護程度噪聲后，隨著隱私保護水平的增高，加入的噪聲量越大，用戶間距離均值不斷增大，方差逐漸減小，發布數據與原始數據的相關性遞減。其中，均值變化表明RP-DP算法添加較少噪聲時，對原始數據的影響較小，添加的噪聲量越多，對原始數據的影響也越大；方差變化表明RP-DP算法隨噪聲的不斷添加，對原始數據的隱私保護效果不斷增強；相關系數變化表明，經過RP-DP算法保護后的發布數據能保持與原始數據較高的相關性，噪聲對數據間的相關性影響不大，特別是添加少量噪聲時(ε=0.9,ε=0.7)，能夠保持與原始數據較高的相關性，僅當添加大量噪聲(ε=0.3)時才會顯著影響發布數據和原始數據間的相關性。

表1 用戶距離各統計量對比

實驗2：差分隱私算法與RP-DP算法對比實驗

實驗2對Bitcoin OTC數據集分別通過差分隱私算法[15]和RP-DP算法(m=500)保護后的發布數據集進行譜聚類(聚8類)對比，實驗以Bitcoin OTC數據集不做變化直接聚類的結果作為標準劃分，與兩種發布數據集的聚類結果對比，計算標準化互信息(normalized mutual information，NMI)來衡量發布數據集的數據可用程度。NMI∈[0,1]，NMI值越大，X和Y劃分就越相似，X表示原始數據的譜聚類結果，Y表示經過隱私保護算法后生成待發布數據集的譜聚類結果。實驗結果如圖3所示。

圖3 不同隱私保護算法發布數據集相對原始數據集譜聚類的NMI對比(m=500)

圖3是經過不同隱私保護算法生成的發布數據集相對原始數據集譜聚類的NMI對比圖。在圖3中，DP表示對Bitcoin OTC數據集進行差分隱私保護后相對原始數據集的譜聚類NMI在不同隱私預算下的變化曲線；RP-DP(m=500)表示對Bitcoin OTC數據集利用RP-DP算法降至500維時，通過RP-DP算法保護后相對原始數據集的譜聚類NMI在不同隱私預算下的變化曲線。由圖3知，對數據集不降維直接利用DP算法保護社交網絡數據，譜聚類結果相對于原始數據的NMI值小于0.1，數據可用性較差；當投影數量m=500時，利用RP-DP算法保護社交網絡數據，在隱私保護水平ε>0.45時，NMI值大于0.7，數據有較好的可用性。圖3表明差分隱私直接對大規模社交網絡數據進行隱私保護，會導致數據可用性很差；通過RP-DP算法對大規模社交網絡數據降維并進行隱私保護，可以保持數據較好的可用性。

實驗3：RP-DP算法將原始數據降至不同維度隨差分隱私預算變化的對比實驗

為了評估RP-DP算法中投影數量對數據可用性影響，實驗3將Bitcoin OTC數據集通過RP-DP算法降至不同維度，并調整差分隱私預算大小進行對比，結果如圖4所示。

圖4 RP-DP算法不同投影數量的發布數據集相對原始數據集譜聚類的NMI對比

圖4是利用RP-DP算法對Bitcoin OTC數據集降至100-1000維度并添加不同差分隱私保護水平ε=0.6,ε=0.5,ε=0.4,ε=0.3下譜聚類NMI值變化曲線。圖4表明，在相同隱私保護水平下，隨著投影數量增加，數據可用性不斷提高；投影到相同維度時，隱私保護程度越大，導致加入的噪聲量越多，數據可用性變差。當投影數量小于200時，即使在低隱私保護水平ε=0.6，NMI值仍小于0.6，這是由于當投影數量m值變小時，一方面，降維過程中數據信息損耗增加；另一方面，投影矩陣的敏感度增加，噪聲量的多少與敏感度成正比，影響了數據可用性。當投影數量大于500時，在高隱私保護水平ε=0.4的情況下，NMI值仍保持在0.72以上。

實驗1表明，RP-DP算法通過隨機投影將原始數據映射到低維子空間可以減少注入的噪聲量，同時能夠保持用戶間歐氏距離的可計算性；實驗2和實驗3表明，差分隱私直接用于大型社交網絡隱私保護時需要大量噪聲，導致數據可用性過低，但利用RP-DP算法降維后能夠有效減少噪聲添加，提高了數據可用性。

4.2 對比分析

本小節將所提出RP-DP算法與相關文獻性對比，見表2。

表2 社交網絡差分隱私保護算法對比

表2中文獻[3,7,9,10]和RP-DP算法都研究適用于社交網絡的隱私保護算法，其中文獻[3,7]是對社交網絡采用不同的噪聲機制實現差分隱私隱私保護，僅適用于小型社交網絡數據發布；文獻[9,10]和RP-DP算法適用于大規模社交網絡數據發布，其中文獻[9]中通過計算原始矩陣的前k個特征值與特征向量并添加拉普拉斯噪聲生成待發布數據，降低了數據可用性且需要對原始矩陣進行計算，文獻[10]中先將社交網劃分為不同子圖，再通過J-L定理降低向量維度，這樣較大程度改變了社交網絡圖的原始結構，且隱私保護效果較差，而RP-DP算法利用隨機投影降維并添加高斯噪聲實現(ε,δ)-差分隱私保護。文獻[17]利用主成分分析差分隱私通過添加拉普拉斯噪聲達到隱私保護目的，該方法通過主成分分析對社交網絡數據降維，需計算數據矩陣的協方差、特征值和特征向量，計算復雜度較高；RP-DP算法不需要存儲原始數據或計算大型n×n矩陣，能夠有效簡化計算，并且只需要加入少量的噪聲，提高了數據可用性。

5 結束語

本文針對面向數據挖掘的社交網絡隱私保護數據發布和共享問題，提出了一種基于隨機投影及差分隱私的大型社交網絡數據發布算法。算法能夠保證發布數據在基于歐式距離分析挖掘中的數據可用性；并有效降低待發布社交網絡數據矩陣的維度，解決了發布n×n大型矩陣的困難，且差分隱私保護只需加入少量噪聲，大大提高了數據可用性。此外，該算法比已有算法更加適用大規模社交網絡數據，簡化了計算復雜性。下一步的研究目標是當原始數據降至非常低維度時，如何提高數據可用性。