基于奇異值分解的含權(quán)網(wǎng)絡(luò)匿名化的安全性分析

曾勇，周靈杰，蔣忠元，劉志宏，馬建峰

（西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院，陜西 西安 710071）

1 引言

目前，大數(shù)據(jù)已成為信息技術(shù)領(lǐng)域的研究熱點(diǎn)。但是，大數(shù)據(jù)的發(fā)展依然面臨許多問題，安全和隱私保護(hù)是目前人們公認(rèn)的關(guān)鍵問題之一[1]。為了保護(hù)用戶的隱私信息，數(shù)據(jù)擁有者一般會在發(fā)布數(shù)據(jù)之前對數(shù)據(jù)進(jìn)行匿名化處理。數(shù)據(jù)發(fā)布匿名保護(hù)是實(shí)現(xiàn)數(shù)據(jù)隱私保護(hù)的核心技術(shù)和基本手段。數(shù)據(jù)的隱私保護(hù)要保證數(shù)據(jù)可用性和安全性之間的平衡。

社交網(wǎng)絡(luò)的隱私保護(hù)不同于關(guān)系數(shù)據(jù)的隱私保護(hù)，它需要綜合考慮網(wǎng)絡(luò)的圖結(jié)構(gòu)、節(jié)點(diǎn)間的關(guān)系強(qiáng)度（權(quán)值）以及節(jié)點(diǎn)的重要性等信息。K-匿名[2]是關(guān)系數(shù)據(jù)隱私保護(hù)的經(jīng)典方法之一，文獻(xiàn)[3,4]將其推廣到社交網(wǎng)絡(luò)的數(shù)據(jù)隱私保護(hù)，分別提出了節(jié)點(diǎn)K-匿名和子圖K-匿名，它們保證了對目標(biāo)節(jié)點(diǎn)或子圖再識別時，至少有K個候選者，從而使目標(biāo)隱私泄露的概率小于。數(shù)據(jù)擾動[5～8]也是社交網(wǎng)絡(luò)匿名化處理的一類常用方法，它主要對社交網(wǎng)絡(luò)進(jìn)行隨機(jī)修改，使攻擊者不能準(zhǔn)確地推測出原始的真實(shí)數(shù)據(jù)，例如，文獻(xiàn)[6]在圖中加入高斯噪聲，對網(wǎng)絡(luò)中邊的權(quán)值進(jìn)行擾動，在指定節(jié)點(diǎn)之間最短路徑及其序列保持不變的情況下，保證其最短路徑長度的隱私性。但是這些方法都存在一定的不足，例如，文獻(xiàn)[9]明確指出K-匿名方法存在信息損失問題，最重要的一點(diǎn)是它們往往對網(wǎng)絡(luò)圖結(jié)構(gòu)破壞比較大，使擾動后圖數(shù)據(jù)的可用性較低。

為了保護(hù)圖數(shù)據(jù)的可用性，研究人員引入人工智能、圖譜分析等理論，提出了基于降秩的方法，這些方法在圖數(shù)據(jù)的譜空間可用性上遠(yuǎn)遠(yuǎn)優(yōu)于上述方法。基于特征值分解方法[10]和基于奇異值分解（SVD,singular value decomposition）方法[11]是其中的2類經(jīng)典方法，特征值與奇異值也稱為圖的譜。這2類方法通過舍棄范數(shù)小的譜及其對應(yīng)的譜向量來保證圖數(shù)據(jù)的隱私與譜空間主緯度上的數(shù)據(jù)可用性。文獻(xiàn)[11]中給出了經(jīng)典的奇異值分解擾動策略和稀疏化的奇異值分解擾動策略，并表明了此類方法能較好地保證圖數(shù)據(jù)的可用性。Wu等[12]提出用特征值（奇異值）分解對擾動網(wǎng)絡(luò)進(jìn)行處理來提高數(shù)據(jù)的可用性。文獻(xiàn)[13,14]將降秩方法引入網(wǎng)絡(luò)的鏈路預(yù)測中，提出了一種基于低秩矩陣的全局信息預(yù)測算法。

基于降秩的方法雖能較好地保護(hù)圖數(shù)據(jù)的可用性，但它并不總是安全的，仍然存在數(shù)據(jù)隱私泄露的風(fēng)險。由于在基于降秩的方法中涉及舍棄譜，那么舍棄譜的數(shù)量是這類方法的關(guān)鍵。目前，在譜分析理論及其他相關(guān)理論中對舍棄譜的數(shù)量并沒有公認(rèn)的結(jié)論。雖然在原網(wǎng)絡(luò)中舍棄譜越少，擾動網(wǎng)絡(luò)的數(shù)據(jù)可用性越好，但在文獻(xiàn)[10]對無權(quán)網(wǎng)絡(luò)的特征值分解測試中發(fā)現(xiàn)，當(dāng)舍棄譜的數(shù)量較少時，可以從擾動網(wǎng)絡(luò)中恢復(fù)原網(wǎng)絡(luò)。文獻(xiàn)[15]采用文獻(xiàn)[10]中所提的方法對城市電路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行了測試，進(jìn)一步表明了基于降秩的方法并不總是安全的，且其安全性與舍棄譜的數(shù)量有關(guān)。雖然文獻(xiàn)[12]提出了用特征值（奇異值）相似性來決定所舍棄譜的數(shù)量，但這樣只關(guān)注了數(shù)據(jù)的可用性而忽略了安全性，并且文中實(shí)驗(yàn)也表明了此方法會引入新的安全問題。文獻(xiàn)[13,14]中給出了舍棄譜的數(shù)量的衡量方法，并且實(shí)驗(yàn)也表明該方法具有較好的鏈路預(yù)測效果，但其主要針對邊缺失的預(yù)測問題及網(wǎng)絡(luò)的動態(tài)變化問題所提出。此外，目前對基于降秩的社交網(wǎng)絡(luò)隱私保護(hù)方法的安全性分析主要針對無權(quán)網(wǎng)絡(luò)，而在含權(quán)網(wǎng)絡(luò)中的安全性分析很少。

