鄭 劍，楊立聰

(江西理工大學(xué) 信息工程學(xué)院，江西 贛州 341000)

0 引 言

目前運(yùn)用于社交網(wǎng)絡(luò)的差分隱私保護(hù)方法主要是關(guān)于小型社交網(wǎng)絡(luò)。盡管這些隱私保護(hù)方法可以抵御背景知識攻擊來達(dá)到保護(hù)社交網(wǎng)絡(luò)的目的，但是隨著大數(shù)據(jù)時代的降臨，用戶量增大、用戶屬性增多，這些方法都需要加入大量噪聲，導(dǎo)致數(shù)據(jù)可用性變差。當(dāng)某網(wǎng)絡(luò)擁有n個社交用戶時，需發(fā)布n×n的大型矩陣，導(dǎo)致計算和存儲成本過高,因此如何提高大型社交網(wǎng)絡(luò)發(fā)布數(shù)據(jù)的數(shù)據(jù)可用性顯得尤為重要。針對這一思路，該文提出了一種基于奇異值分解的大型社交網(wǎng)絡(luò)差分隱私保護(hù)算法(random projection-singular value decomposition and differential privacy，RP-SVD-DP)，RP-SVD-DP算法利用隨機(jī)投影將高維社交網(wǎng)絡(luò)數(shù)據(jù)映射到低維空間，再對降維后的矩陣進(jìn)行奇異值分解，在奇異值中加入少量差分隱私噪聲保護(hù)用戶隱私，提高發(fā)布數(shù)據(jù)在基于歐氏距離數(shù)據(jù)挖掘中的數(shù)據(jù)可用性。

1 相關(guān)工作

該文利用差分隱私對社交網(wǎng)絡(luò)實現(xiàn)隱私保護(hù)，因此相關(guān)的已有工作包括：黃海平等[1]提出了一種基于非交互的差分隱私保護(hù)模型實現(xiàn)對邊權(quán)的保護(hù)。周藝華等[2]提出了基于聚類的社交網(wǎng)絡(luò)隱私保護(hù)方法。朱勇華等[3]提出一種差分隱私保護(hù)模型的擾動策略。王丹等[4]提出一種權(quán)重社交網(wǎng)絡(luò)隱私保護(hù)算法。劉爽英等[5]提出一種滿足差分隱私保護(hù)模型的邊權(quán)重保護(hù)策略。Wang Dan等[6]通過對原始的加權(quán)社交網(wǎng)絡(luò)進(jìn)行分割，然后在每個子網(wǎng)絡(luò)利用差分隱私算法來減少噪聲的加入量。Li Xiaoye等[7]提出了一種兩步差分私有方法來釋放群體間聚類系數(shù)的分布。Liu Peng等[8]提出了一個保留社區(qū)結(jié)構(gòu)信息的局部差異隱私模型。但是將這些方法運(yùn)用到社交網(wǎng)絡(luò)，需要很高的計算和儲存空間，且當(dāng)用戶量大時需要添加大量噪聲，影響數(shù)據(jù)可用性。

隨著大數(shù)據(jù)時代來臨，社交網(wǎng)絡(luò)用戶數(shù)量龐大且屬性值多，蘭麗輝等[9]通過重構(gòu)分割后的社交網(wǎng)絡(luò)子圖并用向量集來表示，構(gòu)建滿足Johnson-Lindestrauss定理的映射函數(shù)，利用隨機(jī)投影技術(shù)對高維向量集進(jìn)行降維得到待發(fā)布向量集。王婷婷等[10]提出一種基于隨機(jī)投影的社交網(wǎng)絡(luò)隱私保護(hù)。綜上所述，如何能夠針對大型社交網(wǎng)絡(luò)進(jìn)行隱私保護(hù)的算法還相對較少，對高維復(fù)雜的社交網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行降維并實現(xiàn)隱私保護(hù)，同時保證數(shù)據(jù)的高可用性，仍然具有挑戰(zhàn)性。

