許佳鈺, 章紅艷, 許 力, 周趙斌

1(福建師范大學(xué) 數(shù)學(xué)與信息學(xué)院, 福州 350007)

2(福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點實驗室, 福州 350007)

近年來, 隨著使用微博、Facebook、Twitter等社交網(wǎng)站的用戶數(shù)快速增加, 產(chǎn)生 了大規(guī)模的社會網(wǎng)絡(luò)數(shù)據(jù). 這些數(shù)據(jù)具有巨大的商業(yè)價值和應(yīng)用場景, 同樣也包含了很多敏感信息[1]. 研究者開發(fā)出了大量的數(shù)據(jù)挖掘技術(shù)和社會網(wǎng)絡(luò)分析方法, 用來挖掘和分析這些數(shù)據(jù)背后的價值. 但如果發(fā)布的數(shù)據(jù)被不正確使用, 用戶可能會遭到惡意攻擊和面臨隱私泄露問題[2], 在數(shù)據(jù)挖掘的過程中需要保護(hù)用戶隱私[3]. 民法典中也確立了平衡個人信息保護(hù)與信息合理使用之間的基本準(zhǔn)則.因此, 對發(fā)布的社會網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行隱私保護(hù)尤為重要[4],在發(fā)布數(shù)據(jù)的同時應(yīng)該保護(hù)好個人隱私信息. 如何在有效地保護(hù)用戶隱私的同時又能保證發(fā)布的數(shù)據(jù)具有可用性[5], 這是人們一直在研究的問題.

數(shù)據(jù)的隱私保護(hù)問題已經(jīng)得到了廣泛的研究,Sweeney[6]在2002年最早提出k-匿名模型, 而最近趨向于個性化的k-匿名[7]的研究. 在k-匿名模型提出之后, l-多樣化[8], t-接近[9]等隱私保護(hù)模型也被先后提出.然而社會網(wǎng)絡(luò)中的節(jié)點之間存在相關(guān)性, 如果僅對節(jié)點進(jìn)行匿名處理, 攻擊者仍可能會根據(jù)邊權(quán)值或圖結(jié)構(gòu)對網(wǎng)絡(luò)進(jìn)行攻擊[10-12]. 目前針對社會網(wǎng)絡(luò)數(shù)據(jù)的隱私保護(hù)方法大致可分為基于聚類和基于圖修改兩種.

其中, 基于聚類的社會網(wǎng)絡(luò)隱私保護(hù)方法是通過特定的聚類規(guī)則將一些節(jié)點和邊進(jìn)行聚類, 然后通過泛化達(dá)到匿名化效果. Hay等[13]提出對網(wǎng)絡(luò)中相似節(jié)點進(jìn)行聚合, 聚合后每個塊中所包含的節(jié)點數(shù)n滿足k≤n≤2k-1的條件, 這樣使得攻擊成功的概率不高于1/k. Skarkala等[14]使用節(jié)點聚類和邊聚類相結(jié)合的方法對加權(quán)無向網(wǎng)絡(luò)進(jìn)行泛化, 以實現(xiàn)k-匿名. 姜火文等[15]利用屬性圖表示社交網(wǎng)絡(luò)數(shù)據(jù), 綜合根據(jù)節(jié)點間的結(jié)構(gòu)和屬性相似度, 將圖中所有節(jié)點聚類成一些包含節(jié)點個數(shù)不小于k的超點. 然而, 基于聚類的社會網(wǎng)絡(luò)隱私保護(hù)方法將節(jié)點聚類成超點或?qū)⑦吘垲惓沙厱?dǎo)致嚴(yán)重的邊信息損失, 破壞網(wǎng)絡(luò)結(jié)構(gòu), 大大降低數(shù)據(jù)可用性.