針對在含權(quán)社交網(wǎng)絡(luò)中基于降秩的隱私保護(hù)方法的安全性問題，本文對其進(jìn)行了分析與測試。目前，降秩的隱私保護(hù)方法主要基于奇異值分解和特征值分解，所以本文選擇了具有代表性的基于奇異值分解的方法進(jìn)行分析，并主要分析了奇異值分解擾動和稀疏化的奇異值分解擾動用于加權(quán)社交網(wǎng)絡(luò)數(shù)據(jù)隱私保護(hù)時抵御重構(gòu)攻擊的能力。為了限定舍棄譜的數(shù)量，本文提出了-容忍性，它表示網(wǎng)絡(luò)中冗余譜所占的比例。其中，ε為網(wǎng)絡(luò)的可重構(gòu)系數(shù)，表示在網(wǎng)絡(luò)可被重構(gòu)的情況下，可被舍棄譜的最大數(shù)量，為網(wǎng)絡(luò)的可重構(gòu)比例系數(shù)。當(dāng)算法中舍棄譜的數(shù)量小于或等于ε時，網(wǎng)絡(luò)可被重構(gòu)，隱私數(shù)據(jù)將被泄露。本文指出目前的譜分析理論能給出的ε上界過于保守，并進(jìn)行了大量實(shí)驗(yàn)來獲取其數(shù)值解。實(shí)驗(yàn)發(fā)現(xiàn)這些網(wǎng)絡(luò)對丟失的譜具有不同的容忍性，且ε、與網(wǎng)絡(luò)參數(shù)之間存在一定的關(guān)系。同時測試了基于 SVD的雙重擾動策略，用于加權(quán)社交網(wǎng)絡(luò)隱私保護(hù)時的安全性。實(shí)驗(yàn)結(jié)果表明，基于 SVD的擾動策略對信息丟失具有一定的容忍性，直接用于社交網(wǎng)絡(luò)的隱私保護(hù)存在被重構(gòu)的風(fēng)險，即使進(jìn)行了雙重擾動，也必須注意舍棄譜的數(shù)量。

2 基于奇異值分解的擾動策略

本節(jié)主要介紹了在加權(quán)社交網(wǎng)絡(luò)中2種典型的基于奇異值分解的擾動策略。

2.1 奇異值分解擾動

文獻(xiàn)[11]中作者將人工智能領(lǐng)域的奇異值分解用作數(shù)據(jù)擾動策略，來保護(hù)數(shù)據(jù)的隱私性。

一個含有N個節(jié)點(diǎn)、M條邊的無向加權(quán)網(wǎng)絡(luò)可以表示為G=(V,E)，其中，V代表節(jié)點(diǎn)的集合，E代表邊的集合，頂點(diǎn)數(shù)N=|V|，邊數(shù)M=|E|。若在邊集E中存在元素eij，表示節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間存在的邊。在加權(quán)網(wǎng)絡(luò)G中每一條邊eij都有一個權(quán)重wij=wji與之相對應(yīng)。假設(shè)G無自環(huán)路且無多重邊，則G可由其鄰接矩陣A∈RN×N表示，其中

對于一個網(wǎng)絡(luò)G的鄰接矩陣A∈RN×N，必然存在一個完全奇異值分解

其中，U、V均為N×N階的酉矩陣，Σ=diag[σ1,σ2,…,σN?1,σN]為對角矩陣，σi為A的奇異值。注：Σ 的對角元素非升序排列，即σ1≥σ2≥…≥σN?1≥σN≥0。

SVD擾動主要通過舍棄其部分較小的奇異值及對應(yīng)的譜向量來實(shí)現(xiàn)對數(shù)據(jù)的擾動。令對角矩陣 Σj為舍棄j(j≥0)個較小的奇異值后的對角矩陣，則有

則SVD擾動后的鄰接矩陣為

2.2 稀疏化的奇異值分解擾動

為了加強(qiáng)對數(shù)據(jù)的保護(hù)，文獻(xiàn)[11]在SVD擾動的基礎(chǔ)上對U、V矩陣做了進(jìn)一步處理，并將這種對數(shù)據(jù)進(jìn)行雙重擾動的方法稱為稀疏化奇異值擾動（SSVD，sparsified singular value decomposition）。SSVD的具體過程如下。

對鄰接矩陣A進(jìn)行奇異值擾動，得Aj。然后令

其中，α是U、V矩陣中數(shù)值的絕對值的下界。則擾動后的矩陣為

α是對矩陣中元素大小的限定，在不同類型的網(wǎng)絡(luò)中，U、V矩陣的值分布差異可能較大，從而導(dǎo)致在α相同的條件下，在U、V矩陣中舍棄的值的比例無法評估。為了更好地適應(yīng)不同類型的網(wǎng)絡(luò)，使U、V中舍棄的值的數(shù)量更可控，本文定義β為U、V中刪除的值的比例，即

其中，nα為U或V矩陣中舍棄值的個數(shù)。

3 重構(gòu)方法及-容忍性