針對王婷婷等[10]提出的隱私保護(hù)算法中存在對降維數(shù)據(jù)直接添加噪聲導(dǎo)致基于歐氏距離數(shù)據(jù)挖掘中數(shù)據(jù)可用性較差的問題，結(jié)合隨機(jī)投影、奇異值分解和差分隱私，提出一種基于奇異值分解的大型社交網(wǎng)絡(luò)差分隱私保護(hù)算法。RP-SVD-DP算法第一步利用隨機(jī)投影對高維社交網(wǎng)絡(luò)圖的數(shù)據(jù)進(jìn)行降維，第二步對降維后的數(shù)據(jù)進(jìn)行奇異值分解并對奇異值加入高斯噪聲，最后通過奇異值分解逆運(yùn)算生成待發(fā)布矩陣。利用奇異值矩陣是一個僅有主對角線上有值的矩陣，值的個數(shù)為矩陣的秩，與對降維后的數(shù)據(jù)直接添加高斯噪聲相比，對奇異值矩陣中的值添加高斯噪聲能有效地降低噪聲的加入量。設(shè)計基于歐氏距離差實驗和基于譜聚類實驗對RP-SVD-DP算法和基于隨機(jī)投影社交網(wǎng)絡(luò)差分隱私算法的數(shù)據(jù)可用性進(jìn)行對比分析。

2 相關(guān)知識

本章主要介紹差分隱私、社交網(wǎng)絡(luò)圖、隨機(jī)投影、奇異值分解和RP-DP算法的基本概念及相關(guān)知識。

2.1 差分隱私

差分隱私[11]是Dwork等在2006年針對數(shù)據(jù)庫數(shù)據(jù)隱私保護(hù)的問題提出的一種新型隱私保護(hù)模型，該模型將隨機(jī)噪聲注入到真實數(shù)據(jù)集中進(jìn)行擾亂，達(dá)到隱私保護(hù)的效果，且數(shù)據(jù)的整體屬性保持不變，擾亂后的數(shù)據(jù)仍可用于數(shù)據(jù)挖掘等操作。

定義1 (ε,δ)-差分隱私[12]：給定一個隨機(jī)查詢算法К，對于任意鄰近數(shù)據(jù)集D和D'，若К在數(shù)據(jù)集D和D'查詢下得到的結(jié)果滿足式(1)，則稱隨機(jī)查詢算法К滿足(ε,δ)-差分隱私。