通過圖修改的方法實現(xiàn)社會網(wǎng)絡(luò)數(shù)據(jù)的隱私保護(hù)方法已成為近些年來研究者關(guān)注的熱點. Liu等[16]首次提出圖的k-度匿名化概念, 并采用增加邊的圖結(jié)構(gòu)修改方式來實現(xiàn)圖的k-度匿名化, 以抵抗節(jié)點度攻擊.Chester等[17]首次提出一種加邊與加點相結(jié)合的方法來實現(xiàn)k-度匿名圖. 針對節(jié)點具有標(biāo)簽的社會網(wǎng)絡(luò), 文獻(xiàn)[18,19]都提出了k-度-l多樣化匿名模型, 該模型在滿足k度匿名的基礎(chǔ)上, 要求度數(shù)相同的k個節(jié)點至少要有l(wèi)種不同標(biāo)簽, 并通過增加或刪除邊以及添加噪聲節(jié)點的方法實現(xiàn)匿名. Casas-Roma等[20]采用窮舉法和貪心算法生成度匿名序列, 通過鄰居中心性邊選擇方法和隨機(jī)邊選擇方法實現(xiàn)k-度匿名. 周克濤等[21]針對傳統(tǒng)的k-度匿名方法添加的噪聲數(shù)據(jù)過多, 提出了改進(jìn)的基于鄰居度序列相似度的k-度匿名保護(hù)方法,可以抵御以節(jié)點的度結(jié)合鄰居度序列作為背景知識的攻擊. Macwan等[22]提出了改進(jìn)的k-度匿名方法, 該模型保留了網(wǎng)絡(luò)結(jié)構(gòu)屬性以及用戶隱私. Kamalkumar等[23]針對大規(guī)模社會網(wǎng)絡(luò)提出快速的隱私保護(hù)方法, 對小社區(qū)實施個性化k-度匿名化. Kiabod等[24]引入一種節(jié)省時間的k-度匿名化方法, 該方法利用基于樹結(jié)構(gòu)計算圖的匿名度序列, 利用基于匿名化級別對圖形自底向上節(jié)點進(jìn)行分區(qū), 實現(xiàn)隱私保護(hù)級別的動態(tài)變化. 張曉琳等[25]針對大規(guī)模社會網(wǎng)絡(luò)有向圖, 提出了一種基于層次社區(qū)結(jié)構(gòu)的大規(guī)模社會網(wǎng)絡(luò)k-出入度匿名方法, 該方法提高了處理大規(guī)模社會網(wǎng)絡(luò)有向圖數(shù)據(jù)的效率, 并在匿名后保證了數(shù)據(jù)發(fā)布時社區(qū)結(jié)構(gòu)分析的可用性. 以上這些基于圖修改的社會網(wǎng)絡(luò)隱私保護(hù)方法大多都采用添加、刪除邊或添加節(jié)點以及子圖同構(gòu)等擾動方式實現(xiàn)k-度匿名, 但這些方法還存在信息損失較為嚴(yán)重的問題.

針對以上兩種方法存在的問題, 本文提出一種基于節(jié)點平均度的k-度匿名隱私保護(hù)方案, 用來解決社會網(wǎng)絡(luò)數(shù)據(jù)的發(fā)布可能導(dǎo)致用戶隱私泄露的問題, 在保護(hù)用戶隱私的同時提高了發(fā)布數(shù)據(jù)的可用性. 本方案首先利用基于平均度的貪心算法生成k-度匿名序列, 然后采用優(yōu)先保留重要邊的圖結(jié)構(gòu)修改方法來對圖進(jìn)行修改, 實現(xiàn)圖的k-度匿名化. 本方案不僅能有效地提高網(wǎng)絡(luò)抵抗度攻擊的能力, 還能克服傳統(tǒng)方案在對網(wǎng)絡(luò)匿名后所產(chǎn)生的信息損失嚴(yán)重的問題, 在保護(hù)用戶隱私的同時提高了發(fā)布數(shù)據(jù)的可用性.

1 相關(guān)定義

在本文中, 用一個無向無權(quán)的圖來表示社會網(wǎng)絡(luò),G=(V,E),V代表用戶實體,E代表實體間的關(guān)系,V={v1,v2,···,vn} 是節(jié)點的集合,是邊的集合且1 ≤i,j≤n.dG代表圖G的度序列,d=[d1,d2,···,dn]. 其中,d(i) 或d(vi)代 表圖中第i個節(jié)點vi的度.