本節(jié)主要對無權(quán)網(wǎng)絡(luò)特征值分解的重構(gòu)方法[10]進(jìn)行推廣，提出在含正整數(shù)權(quán)重網(wǎng)絡(luò)中的重構(gòu)方法。對于含任意權(quán)重的社交網(wǎng)絡(luò)，提出非精確重構(gòu)的概念以及2種重構(gòu)方法。為了分析降秩方法的安全性，提出了-容忍性，它反映了隱私數(shù)據(jù)何時會被泄露。同時，在3.4節(jié)對重構(gòu)方法以及ε進(jìn)行了理論上的分析。

3.1 重構(gòu)的描述

在SVD擾動中，顯然，j=0時Aj=A，j≠0時Aj≠A。當(dāng)j≠0時，Aj中的值分布服從一定的規(guī)律。圖1給出了在ER網(wǎng)絡(luò)（N=100，p=0.5）中j=0、j=10、j=20以及j=30時Aj中值的分布情況（在其他模型網(wǎng)絡(luò)中具有相同的結(jié)果），其中，A中的權(quán)值服從[1,5]之間的均勻分布。由圖1可以看出，Aj中的值在[0,5]中各整數(shù)值的附近分布。

當(dāng)j≠0時，Aj中的值含有非整數(shù)以及負(fù)值，本文試圖用Aj重構(gòu)A，以獲得原網(wǎng)絡(luò)的全部信息。令重構(gòu)后的矩陣為，假設(shè)攻擊者無任何背景知識，對于含有正整數(shù)權(quán)值的網(wǎng)絡(luò)，定義為

假設(shè)攻擊者已知網(wǎng)絡(luò)權(quán)重的分布規(guī)律，為了能在j取值更大的情況下重構(gòu)出網(wǎng)絡(luò)，可以根據(jù)網(wǎng)絡(luò)中值的分布情況對重構(gòu)操作進(jìn)行調(diào)整。例如，已知網(wǎng)絡(luò)中的權(quán)值僅為偶數(shù)，為取得更佳的還原效果，則重構(gòu)操作可以調(diào)整為

3.2 非精確重構(gòu)

3.1節(jié)所提到的重構(gòu)方法都是對含整數(shù)權(quán)重網(wǎng)絡(luò)的精確重構(gòu)，而對于含有任意數(shù)權(quán)重的網(wǎng)絡(luò)來說，權(quán)值可能不全為整數(shù)，可能含有多位小數(shù)，這時若想精確地重構(gòu)出原來的網(wǎng)絡(luò)，代價是非常大的，有時甚至是計(jì)算不可行的?？紤]到對某些值允許一定誤差的存在，本節(jié)給出了非精確重構(gòu)方法。

對于一個加權(quán)網(wǎng)絡(luò)G，其鄰接矩陣為A，若它的重構(gòu)網(wǎng)絡(luò)與它本身之間滿足

則稱其中，||A||F表示矩陣A的F（Frobenius）范數(shù)[16]，定義為非精確重構(gòu)出了A，記為

式(11)左邊部分稱為網(wǎng)絡(luò)之間的值差[11]，為重構(gòu)噪聲矩陣，它們表示?相較A失真的程度。0≤θ≤1為用戶閾值，用來限定非精確重構(gòu)的程度。θ越小，重構(gòu)出A，即與A就越相似，當(dāng)θ=0時，

本文提出了2種非精確重構(gòu)方法。假設(shè)原鄰接矩陣A及其擾動鄰接矩陣Aj，且A中權(quán)值最多含有nmax位小數(shù)，則這2種方法分別介紹如下。

方法 1 首先將原網(wǎng)絡(luò)中權(quán)值整數(shù)化：Am=m×A，其中，m=10nmax（注：在小數(shù)位數(shù)較多的情況下，可以選擇犧牲某些位，從而避免m太大引起的權(quán)值過大、處理困難等問題）。然后利用第 2節(jié)的方法對Am進(jìn)行SVD擾動和重構(gòu)。

方法 2 對重構(gòu)方法進(jìn)行調(diào)整以適應(yīng)對權(quán)值為小數(shù)的匹配。重構(gòu)方法調(diào)整為

2種重構(gòu)方法本質(zhì)上是相同的，但由于2種方法在對原網(wǎng)絡(luò)的處理上要求不同，就導(dǎo)致方法1必須準(zhǔn)確地知道原網(wǎng)絡(luò)的數(shù)據(jù)，而方法2根據(jù)原網(wǎng)絡(luò)的特性來直接調(diào)整重構(gòu)方法，所以只需要了解原網(wǎng)絡(luò)的部分特性。方法1實(shí)質(zhì)上是權(quán)重全部為整數(shù)時的非精確重構(gòu)，所以對2種方法的測試可以說明含任意權(quán)值的網(wǎng)絡(luò)的非精確可重構(gòu)性。

3.3 -容忍性及可重構(gòu)系數(shù)

當(dāng)j在一定條件下對擾動網(wǎng)絡(luò)進(jìn)行重構(gòu)時，可以重構(gòu)出原鄰接矩陣A，即為了衡量網(wǎng)絡(luò)對信息丟失的容忍程度，本文定義了-容忍性。

定義1-容忍性。設(shè)網(wǎng)絡(luò)G及其鄰接矩陣A，其規(guī)模為N，A的擾動矩陣為Aj，重構(gòu)矩陣為令ε為

稱ε為G的可重構(gòu)系數(shù)，稱為G的可重構(gòu)比例系數(shù)。

在刪除網(wǎng)絡(luò)中ε個譜及對應(yīng)譜向量時，網(wǎng)絡(luò)依然可以被重構(gòu)，即-容忍性反映了網(wǎng)絡(luò)中無用譜（或稱冗余譜）所占的比例。一個網(wǎng)絡(luò)中ε越大，基于降秩方法中需要舍棄的譜的數(shù)量就越大（保證網(wǎng)絡(luò)不被重構(gòu)的情況下），則在相同擾動條件下，網(wǎng)絡(luò)被重構(gòu)的概率越大。