Pr[К(D)∈S]≤eε×Pr[К(D')∈S]+δ

(1)

其中，Pr[·]表示若應(yīng)用隨機(jī)查詢算法M數(shù)據(jù)可能被泄露的風(fēng)險；ε表示隨機(jī)查詢算法К所能夠提供的隱私保護(hù)水平；δ表示允許每個目標(biāo)數(shù)據(jù)都會存在δ大小的概率隱私會泄露，δ的取值通常是很小的常數(shù)。

定義2 高斯機(jī)制[12]：對于給定數(shù)據(jù)集D，有查詢函數(shù)f:D→Rd，如果有c2>2ln(1.25/δ)，σ≥Δ2(f)/ε，并且N(0,σ2)獨立同分布，則算法A滿足(ε,δ)差分隱私。

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

(2)

定義3 敏感度[12]：數(shù)據(jù)集D和D'至多相差一條數(shù)據(jù)集，假設(shè)Δ2(f)是隨機(jī)查詢函數(shù)f的敏感度，則：

(3)

2.2 社交網(wǎng)絡(luò)圖

社交網(wǎng)絡(luò)包括用戶以及用戶之間的關(guān)系，通常用圖來表示，圖1是一個簡單的社交網(wǎng)絡(luò)圖。其中頂點表示用戶，邊表示圖中兩個用戶之間的關(guān)系。

對社交網(wǎng)絡(luò)圖G=(V,E)進(jìn)行差分隱私保護(hù)可以轉(zhuǎn)化成對圖的鄰接矩陣A∈{0,1}n×n進(jìn)行差分隱私保護(hù)。其中節(jié)點i和節(jié)點j若存在關(guān)系則Aij=1，否則Aij=0。圖1社交網(wǎng)絡(luò)圖對應(yīng)的鄰接矩陣為：

2.3 隨機(jī)投影

隨機(jī)投影是一種比較有效的降維方法，具有無需考慮原始數(shù)據(jù)本身固有結(jié)構(gòu)、計算負(fù)載低、運(yùn)行效率高等特點。隨機(jī)投影的理論依據(jù)是Johnson-Lindestrauss定理[13]。

定義4 Johnson-Lindestrauss定理(簡稱J-L定理)：對給定的失真率ε(0<ε<1)和任意正整數(shù)d，令整數(shù)k=O(log(n)/ε2)，那么對于任意Rd空間中的n個點構(gòu)成的集合V，始終存在一個映射f:Rd→Rk使得所有的x,y∈V，有：

(4)

2.4 奇異值分解

奇異值分解(singular value decomposition，SVD)屬于線性代數(shù)中的一種矩陣分解，廣泛應(yīng)用于機(jī)器學(xué)習(xí)的領(lǐng)域中。

定義5 奇異值分解[14]：設(shè)m×n階矩陣A，且m≥n≥0。令A(yù)的秩為r，則存在酉矩陣U、V使得：

(5)

其中，Σ=diag[υ1,υ2,…,υr]為對角矩陣，|Σ|=r，υi為A的奇異值，且υ1≥υ2≥…≥υr≥0，U、V分別為A的左右奇異向量。

定義6 Mirsky定理[15]：令X與X'為具有相同奇異值數(shù)的兩個矩陣，且：

(6)

那么對于任意的酉不變范數(shù)‖·‖，有：

(7)

定義7 矩陣2-范數(shù)[16]：對于矩陣A(m×n),Aij為A中對應(yīng)位置的元素，則它的2-范數(shù)為：

(8)

其中，λ1為ATA的最大特征值。

2.5 RP-DP算法

基于隨機(jī)投影的社交網(wǎng)絡(luò)差分隱私算法(random projection and differential privacy，RP-DP)是王婷婷等[10]針對有n個用戶的社交網(wǎng)絡(luò)數(shù)據(jù)，結(jié)合隨機(jī)投影提出的差分隱私算法。該算法通過對原始社交網(wǎng)絡(luò)圖的鄰接矩陣?yán)秒S機(jī)投影進(jìn)行降維，再對降維矩陣加入高斯噪聲，最后發(fā)布經(jīng)過混淆的矩陣。算法的步驟如下：

輸入：具有n個用戶的社交網(wǎng)絡(luò)G

(1)生成社交網(wǎng)絡(luò)圖G的鄰接矩陣A；

(2)生成投影矩陣P；

(3)利用隨機(jī)投影生成低維矩陣Ap=A×P；

(4)生成噪聲矩陣Δ～N(0,σ2)；

RP-DP算法利用隨機(jī)投影將原始社交網(wǎng)絡(luò)從n×n維高維矩陣A轉(zhuǎn)化為m×n低維矩陣Ap，其中m?n，簡化了算法的計算復(fù)雜性。但RP-DP算法存在一個問題，在步驟4中生成的噪聲矩陣Δ∈Rn×m仍是m×n維的，所帶來的噪聲對數(shù)據(jù)的可用性破壞仍是十分巨大的。在RP-DP算法中，對數(shù)據(jù)集中任意兩個用戶x,y，記兩個用戶之間的原始距離為dist(x,y)=‖x-y‖2。經(jīng)過RP-DP算法輸出后可得x'=xP+Δ1,y'=yP+Δ2，則用戶之間的歐氏距離為：

dist(x',y')=‖x'-y'‖2=

‖(x-y)P+Δ1+Δ2‖2

(9)

其中經(jīng)RP-DP算法擾動后用戶之間距離平方的期望為：

(10)

根據(jù)期望公式可知，原始數(shù)據(jù)中任意兩個用戶之間擾動后距離的平方比原始距離的平方的期望值多一個定值2mσ2。因此減少加入噪聲矩陣的維度m可以減少加入的噪聲量，使擾動后的期望值更低。因此引入奇異值分解，對投影后的矩陣進(jìn)行奇異值分解，對奇異值添加高斯噪聲，添加更少的噪聲，提高數(shù)據(jù)可用性。

3 RP-SVD-DP算法

考慮到RP-DP算法中存在將高維數(shù)據(jù)降低至低維數(shù)據(jù)中直接添加高斯噪聲會產(chǎn)生較大噪聲量的問題，該文提出一種基于奇異值分解的社交網(wǎng)絡(luò)差分隱私算法。

3.1 算法概述

RP-SVD-DP算法將隨機(jī)投影、奇異值分解相結(jié)合解決了RP-DP算法中加入噪聲量較大的問題。RP-SVD-DP算法首先生成社交網(wǎng)絡(luò)的鄰接矩陣，利用隨機(jī)投影將高維矩陣轉(zhuǎn)化為低維矩陣，然后對低維矩陣進(jìn)行奇異值分解，分解成左奇異矩陣、右奇異矩陣和奇異值矩陣，最后對奇異值矩陣添加高斯噪聲，根據(jù)奇異值分解逆運(yùn)算生成待發(fā)布矩陣。

RP-SVD-DP算法對奇異值矩陣添加噪聲，因為奇異值矩陣只有主對角線上有值，并且值的個數(shù)為矩陣的秩，相比于RP-DP算法中的m×n維的噪聲矩陣Δ，有效地減小了算法對數(shù)據(jù)集添加的噪聲量。

3.2 算法流程

根據(jù)流程圖可知，算法大致可以分為7個步驟：

(1)對原始社交網(wǎng)絡(luò)圖進(jìn)行預(yù)處理，計算其鄰接矩陣A，A∈Rn×n；

(2)生成一個隨機(jī)高斯矩陣P，矩陣P中的隨機(jī)數(shù)服從高斯分布N(0,1/m)；

(3)利用隨機(jī)高斯矩陣P計算投影后矩陣AP=A×P，AP∈Rn×m；

(5)對奇異值υ添加高斯噪聲Δ～N(0,σ2)得到υ'；

3.3 算法偽代碼

算法1：RP-SVP-DP算法。

Input：Original social network GraphG

(1)adjacency matrixA←G,A∈Rn×n

(3)Dimension reductionAp=A×P

(5)Add noise Σ'=Σ+Δ～N(0,σ2)

3.4 算法隱私性分析

首先計算經(jīng)隨機(jī)投影降到m維后的矩陣多維奇異值查詢函數(shù)的全局敏感度。令查詢函數(shù)f:D→Rd，輸入為圖G(含n的節(jié)點)，整數(shù)m(1≤m≤n)，輸出為圖G經(jīng)隨機(jī)投影降維后矩陣的奇異值組成的向量。

不失一般性，在原圖G中對節(jié)點v與u之間的邊權(quán)重改變1，作為D'。令圖G的鄰接矩陣為A，則有‖A-A'‖2=1。令經(jīng)過隨機(jī)投影降維后的矩陣為Ap，則有：

(11)

其中，Pi,j是服從N(0,1/m)的正態(tài)分布。

由定義7可知：

(12)

3.5 數(shù)據(jù)可用性保障

本節(jié)分析原始數(shù)據(jù)經(jīng)過RP-SVD-DP算法保護(hù)后，任意兩個用戶之間的歐幾里得距離的平方在期望值相對不變，即保證原始社交網(wǎng)絡(luò)數(shù)據(jù)在基于歐氏距離分析挖掘中的數(shù)據(jù)可用性。

對數(shù)據(jù)中任意兩個用戶x,y，記兩個用戶之間的原始距離為dist(x,y)=‖x-y‖2。經(jīng)RP-SVD-DP算法輸出后，則有dist(x',y')=‖x'-y'‖2‖(x-y)P+Δ1+Δ2‖2。

令Δ=Δ1+Δ2，因為Δ1,Δ2～N(0,σ2)，所以Δ～N(0,2σ2)。則有：

綜上所述：

4 實驗設(shè)計與結(jié)果分析

4.1 實驗環(huán)境與實驗設(shè)計

硬件環(huán)境：Intel(R) Xeon(R) CPU E5-2680 v3 @ 2.50 GHz；32 G內(nèi)存;1 T硬盤。

軟件環(huán)境：Windows 10，64位操作系統(tǒng);Python3。

實驗數(shù)據(jù)采用了斯坦福大學(xué)公開數(shù)據(jù)集SNAP Social network中的Bitcoin OTC子集(含5 881個節(jié)點35 592條邊)。

為了對RP-SVD-DP算法和RP-DP算法基于歐氏距離數(shù)據(jù)挖掘中的數(shù)據(jù)可用性進(jìn)行對比分析，本節(jié)設(shè)計了兩個實驗。第一個實驗為基于歐氏距離差的實驗，通過計算經(jīng)過RP-SVD-DP算法和RP-DP算法隱私保護(hù)后的待發(fā)布矩陣中用戶間歐氏距離和原始社交網(wǎng)絡(luò)圖中用戶之間的歐氏距離之差來衡量算法的數(shù)據(jù)可用性；第二個實驗為基于譜聚類的實驗，對經(jīng)過RP-SVD-DP算法和RP-DP算法隱私保護(hù)后的待發(fā)布矩陣進(jìn)行譜聚類，通過計算標(biāo)準(zhǔn)化互信息NMI來衡量算法的數(shù)據(jù)可用性。

4.2 歐氏距離差實驗

為了對所提出的RP-SVD-DP算法和RP-DP算法添加的噪聲量做統(tǒng)一的度量，用待發(fā)布矩陣用戶間的歐氏距離和原始社交網(wǎng)絡(luò)圖中用戶之間的歐氏距離之差來衡量算法的數(shù)據(jù)可用性，以此為評價依據(jù)衡量噪聲加入量所帶來數(shù)據(jù)可用性的變化。實驗從Bitcoin OTC數(shù)據(jù)集中隨機(jī)采樣選取了600名用戶(約為總體十分之一)，并計算用戶原始?xì)W氏距離分別經(jīng)RP-DP算法和RP-SVD-DP算法在相同隱私保護(hù)水平下擾動后的用戶間歐氏距離差。在實驗中，將原始數(shù)據(jù)集降至500維，即m=500，以及差分隱私保護(hù)水平分別設(shè)為ε=0.3,0.5.0.7.0.9,為了提高實驗結(jié)果的準(zhǔn)確性，在每個隱私預(yù)算下進(jìn)行十次實驗取平均值。實驗結(jié)果如表1所示。