定義1. 向量k-匿名. 如果整數(shù)向量V是k-度匿名的, 那么向量V中每個值都出現(xiàn)至少k次. 例如, 向量V=[5,5,3,3,2,2,2]是2-度匿名的.

定義2. 圖的k-度匿名. 如果圖G的度數(shù)序列d是k-匿名的, 那么圖G= (V,E)是k-度匿名的.

顯然, 只要找到原圖的最優(yōu)k-度匿名向量, 就可以根據(jù)該向量在原圖基礎(chǔ)上增補(bǔ)出新的k-度匿名圖. 如圖1(a)是一個沒有進(jìn)行過度匿名的原始圖, 度序列為[2,3,3,5,3,2,4,3,3,2], 給定度序列和相應(yīng)的節(jié)點ID序列.由于只有節(jié)點4具有度5, 而只有節(jié)點7具有度4, 所以任何人都可以重新識別出節(jié)點4和節(jié)點7. 將圖1(a)匿名成圖1(b), 度序列為[3,4,4,5,3,5,5,4,3,4], 變成一個3-度匿名圖, 這時圖中任何一個節(jié)點都至少有2個節(jié)點與其度數(shù)相同, 可以重新識別節(jié)點4或節(jié)點7的概率都減少到1/3.

圖1 匿名前后對比圖

因此, 如果一個圖滿足k-度匿名, 則表明圖中任一個節(jié)點至少與其他k-1個節(jié)點具有相同的度, 利用節(jié)點度數(shù)作為背景知識的攻擊者能夠識別目標(biāo)個體的概率不超過1/k[16]. 我們用k值這個指標(biāo)來衡量社會網(wǎng)絡(luò)的抵御攻擊能力,k值越大, 目標(biāo)個體身份被攻擊者識別的概率就越小, 社會網(wǎng)絡(luò)的抵御攻擊能力就越強(qiáng), 隱私保護(hù)程度也就越高.

根據(jù)以上定義, 為了將輸入圖G轉(zhuǎn)換為結(jié)構(gòu)上類似于G的k-度匿名圖, 我們首先需要將G的度序列d轉(zhuǎn)換成k-度匿名序列, 然后根據(jù)度匿名序列對G進(jìn)行圖結(jié)構(gòu)修改構(gòu)造出, 我們在圖結(jié)構(gòu)修改時是通過增加、刪除或者交換邊來實現(xiàn)節(jié)點度數(shù)的調(diào)整. 以單純對邊進(jìn)行操作, 不增加節(jié)點的策略為例, 我們希望選擇邊變化最少(度數(shù)變化最少)的方案來實現(xiàn)k-度匿名,這樣可以保證匿名前后圖結(jié)構(gòu)的相似性.

定義3. 基于平均度的圖匿名代價. 圖匿名代價可用匿名前后邊的變化數(shù)來計算, 根據(jù)握手定理可知一條邊貢獻(xiàn)兩個度, 即匿名前后度的總變化數(shù)剛好是邊的總變化數(shù)的兩倍, 因此邊的變化數(shù)與度的變化數(shù)直接相關(guān).

圖匿名代價GA(G,)由式(1)計算得到:

對于i＜j, 節(jié)點i到j(luò)之間的所有節(jié)點的平均度為d(a), 由式(3)計算得到:

如果節(jié)點i到j(luò)之間的所有節(jié)點形成同一個匿名組, 同一組中所有節(jié)點的度都匿名成該組所有節(jié)點的平均度d(a), 則有式(4)成立:

將該組的匿名代價記為I(d[i,j]),則基于節(jié)點平均度的k-度匿名代價由式(5)計算得到:

在進(jìn)行圖修改操作時要實現(xiàn)式(5)的最小化, 以保持?jǐn)?shù)據(jù)可用性.

2 社會網(wǎng)絡(luò)的k-度匿名隱私保護(hù)方案