3.4 ε取值的分析

對于鄰接矩陣A的奇異值分解可以表示為

對于矩陣A中的任意一個元素aij可以表示為

那么，當(dāng)滿足

可以還原出原數(shù)據(jù)為

由此可見重構(gòu)的條件為式(17)，即

考慮到社交網(wǎng)絡(luò)的無向特性，則A為實(shí)對稱矩陣。設(shè)λi為A的特征值，且|λ1|≥|λ2|≥…≥|λn|，由奇異值分解的性質(zhì)[17,18]可得結(jié)論1。

結(jié)論 1σi=|λi|，vi=sign(λi)ui，若λi=0，則sign(λi)=1。

由此，式(19)左邊的值可以表示為

又因?yàn)閁為酉矩陣[17]，那么它的n個行向量是兩兩正交的單位向量。由此可知||uiuiT||2≤1，繼而可得|(uiuiT)ij|≤1，所以利用文獻(xiàn)[10]求解可重構(gòu)系數(shù)的方法，最終可得舍棄奇異值的數(shù)量的一個上界為

式(18)中的界是比較保守的，因?yàn)?uiuiT)ij可能存在負(fù)值。同時考慮到大多情況下網(wǎng)絡(luò)將近一半的特征值為負(fù)值，由結(jié)論1可知，(uiuiT)ij為負(fù)值的可能性比較大，這就導(dǎo)致這個界是大于實(shí)際值的，而其下確界在矩陣譜分析理論中還沒有公認(rèn)的結(jié)論[19]，導(dǎo)致可重構(gòu)系數(shù)的計(jì)算誤差過大。換句話說，降秩方法中用此理論值作為舍棄的譜數(shù)量的依據(jù)可以保證網(wǎng)絡(luò)不被重構(gòu)，但此值不是最小值。接下來，本文通過實(shí)驗(yàn)來計(jì)算可重構(gòu)系數(shù)的精確值。

4 網(wǎng)絡(luò)的可重構(gòu)系數(shù)

-容忍性反映了算法對網(wǎng)絡(luò)中譜丟失的容忍程度，ε體現(xiàn)了算法中最少需要舍棄的譜的數(shù)量。ε、在一定程度上代表了網(wǎng)絡(luò)的可重構(gòu)性和一個網(wǎng)絡(luò)經(jīng)過SVD擾動后可被重構(gòu)的概率。

由3.4節(jié)分析可知，ε理論計(jì)算誤差較大，故本文通過實(shí)驗(yàn)來獲取其數(shù)值解。4.1節(jié)主要測試了不同網(wǎng)絡(luò)中的ε以及它與網(wǎng)絡(luò)參數(shù)之間的關(guān)系。4.2節(jié)則針對本文提出的非精確重構(gòu)方法，進(jìn)行了測試與分析。同時，針對基于奇異值分解的雙重擾動方法的安全性，4.3節(jié)測試了在SSVD擾動下網(wǎng)絡(luò)的可重構(gòu)性和非精確可重構(gòu)性。為了便于分析，設(shè)本節(jié)測試的所有網(wǎng)絡(luò)的權(quán)值均為服從[wmin,wmax]上的均勻分布，那么對含整數(shù)權(quán)重網(wǎng)絡(luò)的重構(gòu)采用式(9)所描述的方法。

本文所有的實(shí)驗(yàn)是在 Windows10專業(yè)版上的Matlab 2015B中進(jìn)行的，電腦的配置為 Intel(R)Core? i5-7500 CPU @3.40 GHz。

4.1 不同網(wǎng)絡(luò)模型的可重構(gòu)系數(shù)

4.1.1 ER網(wǎng)絡(luò)

ER（Erd?s-Rényi）網(wǎng)絡(luò)[20]用隨機(jī)圖的方式來描述網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，具有易于描述和分析的優(yōu)點(diǎn)，是復(fù)雜網(wǎng)絡(luò)研究的基本理論之一。本文生成的 ER無向加權(quán)網(wǎng)絡(luò)采用G(N,p)模型，記為Gp(N,W)，其中，N為網(wǎng)絡(luò)的規(guī)模。在此類網(wǎng)絡(luò)中所有節(jié)點(diǎn)對之間以概率p相連接，且被隨機(jī)賦予一個權(quán)重w。

首先，本文對ER網(wǎng)絡(luò)中ε的分布情況進(jìn)行了實(shí)驗(yàn)分析。實(shí)驗(yàn)所選取的網(wǎng)絡(luò)規(guī)模為N=200，權(quán)值分布參數(shù)均為wmin=1、wmax=5，p分別取0.1、0.3、0.5、0.7以及0.9。本文對每種類型的網(wǎng)絡(luò)取2 000個進(jìn)行重構(gòu)系數(shù)的計(jì)算然后求ε的平均值。圖2顯示了p取不同值時ε的分布情況，其中離散點(diǎn)是真實(shí)數(shù)據(jù)，曲線是用高斯分布擬合的結(jié)果，由此可以得到結(jié)論2。

圖2 ER網(wǎng)絡(luò)中可重構(gòu)系數(shù)的分布情況

結(jié)論2 ER網(wǎng)絡(luò)中ε服從高斯分布。