表1 不同隱私保護(hù)算法用戶間歐氏距離差

分析表1數(shù)據(jù)可知，RP-DP算法和RP-SVD-DP算法的歐氏距離差不大，說明算法都滿足J-L定理，且歐氏距離差隨著隱私預(yù)算ε的變大而變小。在相同的隱私預(yù)算ε下，RP-SVD-DP算法的用戶間歐氏距離差均小于RP-DP算法，且隨著隱私預(yù)算不斷減小，RP-SVD-DP算法歐氏距離差的增長幅度也小于RP-DP算法，說明RP-SVD-DP算法的數(shù)據(jù)可用性優(yōu)于RP-DP算法。由實驗結(jié)果得出，RP-SVD-DP算法加入的噪聲量低于RP-DP算法。

4.3 譜聚類實驗

為了對所提出的RP-SVD-DP算法和RP-DP算法發(fā)布的數(shù)據(jù)在基于歐氏距離數(shù)據(jù)挖掘中數(shù)據(jù)可用性做統(tǒng)一的度量，用標(biāo)準(zhǔn)化互信息NMI衡量算法的數(shù)據(jù)可用性，以此為評價依據(jù)衡量投影數(shù)量m和隱私預(yù)算參數(shù)ε所帶來數(shù)據(jù)可用性的變化。