本節(jié)提出了一種基于節(jié)點平均度的k-度匿名隱私保護(hù)方案, 方案主要包括度匿名序列生成和圖結(jié)構(gòu)修改兩個階段. 首先利用基于平均度的貪心算法對社會網(wǎng)絡(luò)節(jié)點度序列進(jìn)行劃分, 生成k-度匿名序列； 然后根據(jù)生成的k-度匿名序列對圖進(jìn)行修改實現(xiàn)圖的k-度匿名化, 修改時采用優(yōu)先保留重要邊的圖結(jié)構(gòu)修改方法.與傳統(tǒng)方案相比, 在對圖結(jié)構(gòu)的修改程度一樣的前提下, 本方案可以達(dá)到更大的k值, 說明本方案相對傳統(tǒng)方案的抵御攻擊能力有顯著提高, 提供了更強(qiáng)的隱私保護(hù).

本文中的符號說明見表1.

表1 符號說明

2.1 度匿名序列生成

本方案利用基于平均度的貪心算法(算法1)生成原始圖的k-度匿名序列.

下面給出了生成k-度匿名序列的算法.

算法1. k-度匿名序列生成算法輸入: 原始圖G, 正整數(shù)k ?d輸出: k-度匿名序列1. d←degree sequence of G 2. sort(d)3. put the first k nodes into group gi 4. i = 1 5. while until every node gets the group do 6. count Cmerge, Cnew 7. if Cmerge＞ Cnewthen 8. i++9. put nodes nk+1 ～n2k into new group gi 10. k = k + 2k 11. else 12. put node nk+1 into group gi 13. k = k + 1 14. end if

15. count da(gi)//計算的平均度16. the degree of node in gi becomes da(gi)17. end while

該算法將社會網(wǎng)絡(luò)圖G和整數(shù)k作為輸入, 首先找到輸入圖G的度數(shù)序列并將其按度數(shù)降序的順序進(jìn)行排序, 然后將前k個節(jié)點放入同一組, 接著分別根據(jù)式(6)和式(7)計算比較Cmerge和Cnew兩個成本, 來決定應(yīng)該將第(k+1)個節(jié)點合并到當(dāng)前的分組中, 還是在位置(k+1)處開始一個新組. 其中Cmerge表示把第(k+1)個節(jié)點合并到當(dāng)前分組所產(chǎn)生的成本, 由式(6)計算得到；Cnew表示把第(k+1)個節(jié)點放入一個新的分組所產(chǎn)生的成本, 由式(7)計算得到.

當(dāng)Cmerge＞Cnew時, 將第k+1～2k的節(jié)點放入一個新的分組, 然后計算和比較第2k+1個節(jié)點的成本并放入相應(yīng)的分組中, 以此類推.

當(dāng)Cmerge＜Cnew時, 將第k+1個節(jié)點合并到上一個分組, 然后計算和比較第k+2個節(jié)點的成本并放入相應(yīng)的分組中, 以此類推.

直到將所有節(jié)點分完組后, 計算每一個分組中節(jié)點的所有節(jié)點的平均度d(a), 然后令該組中所有節(jié)點的度都變?yōu)槠骄? k-度匿名序列生成.

2.2 圖結(jié)構(gòu)修改

在上一節(jié)中, 原始圖的度序列已經(jīng)被匿名成為k-度匿名序列. 根據(jù)生成的k-度匿名序列對圖結(jié)構(gòu)進(jìn)行修改, 使得修改后的匿名圖的度序列滿足匿名要求.

本方案中進(jìn)行圖結(jié)構(gòu)修改時對邊的操作方式主要包含以下3種:

(1)邊增加策略: 如圖2所示, 我們選擇兩個不同節(jié)點vi,vj∈V, 若(vi,vj)?E, 可以在節(jié)點vi,vj之間添加一條邊(vi,vj), 兩個節(jié)點的度同時增加1； 若(vi,vj)∈E,此時需要找到節(jié)點vi的不相鄰節(jié)點集合(vi), 以及vj的不相鄰節(jié)點集合(vj), 在(vi)和(vj)中分別找到兩個節(jié)點vp,vq滿足(vp,vq)∈E, 刪除邊(vp,vq),同時增加邊(vp,vi) 與 邊(vq,vj) ,此時我們可以看出兩個節(jié)點vi,vj的度同時增加1, 而節(jié)點vp,vq的度沒有變化, 并且增加了一條邊.