由結(jié)論 2可知，對于相同類型的網(wǎng)絡(luò)，其ε值存在差異，那么用其均值εm代表一種網(wǎng)絡(luò)類型的重構(gòu)系數(shù)是否合適，本文將對其進(jìn)一步分析和測試。圖3為G0.5(N,W)中ε均值與方差的關(guān)系，其中網(wǎng)絡(luò)參數(shù)為wmin=1、wmax=5，N從50到1 000，每隔50測試1 000組數(shù)據(jù)計(jì)算均值與方差。從圖3可以看出，ε的方差相較其均值εm很小，且在其他模型網(wǎng)絡(luò)中也存在同樣的規(guī)律，由此可以得到結(jié)論3。

結(jié)論 3 不能用單次實(shí)驗(yàn)結(jié)果代表網(wǎng)絡(luò)的可重構(gòu)系數(shù)，可以用多次實(shí)驗(yàn)的均值εm表示。

圖3 可重構(gòu)系數(shù)均值與方差的分布

接下來，本文測試了在ER網(wǎng)絡(luò)中網(wǎng)絡(luò)參數(shù)對εm的影響。首先，利用 2種類型的網(wǎng)絡(luò)G0.2(N,W)與G0.5(N,W)對εm與N的關(guān)系進(jìn)行了實(shí)驗(yàn)分析，其中權(quán)值服從[1,3]與[1,5]上的均勻分布。對于每種類型的網(wǎng)絡(luò)，N取50到1 000，其中N每增加50取200個網(wǎng)絡(luò)進(jìn)行測試。圖4顯示了εm隨N變化的情況，其中實(shí)線是擬合的結(jié)果。顯然，εm與N呈線性關(guān)系，即-容忍性與網(wǎng)絡(luò)規(guī)模無關(guān)。同時，網(wǎng)絡(luò)的稀疏程度對有一定的影響，但相對較小。而網(wǎng)絡(luò)中權(quán)值的分布卻對其有較明顯的影響。表1中展示了圖4中的擬合結(jié)果：ε可高達(dá) 25%N，說明舍棄 25%的奇異值時，網(wǎng)絡(luò)依然可能被重構(gòu)。本文繼續(xù)分析了權(quán)值分布參數(shù)（這里指wmax）對的影響。圖5是在G0.5(200,W)中測試的結(jié)果，其中wmin=1，wmax取1到20，每隔1取1 000個網(wǎng)絡(luò)進(jìn)行測試。圖5中離散點(diǎn)是真實(shí)數(shù)據(jù)，曲線是用冪律函數(shù)擬合的結(jié)果。由圖5可知，wmax與之間存在冪律分布，且wmax越小，越大。

圖4 ER網(wǎng)絡(luò)中可重構(gòu)系數(shù)與網(wǎng)絡(luò)規(guī)模的關(guān)系

表1 ER網(wǎng)絡(luò)的可重構(gòu)比例系數(shù)

圖5 ER網(wǎng)絡(luò)中與權(quán)值分布的關(guān)系

圖5中，當(dāng)wmax為1時，網(wǎng)絡(luò)可視為無權(quán)網(wǎng)絡(luò)，此時，最大，為45%左右，這與文獻(xiàn)[10]在無權(quán)網(wǎng)絡(luò)中的結(jié)論基本保持一致，從而證明了本文所測數(shù)據(jù)的可用性。同時也表明了在無權(quán)網(wǎng)絡(luò)中 SVD擾動方法的-容忍性大，被重構(gòu)的風(fēng)險大。

4.1.2 BA網(wǎng)絡(luò)

BA（Barabasi-Albert）網(wǎng)絡(luò)[21]是一種隨機(jī)無標(biāo)度網(wǎng)絡(luò)，它的度分布服從冪律分布。本文用于分析的無標(biāo)度網(wǎng)絡(luò)采用 BA網(wǎng)絡(luò)模型生成，記為G(m0,m)(N,W)，其中，m0代表初始節(jié)點(diǎn)的數(shù)量，m表示每增加一個節(jié)點(diǎn)所增加的邊數(shù)。

本文首先利用 3種 BA網(wǎng)絡(luò)：G(4,4)(N,W)、G(8,8)(N,W)、G(12,12)(N,W)，測試了εm與N的關(guān)系，其中，網(wǎng)絡(luò)的權(quán)值分布參數(shù)為wmin=1、wmax=5，N從600到1 500，每隔100取200個網(wǎng)絡(luò)進(jìn)行測試。圖6為測試結(jié)果，圖6中的擬合結(jié)果如表2所示。由實(shí)驗(yàn)結(jié)果可知，εm與N之間存在線性關(guān)系，而網(wǎng)絡(luò)參數(shù)m0、m對影響較小。

表2 BA網(wǎng)絡(luò)的可重構(gòu)比例系數(shù)

圖6 BA網(wǎng)絡(luò)中可重構(gòu)系數(shù)與網(wǎng)絡(luò)規(guī)模的關(guān)系

同時，利用這3種網(wǎng)絡(luò)測試了權(quán)值分布對可重構(gòu)系數(shù)的影響。圖7給出了wmax與的關(guān)系，其中，N=600，wmin固定為1，wmax取1到20，每隔1取200個網(wǎng)絡(luò)進(jìn)行測試。由圖7可知，wmax與之間同樣存在冪律關(guān)系，且wmax越小，越大。當(dāng)wmax=1，鄰接矩陣A可視為無權(quán)網(wǎng)絡(luò)，最大為50%，網(wǎng)絡(luò)被重構(gòu)的風(fēng)險最大。

圖7 BA網(wǎng)絡(luò)中與權(quán)值分布的關(guān)系

4.1.3 小世界網(wǎng)絡(luò)