譜聚類實驗分為兩部分，分別改變隨機(jī)投影數(shù)量m和差分隱私保護(hù)水平ε，對原始數(shù)據(jù)集進(jìn)行聚類，通過計算不同隱私保護(hù)算法下的標(biāo)準(zhǔn)化互信息NMI來衡量發(fā)布數(shù)據(jù)集的數(shù)據(jù)可用性程度。

在改變隨機(jī)投影數(shù)量m的對比實驗中，將算法的差分隱私保護(hù)水平分別設(shè)為ε=0.5和ε=0.9。通過將原始數(shù)據(jù)集從高維數(shù)據(jù)轉(zhuǎn)化為不同維數(shù)的低維數(shù)據(jù)，對比兩算法NMI值的大小，從而分析算法數(shù)據(jù)可用性，實驗結(jié)果如表2所示。

表2 不同隨機(jī)投影數(shù)量m值，算法發(fā)布數(shù)據(jù)集譜聚類的NMI值對比

分析表2可知，RP-SVD-DP算法和RP-DP算法的NMI值均隨著隨機(jī)投影數(shù)量m的增大而增大，說明將原始高維數(shù)據(jù)的維度降的越低，所丟失掉的信息越多，導(dǎo)致算法的數(shù)據(jù)可用性越差。在相同差分隱私保護(hù)水平的情況下，RP-SVD-DP算法的NMI值均高于RP-DP算法。當(dāng)m=500，ε=0.9時，RP-SVD-DP算法的NMI值達(dá)到了0.947，而RP-DP算法的NMI值只有0.677；當(dāng)m=500，ε=0.5時，RP-SVD-DP算法和RP-DP算法的NMI值分別為0.578和0.491。由實驗結(jié)果得出，在相同的隱私預(yù)算下，將原始數(shù)據(jù)集降低至不同維度，RP-SVD-DP的數(shù)據(jù)可用性均優(yōu)于RP-DP算法。