圖2 邊增加策略的方式

(2)邊刪除策略: 如圖3所示, 我們選擇兩個不同節(jié)點vi,vj∈V, 若(vi,vj)∈E, 此時我們可以在節(jié)點vi,vj之間刪除邊(vi,vj), 兩個節(jié)點的度同時減1； 若(vi,vj)?E,此時我們需要找到節(jié)點vi的相鄰節(jié)點集合Γ (vi), 以及vj的相鄰節(jié)點集合Γ (vj). 在Γ (vi)和 Γ (vj)中分別找到兩個節(jié)點vp,vq滿足(vp,vq)?E, 增加邊(vp,vq), 同時刪除邊(vp,vi) 與 邊(vq,vj) . 此時節(jié)點vi,vj的度同時減少1, 而vp,vq的度沒有變化, 并且減少了一條邊.

圖3 邊刪除策略的方式

(3)邊交換策略: 如圖4所示, 在邊交換策略中,(vj,vp) 與 (vi,vj)?E這兩種情況的邊操作是一樣的, 需要同時對3個點進(jìn)行操作. 如果vi,vj,vp∈V, 且同時滿足(vi,vp)∈E和(vj,vp)?E, 此時刪除邊(vi,vp), 增加邊(vj,vp), 節(jié)點vi的度減少1, 而節(jié)點vj的 度增加了1,vp的度和邊數(shù)沒有變化.

圖4 邊交換策略的方式

原始圖中節(jié)點v的度數(shù)d(v)與其所屬分組的平均度數(shù)d(a)之間可能存在的大小關(guān)系有如下3種情況:

(1)當(dāng)d(v)＜d(a) 時 , Δd(v)＞0 , 節(jié)點v需要通過執(zhí)行邊增加策略使節(jié)點度數(shù)增加.

(2)當(dāng)d(v)＞d(a) 時 , Δd(v)＜0 , 節(jié)點v需要通過執(zhí)行邊刪除策略使節(jié)點度數(shù)減少.

(3)當(dāng)d(v)=d(a) 時, Δd(v)=0 , 節(jié)點v滿足匿名化,不需要進(jìn)行任何操作.

我們在進(jìn)行圖結(jié)構(gòu)修改時只需考慮還未滿足度匿名化的節(jié)點, 對于滿足度匿名化的節(jié)點可直接跳過無需進(jìn)行任何操作. 對于還未滿足度匿名化的節(jié)點, 需要根據(jù)兩個點間的度數(shù)大小關(guān)系以及有無連邊的情況選擇相應(yīng)的圖修改策略.

任意兩個節(jié)點vi,vj, 兩者都滿足Δd(v)＜0, 則需要執(zhí)行圖2中的邊增加策略, 還需根據(jù)兩個節(jié)點之間是否存在邊選擇相應(yīng)的操作方式. 當(dāng)兩個節(jié)點之間不存在邊時, 則選擇操作方式如圖2(a)； 當(dāng)兩個節(jié)點之間存在邊時, 則選擇操作方式如圖2(b).

任意兩個節(jié)點vi,vj, 兩者都滿足Δd(v)＞0, 則需要執(zhí)行圖3中的邊刪除策略, 還需根據(jù)兩個節(jié)點之間是否存在邊選擇相應(yīng)的操作方式. 當(dāng)兩個節(jié)點之間不存在邊時, 則選擇操作方式如圖3(a)； 當(dāng)兩個節(jié)點之間存在邊時, 則選擇操作方式如圖3(b).

任意兩個節(jié)點vi,vj, 其中一個滿足Δd(v)＞0, 另一個滿足Δd(v)＜0時, 則需要執(zhí)行圖4中的邊交換策略,無論兩個節(jié)點之間是否存在邊, 操作方式都是一樣的.