小世界網(wǎng)絡(luò)[22]是介于隨機(jī)網(wǎng)絡(luò)和規(guī)則網(wǎng)絡(luò)之間的網(wǎng)絡(luò)。WS（Watts and Strogatz）模型首先構(gòu)造一個度為2×k的環(huán)形規(guī)則網(wǎng)絡(luò)，然后再以概率p將邊打亂重連。將 WS模型生成的網(wǎng)絡(luò)記為G(k,p)(N,W)。

首先，對εm與N之間關(guān)系進(jìn)行了測試。圖8顯示了當(dāng)k為2、5，p為0.2、0.4、0.6時WS網(wǎng)絡(luò)中εm與N的關(guān)系。其中，網(wǎng)絡(luò)的權(quán)值分布參數(shù)均為wmin=1、wmax=5，N取50到500，每隔50取1 000個網(wǎng)絡(luò)進(jìn)行測試。表3給出了圖8中的擬合值。實(shí)驗(yàn)發(fā)現(xiàn)，在不同的網(wǎng)絡(luò)參數(shù)下，εm與N均存在線性關(guān)系，并且的取值取決于k和p的取值。

圖8 WS網(wǎng)絡(luò)中可重構(gòu)系數(shù)與網(wǎng)絡(luò)規(guī)模的關(guān)系

表3 WS網(wǎng)絡(luò)的可重構(gòu)比例系數(shù)

對于網(wǎng)絡(luò)中權(quán)值分布參數(shù)wmax對εm的影響，本文在wmin=1，N=200，k=2、5，p=0.2、0.4時進(jìn)行了測試分析，圖9為實(shí)驗(yàn)結(jié)果。從圖9可以看出，與wmax之間依然存在冪律關(guān)系，且wmax越小就越大。

4.1.4 實(shí)際網(wǎng)絡(luò)

為了測試實(shí)際網(wǎng)絡(luò)的-容忍性，本文對

圖9 WS網(wǎng)絡(luò)中與權(quán)值分布的關(guān)系

4個真實(shí)數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)，4個數(shù)據(jù)集分別為Facebook[23]、US Airlines[23]、Jazz[24]、Metabolic[23]。它們均為無向網(wǎng)絡(luò)，包含的節(jié)點(diǎn)數(shù)分別為 4 039、332、198、453。為了測試權(quán)值不同時網(wǎng)絡(luò)的容忍性，本文為網(wǎng)絡(luò)中的每條邊隨機(jī)賦予一個服從均勻分布的正整數(shù)權(quán)值，并測試了wmin固定為1時wmax與εm的關(guān)系，圖10為實(shí)驗(yàn)結(jié)果。從圖10可以看出，實(shí)際網(wǎng)絡(luò)對舍棄的維度信息具有不同程度的容忍度，在某些情況下舍棄45%的維度信息仍不能保證數(shù)據(jù)的安全性。

圖10 實(shí)際網(wǎng)絡(luò)中權(quán)值分布的關(guān)系

本節(jié)主要測試了不同網(wǎng)絡(luò)的-容忍性。通過分析實(shí)驗(yàn)結(jié)果，可以得到以下結(jié)論。

結(jié)論4 BA、ER及WS網(wǎng)絡(luò)中，可重構(gòu)系數(shù)與網(wǎng)絡(luò)規(guī)模存在線性關(guān)系，可重構(gòu)比例系數(shù)與網(wǎng)絡(luò)規(guī)模無關(guān)，即-容忍性與網(wǎng)絡(luò)規(guī)模無關(guān)。

結(jié)論5 BA、ER及 WS網(wǎng)絡(luò)中，當(dāng)網(wǎng)絡(luò)中權(quán)值為整數(shù)且服從[1,wmax]上的均勻分布時，wmax與之間存在冪律分布，且wmax越小，越大。

通過對各種網(wǎng)絡(luò)-容忍性的測試發(fā)現(xiàn)，SVD擾動對網(wǎng)絡(luò)維度的舍棄具有一定的容忍性，甚至在BA網(wǎng)絡(luò)中可高達(dá)50%，由此可得結(jié)論6。

結(jié)論6 SVD擾動方法用于含整數(shù)權(quán)重的社交網(wǎng)絡(luò)的數(shù)據(jù)隱私保護(hù)并不總是安全的，存在被重構(gòu)的危險。

4.2 非精確重構(gòu)中的可重構(gòu)系數(shù)

為測試含任意權(quán)重網(wǎng)絡(luò)的-容忍性，本文利用ER網(wǎng)絡(luò)對2種非精確重構(gòu)方法中的可重構(gòu)系數(shù)進(jìn)行了測試。首先測試了εm與網(wǎng)絡(luò)規(guī)模N的關(guān)系，圖11為實(shí)驗(yàn)結(jié)果。

圖11 非精確重構(gòu)中可重構(gòu)系數(shù)與網(wǎng)絡(luò)規(guī)模的關(guān)系

由圖11可以看出，εm與N同樣存在線性關(guān)系，同時也可以看出nmax對重構(gòu)系數(shù)基本沒有影響。表4給出了可重構(gòu)比例系數(shù)a的擬合值，對比方法1與方法2可以發(fā)現(xiàn)，它們的結(jié)果是保持一致的。

表4 非精確可重構(gòu)比例系數(shù)

圖12為利用ER網(wǎng)絡(luò)Gp(200,W)測試與wmax關(guān)系的結(jié)果，可以發(fā)現(xiàn)在非精確重構(gòu)中權(quán)值的分布對重構(gòu)系數(shù)不再有明顯的影響。這是由于非精確重構(gòu)的定義相對于原網(wǎng)絡(luò)的值而言并不是絕對的，在ε取值相同的條件下，網(wǎng)絡(luò)中權(quán)值越大，重構(gòu)噪聲矩陣中的值就越大。最后利用 ER網(wǎng)絡(luò)Gp(200,W)測試了θ與重構(gòu)比例系數(shù)的關(guān)系。