在改變差分隱私保護(hù)水平ε的對比實驗中，將原始數(shù)據(jù)集通過隨機(jī)投影降低至500維，即m=500，將差分隱私保護(hù)水平ε設(shè)為不同值，對比兩算法的NMI值大小，分析算法數(shù)據(jù)可用性，實驗結(jié)果如表3所示。

表3 不同隱私保護(hù)算法發(fā)布數(shù)據(jù)集相對原始數(shù)據(jù)集譜聚類的NMI對比(m=500)

分析表3可知，在相同的投影維度m=500的情況下，RP-SVD-DP算法和RP-DP算法的NMI值均隨著隱私保護(hù)水平ε的增大而增大。由圖中曲線可知，當(dāng)隱私保護(hù)水平ε=0.3時，RP-SVD-DP算法的NMI值為0.513，而RP-DP算法的NMI值僅有0.357；當(dāng)隱私保護(hù)水平ε=0.7時，RP-SVD-DP算法的NMI值大于0.748，而RP-DP算法的NMI值僅有0.536。由實驗結(jié)果得出，把原始數(shù)據(jù)集降低至相同維度，在不同的隱私預(yù)算下RP-SVD-DP的數(shù)據(jù)可用性均優(yōu)于RP-DP算法。

5 結(jié)束語

為解決RP-DP算法中因噪聲過大導(dǎo)致數(shù)據(jù)可用性低的問題，提出了一種改進(jìn)的RP-SVD-DP算法。在RP-SVD-DP算法中，先對原始數(shù)據(jù)利用隨機(jī)投影進(jìn)行降維；再對降維后的數(shù)據(jù)進(jìn)行奇異值分解，對奇異值矩陣加入差分隱私噪聲；最后發(fā)布加噪后的數(shù)據(jù)。實驗表明，RP-SVD-DP算法在基于歐氏距離的實驗中加入的噪聲量更少，數(shù)據(jù)可用性優(yōu)于RP-DP算法。提出的基于奇異值分解的社交網(wǎng)絡(luò)差分隱私算法是一種非交互式隱私保護(hù)方法，無法做到數(shù)據(jù)的實時更新發(fā)布，在大數(shù)據(jù)時代，數(shù)據(jù)通常都是實時變化的，所以下一步要將該算法擴(kuò)展至交互式，盡可能地保證數(shù)據(jù)的實時性。