在邊操作中選擇邊的時候, 要考慮保留重要的邊,方案中我們利用了鄰域中心性(Neighbourhood Centrality,NC)值來量化大型網(wǎng)絡(luò)的邊緣相關(guān)性[20]. 邊(vi,vj)的鄰域中心性定義為同時與vi或vj相鄰, 但不同時與vi和vj相鄰的節(jié)點的比例, 由式(8)計算得到:

NC值越小, 說明該邊的邊相關(guān)程度就越低, 該邊的重要程度比較低；NC值越大, 說明該邊的邊相關(guān)程度就越高, 該邊的重要程度比較低. 為了降低圖修改前后的信息損失量, 本方案在進(jìn)行邊操作時選擇NC值較低的邊.

本方案的算法在執(zhí)行時會多次遍歷, 直達(dá)圖結(jié)構(gòu)修改完成, 具體的圖結(jié)構(gòu)修改算法如算法2所示.

算法2. 圖結(jié)構(gòu)修改算法輸入: 原始圖G, 原始圖度序列d, k-度匿名序列?G輸出: k-度匿名圖 1. while True do Δd=?d-d 2. sort(|Δd|)3. vi=|Δd|max 4. pick node |Δd|vj≠0 5. pick node vj randomly, Δdvj＞0 Δdvj＞0 6. if and then 7. if there exits (vi,vj) then vp,vq?Γ(vj)vp,vq?Γ(vj)8. pick two nodes vp,vq randomly (exits (vp,vq) and and )9. delete (vp,vq), add (vi,vp), add (vj,vp)10. else 11. add (vi,vj)Δdvi++,Δdvj++12. 13. end if Δdvi＜0 Δdvj＜0 14. if and then 15. if there exits (vi,vj) then 16. delete (vi,vj)17. else vp∈Γ(vi)vq∈Γ(vj)18. pick two nodes vp,vq randomly (not exits (vp,vq) and and )19. delete (vi,vp), delete (vj,vq), add (vp,vq)Δdvi--,Δdvj--20. 21. end if Δdvi＜0 Δdvj＞0 22. if and then vp∈Γ(vi) vp?Γ(vj)23. pick node vp randomly ( and )24. delete (vi,vp), add (vj,vp)Δdvi--,Δdvj++25. Δdvi＞0 Δdvj＜0 26. if and then vq?Γ(vi) vq∈Γ(vj)27. pick node vq randomly ( and )28. add (vi,vp), delete (vj,vp)Δdvi++,Δdvj--29. 30. end while

在上述算法中, 將原始圖G和匿名前后的度序列作為輸入, 首先計算每個節(jié)點需增加的度數(shù)| Δd(v)|, 這個過程的時間復(fù)雜度為O(n), 并對其進(jìn)行降序排序, 排序過程的時間復(fù)雜度O(nlog2n). 然后選取| Δd(v)|值最大的節(jié)點vi和| Δd(v)|值 非零的節(jié)點vj, 判斷vi與vj之間的度數(shù)關(guān)系以及有無連邊, 執(zhí)行相應(yīng)的邊操作, 并更新兩個節(jié)點相應(yīng)的Δd(v)值, 這個過程的時間復(fù)雜度為O(1).根據(jù)更新后的Δd(v)值繼續(xù)選擇操作的節(jié)點, 重復(fù)以上步驟, 直到所有節(jié)點的Δd(v)值為0, 則圖結(jié)構(gòu)修改完成,總重復(fù)次數(shù)為O(n)級別. 因此, 該算法的總時間復(fù)雜度為O(n2)級別. 但是在真實社交網(wǎng)絡(luò)中 算法仍有較好的執(zhí)行效率, 能夠滿足實際需求.

3 實驗結(jié)果分析

本方案使用Facebook數(shù)據(jù)集進(jìn)行仿真實驗, 來源于 Stanford大學(xué)的一個公開數(shù)據(jù)庫SNAP[26], 該數(shù)據(jù)集說明了Facebook社交網(wǎng)站上的各個用戶之間的關(guān)系,包含節(jié)點數(shù)4039個, 無向邊88 234條, 節(jié)點的總度數(shù)為176 468度, 平均度數(shù)為43度, 且節(jié)點的度服從冪律分布. 算法代碼用Python編程實現(xiàn), 實驗環(huán)境為Intel Core i5 CPU 1.4 GHz, 16 GB內(nèi)存, 操作系統(tǒng)為 MacOS.