圖12 2種非精確重構(gòu)方法下可重構(gòu)比例系數(shù)與權(quán)值分布的關(guān)系

圖13是2種非精確重構(gòu)方法下可重構(gòu)比例系數(shù)與θ的關(guān)系，其中曲線是用冪律分布擬合的結(jié)果。由此可看出θ與服從冪律分布。

由4.1節(jié)的實(shí)驗(yàn)可知，在各模型網(wǎng)絡(luò)及實(shí)際網(wǎng)絡(luò)中，ε與N以及與wmax之間具有相同的規(guī)律。本節(jié)選取ER網(wǎng)絡(luò)為代表，由實(shí)驗(yàn)結(jié)果可得以下結(jié)論。

結(jié)論7 在非精確重構(gòu)中，BA、ER及WS網(wǎng)絡(luò)中可重構(gòu)系數(shù)與網(wǎng)絡(luò)規(guī)模之間存在線性關(guān)系；可重構(gòu)比例系數(shù)不受網(wǎng)絡(luò)權(quán)值分布的影響；非精確重構(gòu)閾值與可重構(gòu)比例之間存在冪律關(guān)系，且閾值越大，可重構(gòu)比例越大。

結(jié)論8 SVD擾動用于任意權(quán)值的社交網(wǎng)絡(luò)隱私保護(hù)時，存在被非精確重構(gòu)的危險。

圖13 2種非精確重構(gòu)方法下可重構(gòu)比例系數(shù)與θ的關(guān)系

4.3 雙重擾動時網(wǎng)絡(luò)的可重構(gòu)系數(shù)

對鄰接矩陣A進(jìn)行稀疏化奇異值擾動后，在j≤ε的條件下依然可以利用上面提到的方法重構(gòu)或非精確重構(gòu)A，并且εm與N依然存在線性關(guān)系。由4.1節(jié)可知，在各模型網(wǎng)絡(luò)中ε與N之間存在相同的關(guān)系，所以本文利用具有代表性的ER網(wǎng)絡(luò)G0.5(N,W)測試了在不同β值下εm與N的關(guān)系，其中，N取50到800，每隔50取100個網(wǎng)絡(luò)進(jìn)行測試。圖14是在權(quán)重全部為整數(shù)的情況下對A重構(gòu)的結(jié)果，其中網(wǎng)絡(luò)的權(quán)值服從[1,5]上的均勻分布。圖15是在權(quán)重為任意值時對A非精確重構(gòu)的結(jié)果，其中，nmax=2，且網(wǎng)絡(luò)的權(quán)值均服從(0,5)上的均勻分布，非精確重構(gòu)閾值θ=0.1。從圖14和圖15可以看出，當(dāng)β高達(dá)16%時，Aj將不再能重構(gòu)鄰接矩陣A；當(dāng)β高達(dá)30%時，將不再能非精確重構(gòu)鄰接矩陣A。而當(dāng)β=4%左右時，Aj重構(gòu)鄰接矩陣A基本不受影響；當(dāng)β=6%左右時，非精確重構(gòu)鄰接矩陣A基本不受影響，由此可得結(jié)論9。

結(jié)論 9 SSVD用于加權(quán)社交網(wǎng)絡(luò)數(shù)據(jù)的隱私保護(hù)時，存在被重構(gòu)和被非精確重構(gòu)的危險。

本節(jié)主要在 SVD擾動下測試了不同含權(quán)網(wǎng)絡(luò)的可重構(gòu)系數(shù)，發(fā)現(xiàn)了可重構(gòu)系數(shù)、可重構(gòu)比例系數(shù)與網(wǎng)絡(luò)參數(shù)之間存在的關(guān)系。針對含任意權(quán)重網(wǎng)絡(luò)的可重構(gòu)系數(shù)，在 ER網(wǎng)絡(luò)中采用非精確重構(gòu)方法進(jìn)行測試，發(fā)現(xiàn)了可重構(gòu)系數(shù)、可重構(gòu)比例系數(shù)與網(wǎng)絡(luò)參數(shù)之間存在的關(guān)系。最后，對基于奇異值分解的雙重擾動策略，分別采用重構(gòu)和非精確重構(gòu)測試了其可重構(gòu)系數(shù)。實(shí)驗(yàn)結(jié)果表明，即使進(jìn)行了雙重擾動，網(wǎng)絡(luò)依然會表現(xiàn)出不同程度的-容忍性，從而說明了基于奇異值分解的擾動策略用于加權(quán)社交網(wǎng)絡(luò)的隱私保護(hù)時具有被重構(gòu)的危險。

圖14 SSVD中β對網(wǎng)絡(luò)重構(gòu)的影響

圖15 SSVD中β對非精確重構(gòu)的影響

5 結(jié)束語

本文測試并分析 SVD擾動方法用于加權(quán)社交網(wǎng)絡(luò)的安全性，提出了網(wǎng)絡(luò)的-容忍性，ε越大，網(wǎng)絡(luò)被重構(gòu)的概率越大，越不安全，并分別用理論和實(shí)驗(yàn)對網(wǎng)絡(luò)的-容忍性進(jìn)行了分析，同時實(shí)驗(yàn)測試了網(wǎng)絡(luò)非精確重構(gòu)時的-容忍性和在 SSVD擾動下的-容忍性。實(shí)驗(yàn)發(fā)現(xiàn)，BA、ER及 WS網(wǎng)絡(luò)中，-容忍性與網(wǎng)絡(luò)規(guī)模無關(guān)，同時表明了SVD擾動對含權(quán)社交網(wǎng)絡(luò)信息的丟失具有較大的容忍性，即使在雙重擾動中舍棄少于5%～50%的維度，依然存在被重構(gòu)和被非精確重構(gòu)的危險。

本文的分析與測試建立在權(quán)值服從均勻分布的基礎(chǔ)之上，下一步的工作將考慮非均勻分布權(quán)值下可重構(gòu)系數(shù)、可重構(gòu)比例系數(shù)與網(wǎng)絡(luò)結(jié)構(gòu)之間的關(guān)系。同時，在重構(gòu)方法中考慮攻擊者背景知識的影響也值得進(jìn)一步研究。

[1] 馮登國, 張敏, 李昊. 大數(shù)據(jù)安全與隱私保護(hù)[J]. 計(jì)算機(jī)學(xué)報,2014, 37(1)∶ 246-258.FENG D G, ZHANG M, LI H, et al. Big data security and privacy protection[J]. Chinese Journal of Computers, 2014, 37(1)∶ 246-258.

[2] WONG R C W, LI J, FU A W C, et al. (α,k)-anonymity∶ an enhancedk-anonymity model for privacy preserving data publishing[C]//The 12th ACM SIGKDD international conference on Knowledge discovery and data mining. 2006∶ 754-759.

[3] CORMODE G, SRIVASTAVA D, YU T, et al. Anonymizing bipartite graph data using safe groupings[J]. The VLDB Journal—The International Journal on Very Large Data Bases, 2010, 19(1)∶ 115-139.

[4] CHENG J, FU A W, LIU J.K-isomorphism∶ privacy preserving network publication against structural attacks[C]//The 2010 ACM SIGMOD International Conference on Management of Data. 2010∶ 459-470.

[5] ABAWAJY J H, NINGGAL M I H, HERAWAN T. Privacy preserving social network data publication[J]. IEEE Communications Surveys &Tutorials, 2016, 18(3)∶ 1974-1997.

[6] LIU L, WANG J, LIU J, et al. Privacy preserving in social networks against sensitive edge disclosure[R]. Technical Report Technical Report CMIDA-HiPSCCS 006-08, 2008.

[7] DAS S, E?ECIO?LU ?, EL ABBADI A. Anonymizing weighted social network graphs[C]//2010 IEEE 26th International Conference on Data Engineering (ICDE). 2010∶ 904-907.

[8] LI Y, LI Y, YAN Q, et al. Privacy leakage analysis in online social networks[J]. Computers & Security, 2015, 49∶ 239-254.

[9] 蘇潔, 劉帥, 羅智勇, 等. 基于信息損失量估計(jì)的匿名圖構(gòu)造方法[J].通信學(xué)報, 2016, 37(6)∶ 56-64.SU J, LIU S, LUO Z Y, et al. Method of constructing an anonymous graph based on information loss estimation[J]. Journal on Communications, 2016, 37(6)∶ 56-64.

[10] LIU D, WANG H, VAN M P. Spectral perturbation and reconstructability of complex networks[J]. Physical Review E, 2010, 81(1)∶ 016101.

[11] XU S, ZHANG J, HAN D, et al. Singular value decomposition based data distortion strategy for privacy preserving[J]. Knowledge and Information Systems, 2006, 10(3)∶ 383-397.

[12] WU L, YING X, WU X. Reconstruction from randomized graph via low rank approximation[C]//The 2010 SIAM International Conference on Data Mining, Society for Industrial and Applied Mathematics. 2010∶ 60-71.

[13] PECH R, HAO D, PAN L, et al. Link prediction via matrix completion[J]. EPL (Europhysics Letters), 2017, 117(3)∶ 38002.

[14] XU X, LIU B, WU J, et al. Link prediction in complex networks via matrix perturbation and decomposition[J]. Scientific Reports, 2017, 7(1)∶ 14724.

[15] SARKAR S. Spectral (re) construction of urban street networks∶ generative design using global information from structure[M]//Design Computing and Cognition'14. Springer International Publishing, 2015∶ 41-55.

[16] 張賢達(dá). 矩陣分析與應(yīng)用(第2版)[M]. 北京∶ 清華大學(xué)出版社, 2013.ZHANG X D. Matrix analysis and applications.(second edi-tion)[M].Beijing∶ Tsinghua University Press, 2013.

[17] 戴華. 矩陣論[M]. 北京∶ 科學(xué)出版社, 2001.DAI H. Matrix theo-ry[M]. Beijing∶ Science Press, 2001.

[18] HORN R A, JOHNSON C R. 矩陣分析[M]. 天津∶ 天津大學(xué)出版社, 1989.HORN R A, JOHNSON, C R, Matrix analysis[M]. Tianjin∶ Tianjin University Press, 2001.

[19] ZHANG X D. Matrix analysis and applications[M]. Cambridge University Press, 2017.

[20] ERD?S P, RéNYI A. On the evolution of random graphs[J]. Transactions of the American Mathematical Society, 1984, 286(1)∶ 257-274.

[21] BARABáSI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439)∶ 509-512.

[22] WATTS D J, STROGATZ S H. Collective dynamics of “small-world”networks[J]. Nature, 1998, 393(6684)∶ 440-442.

[23] ABUELHAIJA S, PEROZZI B, ALRFOU R. Learning edge representations via low-rank asymmetric projections[C]//The 2017 ACM Conference on Information and Knowledge Management. 2017∶ 1787-1796.

[24] GLEISER P M, DANON L. Community structure in jazz[J]. Advances in Complex Systems, 2003, 6(4)∶ 565-573.