對于社會網(wǎng)絡(luò)中的圖數(shù)據(jù), 在進(jìn)行匿名隱私保護(hù)的同時保持其可用性是非常重要的[10]. 為了說明本文提出的k-度匿名隱私保護(hù)方案的有效性, 我們通過計算邊的變化率來說明數(shù)據(jù)的信息損失量, 其中邊的變化率為匿名前后邊的變化數(shù)與原始圖中的邊總數(shù)之比.數(shù)據(jù)的信息損失量越小, 則數(shù)據(jù)的可用性越好. 另外我們還考慮了圖結(jié)構(gòu)的一些基本屬性, 主要測試平均聚類系數(shù)、平均最短路徑、節(jié)點平均度這3個指標(biāo). 單個節(jié)點的聚類系數(shù)是它所有相鄰節(jié)點之間連邊的數(shù)目占可能的最大連邊數(shù)目的比例, 而整個網(wǎng)絡(luò)的平均聚類系數(shù)就是所有節(jié)點簇系數(shù)的平均值； 平均最短路徑是網(wǎng)絡(luò)中所有結(jié)點對的距離的平均值； 節(jié)點平均度是網(wǎng)絡(luò)中所以節(jié)點的度數(shù)之和與節(jié)點總數(shù)之比. 我們將實驗前的數(shù)據(jù)與進(jìn)行k-度匿名后的數(shù)據(jù)進(jìn)行對比, 同時與文獻(xiàn)[16,20]的方案進(jìn)行對比來, 以驗證本方案的有效性.

圖5展示的是本方案和文獻(xiàn)[16,20]的方案在匿名前后信息損失量的變化結(jié)果, 表2是具體的實驗數(shù)據(jù). 通過對比分析在匿名前后網(wǎng)絡(luò)的邊變化率來衡量信息損失量. 如圖5所示, 隨著k值的增大, 3種方案造成的信息損失量也都跟著變大, 但是相比于文獻(xiàn)[16,20]兩種方案, 本方案信息損失量是最小的, 更好地保持了數(shù)據(jù)的高可用性.圖6展示了本方案和文獻(xiàn)[16,20]方案在匿名前后聚類系數(shù)的變化結(jié)果, 表3是具體的實驗數(shù)據(jù). 如圖6所示, 與文獻(xiàn)[16,20]兩種方案相比, 本方案使得匿名后的網(wǎng)絡(luò)在不同的k值下始終最接近于原始網(wǎng)絡(luò)的平均聚類系數(shù)值, 對網(wǎng)絡(luò)平均聚類系數(shù)的影響明顯小于另外兩種方案. 文獻(xiàn)[16]的方案在圖結(jié)構(gòu)修改時沒有考慮保留重要的邊, 使得匿名后網(wǎng)絡(luò)的平均聚類系數(shù)與原始網(wǎng)絡(luò)相比有較大改變, 對圖結(jié)構(gòu)的修改較大. 而本方案在圖結(jié)構(gòu)修改時引入了NC值來保留重要的邊, 匿名前后圖結(jié)構(gòu)變化非常小. 由此可見, 本方案在實現(xiàn)k-度匿名保護(hù)用戶隱私同時, 還能保持?jǐn)?shù)據(jù)具有較高的可用性.

圖5 信息損失量對比圖

表2 信息損失量對比

圖6 平均聚類系數(shù)對比圖

表3 平均聚類系數(shù)對比

圖7展示的是本方案和文獻(xiàn)[16,20]的方案在匿名前后平均最短路徑的變化結(jié)果, 表4是具體的實驗數(shù)據(jù).如圖7所示, 隨著k值的增加, 3種方案的平均最短路徑都在減小, 但是文獻(xiàn)[16]的方案使得匿名后網(wǎng)絡(luò)的平均最短路徑始終大于原始網(wǎng)絡(luò), 較大程度地破壞了網(wǎng)絡(luò)結(jié)構(gòu). 當(dāng)k值較小時, 文獻(xiàn)[20]的方案使得匿名后網(wǎng)絡(luò)的平均最短路徑始大于原始網(wǎng)絡(luò), 對網(wǎng)絡(luò)結(jié)構(gòu)的破壞較大；當(dāng)k值較大時, 文獻(xiàn)[20]的方案使得匿名后網(wǎng)絡(luò)的平均最短路徑始小于原始網(wǎng)絡(luò), 對網(wǎng)絡(luò)結(jié)構(gòu)的破壞較小. 而本方案使得匿名后網(wǎng)絡(luò)的平均最短路徑始終小于原始網(wǎng)絡(luò), 較好地保持了網(wǎng)絡(luò)結(jié)構(gòu)的穩(wěn)定性.

圖7 平均最短路徑對比圖

表4 平均最短路徑對比

圖8展示的是本方案和文獻(xiàn)[16,20]的方案在匿名前后節(jié)點平均度的變化結(jié)果, 表5是具體的實驗數(shù)據(jù). 如圖8所示, 隨著k值的增加, 本方案對原始網(wǎng)絡(luò)節(jié)點平均度的改變量最小, 匿名后網(wǎng)絡(luò)的節(jié)點平均度數(shù)與原始網(wǎng)絡(luò)基本相同. 文獻(xiàn)[20]的方案對原始網(wǎng)絡(luò)節(jié)點平均度的改變程度略高于本方案. 文獻(xiàn)[16]的方案使得匿名前后網(wǎng)絡(luò)的節(jié)點平均度有較大改變, 對原始網(wǎng)絡(luò)結(jié)構(gòu)的破壞較為嚴(yán)重.

表5 節(jié)點平均度對比

圖8 節(jié)點平均度對比圖

圖9展示了本方案和文獻(xiàn)[16,20]的方案在運行時間上的比較結(jié)果, 表6是具體的實驗數(shù)據(jù). 如圖9所示, 當(dāng)k值較小時, 3個方案的算法運行時間大致相同,當(dāng)k值較大時, 本方案的運行時間要高于文獻(xiàn)[16,20]的方案. 但總體來說, 本方案的運行時間不會比另外兩個方案高出很多, 且本方案使得社會網(wǎng)絡(luò)在抵御度攻擊方面和保持圖數(shù)據(jù)可用性方面均有了較好的改進(jìn),因此這樣稍高的時間復(fù)雜度還是在可接受范圍內(nèi).

表6 執(zhí)行時間對比(s)

圖9 執(zhí)行時間對比圖

4 結(jié)束語

針對社會網(wǎng)絡(luò)數(shù)據(jù)的發(fā)布可能遭到度攻擊進(jìn)而導(dǎo)致用戶隱私泄露的問題, 本文提出一種基于節(jié)點平均度的k-度匿名隱私保護(hù)方案, 本方案在保護(hù)用戶隱私的同時保證了發(fā)布的數(shù)據(jù)具有較高可用性. 首先利用基于平均度的貪心算法對社會網(wǎng)絡(luò)節(jié)點度序列進(jìn)行劃分, 使得同一分組中節(jié)點的度都修改成平均度, 生成k-度匿名序列, 極大地減少了與原始度序列的距離； 然后使用邊增加、邊刪除、邊交換3種邊操作方式對原始圖進(jìn)行圖結(jié)構(gòu)修改, 由于對邊進(jìn)行操作時考慮了NC值, 保留了網(wǎng)絡(luò)中重要的邊, 匿名后的網(wǎng)絡(luò)保持了較好的連通性和關(guān)系結(jié)構(gòu), 從而提高了發(fā)布數(shù)據(jù)的可用性.本方案不僅能有效提高社會網(wǎng)絡(luò)抵御度攻擊的能力,還能保持網(wǎng)絡(luò)結(jié)構(gòu)的高穩(wěn)定性和發(fā)布數(shù)據(jù)的高可用性.但是在算法的時間復(fù)雜度方面, 與其它方案相比優(yōu)勢不夠明顯, 因此還需要在未來進(jìn)一步研究如何減小算法的時間復(fù)雜度.