基于節(jié)點分類的k度匿名隱私保護(hù)方法

金 葉,丁曉波,龔國強(qiáng),呂 科

(三峽大學(xué) 計算機(jī)與信息學(xué)院,湖北 宜昌 443002)

0 概述

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展,許多移動應(yīng)用系統(tǒng)和線上交流平臺不斷出現(xiàn),形成多種類型的社交網(wǎng)絡(luò),如微信、QQ、新浪微博、Facebook、Twitter等[1],這些社交平臺擁有上億的用戶并產(chǎn)生海量數(shù)據(jù),通過對網(wǎng)絡(luò)中產(chǎn)生的海量數(shù)據(jù)分析和研究,可以識別出人們的身份、聯(lián)系方式等隱私信息,因此針對社交網(wǎng)絡(luò)數(shù)據(jù)的保護(hù)已經(jīng)變得至關(guān)重要[2]。在發(fā)布數(shù)據(jù)時,如何保證數(shù)據(jù)具有研究價值和實用性的同時能有效保護(hù)數(shù)據(jù)的隱私信息,也是人們一直關(guān)注的問題[3]。在文獻(xiàn)[4]提出針對關(guān)系型數(shù)據(jù)的k匿名方法后,數(shù)據(jù)隱私保護(hù)開始衍生出各種各樣的匿名方案,針對屬性數(shù)據(jù)有(k,l)[5]、(p,k)[6]等保護(hù)方法,而針對具有圖結(jié)構(gòu)的數(shù)據(jù),采取k度匿名的思想進(jìn)行匿名隱私保護(hù)[7-8]。文獻(xiàn)[9]提出針對節(jié)點度攻擊的k度匿名保護(hù)方法,通過增加或者刪除邊的方式來匿名節(jié)點的度。文獻(xiàn)[10]通過優(yōu)化邊的選擇策略來改進(jìn)k度匿名,降低了邊的修改數(shù)目,從而提高數(shù)據(jù)的實用性。文獻(xiàn)[11]通過將節(jié)點聚類形成多個“超節(jié)點”,每個“超節(jié)點”中至少含有k個節(jié)點,從而提出簇聚類匿名方法來保護(hù)隱私信息。文獻(xiàn)[12]提出針對復(fù)雜網(wǎng)絡(luò)的可拓展聚類算法。文獻(xiàn)[13]提出通過縮小圖中任意兩節(jié)點間的距離來實現(xiàn)k度匿名保護(hù)。

在傳統(tǒng)k度匿名保護(hù)方法中,匿名算法雖然能快速構(gòu)建出一個滿足k度序列的社交網(wǎng)絡(luò)圖,但是因為對圖進(jìn)行重構(gòu),在很大程度上造成了圖結(jié)構(gòu)的損壞,節(jié)點間的結(jié)構(gòu)關(guān)系受到嚴(yán)重破壞,并且該方法在攻擊者只擁有節(jié)點的度這一先驗知識時是具有保護(hù)效用的,但當(dāng)攻擊者擁有更強(qiáng)的先驗知識時,如節(jié)點的一跳鄰居結(jié)構(gòu)、節(jié)點的社區(qū)關(guān)系等信息,k度匿名保護(hù)方法則無法抵抗這些攻擊。本文提出一種改進(jìn)的k度匿名保護(hù)方法,從節(jié)點本身出發(fā)優(yōu)化節(jié)點的度及圖的結(jié)構(gòu)。

1 相關(guān)定義

在本文中,社交網(wǎng)絡(luò)用一個無向無權(quán)的圖來表示,V表示用戶實體,E表示實體間的關(guān)系,V={v1,v2,…,vn}是節(jié)點的集合,E={(vi,vj)|vi,vj∈V}是邊的集合且1≤i,j≤n,deg(vi)或者deg(i)表示圖中節(jié)點vi的度。本文匿名方法考慮社交網(wǎng)絡(luò)具有的“小世界”現(xiàn)象[14],對節(jié)點進(jìn)行劃分形成多個社區(qū)結(jié)構(gòu),分別對社區(qū)內(nèi)的節(jié)點和連接社區(qū)的節(jié)點采取匿名操作。從整體圖來看,實現(xiàn)的是度匿名,但是從節(jié)點之間的社區(qū)連接來看,也實現(xiàn)了連接關(guān)系的匿名,不同的保護(hù)策略對不同的節(jié)點匿名,達(dá)到更好的匿名效果,能有效抵抗社區(qū)關(guān)系和度等推理攻擊手段。

對一個原始的社交網(wǎng)絡(luò)圖數(shù)據(jù),本文首先對其進(jìn)行預(yù)處理,將節(jié)點劃分到不同的社區(qū)中,并采用模塊度這一概念判斷當(dāng)前節(jié)點劃分的有效性。

定義1(模塊度) 模塊度又稱模塊化度量值,是一種常用的衡量網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)強(qiáng)度的方法[15]。式(1)為模塊度的數(shù)學(xué)表達(dá)式:

(1)

通過模塊度的約束,將整個圖劃分為多個社區(qū)子圖,每個社區(qū)子圖包含多個節(jié)點,而串聯(lián)起這些社區(qū)子圖的節(jié)點就是重要的橋梁節(jié)點,社區(qū)內(nèi)除去這些橋梁節(jié)點,其余的是普通節(jié)點。

定義2(邊緣節(jié)點) 邊緣節(jié)點又稱為橋梁節(jié)點,對于劃分后的節(jié)點,社區(qū)中和其他社區(qū)存在連接關(guān)系的節(jié)點稱為邊緣節(jié)點,如屬于社區(qū)A的節(jié)點v,與社區(qū)B中的節(jié)點u之間有一條邊相連,則節(jié)點v和u分別是社區(qū)A和B中的邊緣節(jié)點。

邊緣節(jié)點充當(dāng)橋的作用,將各個社區(qū)串聯(lián)起來,有著非常重要的影響力和傳播力。在現(xiàn)實生活中,充當(dāng)橋梁作用的用戶通常都是與其他用戶連接緊密、關(guān)系復(fù)雜的人,圖能夠充分體現(xiàn)這一關(guān)系,而且社區(qū)結(jié)構(gòu)也與 “物以類聚,人以群分”概念相符,相同興趣愛好的用戶聚到一起形成社區(qū),各類用戶分布在各個社區(qū)中,又由充當(dāng)橋梁的共同用戶互相連接起來,形成復(fù)雜的社交網(wǎng)絡(luò)圖[15-16]。對邊緣節(jié)點的匿名,不僅要考慮節(jié)點的度,而且要考慮節(jié)點之間的社區(qū)關(guān)系,攻擊者具有的背景知識豐富多樣,泄露社區(qū)的關(guān)系相當(dāng)于泄露了社區(qū)中的節(jié)點信息,因此對邊緣節(jié)點的社區(qū)關(guān)系匿名比簡單的度匿名更加重要。

根據(jù)邊緣節(jié)點的定義可知,多個社區(qū)之間通過不同邊緣節(jié)點連接,一個邊緣節(jié)點可能與多個社區(qū)存在連接關(guān)系,統(tǒng)計該邊緣節(jié)點所連的社區(qū)號,則可以得到各個社區(qū)的連接關(guān)系。

定義3(邊緣節(jié)點社區(qū)序列) 對于一個邊緣節(jié)點vi,與其相連的社區(qū)數(shù)為cni,圖中所有邊緣節(jié)點的社區(qū)數(shù)組成社區(qū)序列CN={cn1,cn2,…,cnm} 。

由定義3可知,邊緣節(jié)點的社區(qū)數(shù)其實也是邊緣節(jié)點的度,與度不相同的是這些節(jié)點所連的社區(qū)之間的關(guān)系不同,對這些社區(qū)數(shù)匿名就相當(dāng)于對社區(qū)關(guān)系匿名。

定義4(邊緣節(jié)點k度匿名) 對于一個邊緣節(jié)點vi,其連接的社區(qū)數(shù)為cni,當(dāng)連接社區(qū)個數(shù)為cni的邊緣節(jié)點至少有k個時,滿足邊緣節(jié)點k度匿名。

邊緣節(jié)點k度匿名引自傳統(tǒng)的隱私保護(hù)方法k度匿名。此類算法的思想是對于表中的任意一條數(shù)據(jù),存在至少k-1條數(shù)據(jù)在屬性上與之相同,則攻擊者成功識別該用戶屬性的概率最大為1/k,本文中的節(jié)點匿名也是采用該思想,即隱藏任意節(jié)點到k個節(jié)點中。

2 基于節(jié)點分類的隱私保護(hù)方法

2.1 攻擊模型

本節(jié)對邊緣節(jié)點攻擊模型進(jìn)行詳細(xì)闡述,并且針對該攻擊模型,提出k度匿名隱私保護(hù)模型來抵抗邊緣節(jié)點攻擊?，F(xiàn)有的去匿名化方法大多是針對子圖結(jié)構(gòu),先將原始圖劃分成多個子圖,然后對每個子圖進(jìn)行節(jié)點去匿名化,對于一些具有明顯社區(qū)結(jié)構(gòu)的子圖,只要運用基本的社區(qū)劃分算法,就能將節(jié)點劃分到不同的社區(qū)中,之后通過對這些社區(qū)中的節(jié)點進(jìn)行k度匿名或者子圖匹配,就能快速識別該節(jié)點。這種通過圖結(jié)構(gòu)關(guān)系來去匿名化節(jié)點的攻擊方法攻擊力度非常大,加劇了信息泄露問題。

在圖1中,將社交網(wǎng)絡(luò)圖劃分為3個社區(qū),由邊緣節(jié)點1、2、3串聯(lián)起整個網(wǎng)絡(luò)圖?？梢钥闯?社區(qū)B與社區(qū)A、社區(qū)C都有連接關(guān)系,但是社區(qū)A和社區(qū)C都只與其中一個社區(qū)相連,也就是與邊緣節(jié)點2相連的社區(qū)數(shù)為2,而邊緣節(jié)點1和節(jié)點3的社區(qū)數(shù)都為1,即邊緣節(jié)點的社區(qū)數(shù)序列為(2,1,1),如果此時攻擊者知道某個節(jié)點所連的社區(qū)數(shù)目為2,那么邊緣節(jié)點2與其所處的社區(qū)都可以被識別出來。本文通過更改邊緣節(jié)點之間的連接關(guān)系,間接改變社區(qū)之間的關(guān)系,實現(xiàn)社區(qū)數(shù)序列的k匿名,從而對社區(qū)和節(jié)點進(jìn)行保護(hù)。

圖1 社區(qū)關(guān)系攻擊示意圖

2.2 基于節(jié)點分類的k度匿名保護(hù)模型

對節(jié)點進(jìn)行分類匿名,一類是社區(qū)內(nèi)節(jié)點,另一類是連接各個社區(qū)的邊緣節(jié)點。首先對M個社區(qū)中的邊緣節(jié)點進(jìn)行遍歷,統(tǒng)計邊緣節(jié)點的社區(qū)數(shù)形成社區(qū)數(shù)序列,然后判斷這個序列是否滿足k匿名。如果不滿足,則從序列數(shù)最小的節(jié)點v開始,隨機(jī)選擇節(jié)點u=(Cv≠Cu& (u,v)?E),添加(u,v)這條邊,通過不斷遍歷[17]實現(xiàn)邊緣節(jié)點的社區(qū)數(shù)序列k度匿名。對于社區(qū)內(nèi)的節(jié)點,首先統(tǒng)計該社區(qū)內(nèi)的度序列,如果度序列滿足k度匿名,則該社區(qū)不需要進(jìn)行邊的修改操作,當(dāng)度序列不滿足k度匿名時,則在社區(qū)內(nèi)進(jìn)行邊的增加或者刪除操作,使得在社區(qū)內(nèi)至少存在k個節(jié)點的度相同,實現(xiàn)社區(qū)內(nèi)節(jié)點的k度匿名。分別對節(jié)點進(jìn)行匿名后,從整個社區(qū)網(wǎng)絡(luò)圖來看,匿名后的圖滿足k度匿名,并且能夠抵抗度攻擊和社區(qū)聚類攻擊。

圖2是k度匿名流程。圖3是基于節(jié)點分類的匿名流程。通過兩個流程圖可以看出,本文匿名算法無需重構(gòu)圖,這樣能保證最大程度地保留原始圖結(jié)構(gòu),并且相比于傳統(tǒng)k度匿名算法,節(jié)點分類匿名思想可以根據(jù)節(jié)點的重要性實施不同程度的隱私保護(hù),具有一定的隱私保護(hù)伸縮性,比k度匿名更加靈活且符合實際情況。

圖2 k度匿名流程

Fig.2 Procedure of implementing k degree anonymity

圖3 基于節(jié)點分類的匿名流程

圖4是2度匿名圖,其中虛線為增加的邊。由此可知,邊緣節(jié)點1、2、3的原始社區(qū)數(shù)序列為(2,1,1),而進(jìn)行邊緣節(jié)點k匿名之后的度序列為(2,2,2),社區(qū)數(shù)都為3,是一個3度匿名序列,攻擊者就無法以高于1/3的概率來推斷出目標(biāo)社區(qū)和社區(qū)間關(guān)系。在社區(qū)內(nèi),如A社區(qū),原始的度序列為(1,3,3,3,2,1),度為2的節(jié)點只有一個,不滿足k度匿名條件,則在社區(qū)內(nèi)進(jìn)行節(jié)點選擇及邊的增加或者刪除操作,最后得到k度匿名序列(2,2,3,3,4,4)是一個2度匿名序列,整個社交網(wǎng)絡(luò)圖實現(xiàn)了2度匿名。

圖4 2度匿名示意圖

2.3 基于節(jié)點分類的匿名算法

一般的隱私保護(hù)方案是將整個社交網(wǎng)絡(luò)看作一個整體,需要不斷遍歷圖中的所有節(jié)點,對于節(jié)點并沒有區(qū)分其影響力和傳播力?？紤]到復(fù)雜網(wǎng)絡(luò)的“小世界”現(xiàn)象,引入社區(qū)這一概念,以區(qū)分不同節(jié)點的影響力,同時對劃分后的節(jié)點進(jìn)行分類,重要性不同的節(jié)點進(jìn)行不同程度的匿名保護(hù),并且在匿名過程中無需遍歷圖中的所有節(jié)點,社區(qū)內(nèi)節(jié)點的匿名只需搜索查找本社區(qū)內(nèi)其他節(jié)點即可,不同社區(qū)可同時進(jìn)行,大幅提高了算法的運行效率。

本文使用的節(jié)點匿名算法首先要將節(jié)點進(jìn)行社區(qū)劃分,然后分別進(jìn)行節(jié)點的匿名保護(hù),算法在執(zhí)行時會多次遍歷,通過改變k值可以增加匿名強(qiáng)度。

算法1節(jié)點分類k度匿名算法(K-Ca)

輸入G=(V,E),M={C1,C2,…,Cm},社區(qū)序列CNk,result

輸出匿名后的k度匿名圖G′=(V′,E′)

1.V←{v1,v2.…,vn},E←{(vi,vj)|i≠j},k←3,result←1

2.while result < k-1

3.for i←1 to m

4.x←v.neighbors?Cv(v∈Ci)

5.result←count(unique(x))sss

6.if result < k-1

7.select a node u?Ci

8.if G.edge(u,v)∈G

9.then reselect a node u

10.G.add edges(u,v)

11.end if

12.end if

13.end for

14.end while

15.for i←1 to m

16.while count(unique(cni))

17.for j←1 to length(Ci)

18.count deg(xi)

19.select a node y∈Ci

20.G.add edges(x,y)

21.end for

22.updateLi

23.end while

24.end for

在上述算法中,result用來記錄當(dāng)前邊緣節(jié)點的社區(qū)數(shù),初始化節(jié)點社區(qū)編號的時間復(fù)雜度為O(n),而后隨機(jī)選擇節(jié)點進(jìn)行社區(qū)數(shù)序列匿名,不斷在社區(qū)間進(jìn)行迭代操作,時間復(fù)雜度為O(ml)(m是社區(qū)個數(shù),l是邊緣節(jié)點個數(shù))。在一般情況下,ml比節(jié)點數(shù)n要大,因此該算法的時間復(fù)雜度為O(ml)。

2.4 信息損失和實用性度量

本文提出的匿名方法將原始圖G=(V,E)轉(zhuǎn)變?yōu)槟涿麍DG′=(V′,E′),節(jié)點集合V=V′,而邊集合E≠E′。節(jié)點分類k度匿名算法對邊的修改是動態(tài)的,對不滿足匿名條件的節(jié)點才會有選擇地進(jìn)行邊的增加或者刪除,因此,從邊的修改程度來衡量信息的損失度,通過計算圖G′和圖G中變化的邊的數(shù)目占原始圖G中邊的總數(shù)的比例來衡量數(shù)據(jù)的損失。計算公式如下:

(2)

基于信息損失度衡量數(shù)據(jù)實用性,信息損失值Loss(G)越大,數(shù)據(jù)實用性越低。

3 實驗結(jié)果與分析

本文通過實驗驗證社區(qū)劃分算法和匿名算法的準(zhǔn)確性并對其實驗結(jié)果進(jìn)行分析。所有實驗均在Windows10系統(tǒng)下完成,配置為16 GB的RAM和3.40 GHz的8核處理器。

3.1 數(shù)據(jù)集

本文主要使用兩個數(shù)據(jù)集:1)Football數(shù)據(jù)集,該數(shù)據(jù)集是由Girvan和Newman根據(jù)美國大學(xué)足球隊之間的關(guān)系收集整理得到,包含115個節(jié)點、613條邊;2)Facebook數(shù)據(jù)集,來源于 Stanford大學(xué)的一個公開數(shù)據(jù)庫SNAP[18],該數(shù)據(jù)集說明了Facebook社交網(wǎng)站上各用戶之間的關(guān)系,包含4 039個節(jié)點、88 234條邊。本文對數(shù)據(jù)集先做了預(yù)處理再進(jìn)行社區(qū)劃分,得到多個子圖的結(jié)構(gòu)數(shù)據(jù)。

3.2 結(jié)果分析

對于社交網(wǎng)絡(luò)中的數(shù)據(jù),在匿名隱私保護(hù)的同時需保證其實用性。為驗證本文匿名算法的正確性與有效性,通過計算邊的變化率來說明數(shù)據(jù)的信息損失度,若數(shù)據(jù)的信息損失度越小,則數(shù)據(jù)的實用性越好。另外,本文還考慮了圖結(jié)構(gòu)的一些基本屬性,主要測試指標(biāo)為度分布、聚類系數(shù)、介數(shù)中心性、最短路徑等[19-20]。將匿名前后的數(shù)據(jù)進(jìn)行對比,驗證本文提出匿名算法的正確性。

圖5對比分析了本文提出的節(jié)點分類k度匿名算法(K-Ca)和傳統(tǒng)k度匿名算法(K-Da)在匿名前后數(shù)據(jù)的信息損失度?？梢钥闯?兩種算法的數(shù)據(jù)損失度均較小,但是相比于K-Da算法,K-Ca算法具有更小的數(shù)據(jù)損失度(低于2%),數(shù)據(jù)實用性更高。

圖5 信息損失度

圖6展示了Facebook數(shù)據(jù)集匿名前后的度分布情況,original Graph表示原始圖。匿名前后的圖數(shù)據(jù)的度分布基本保持一致,說明本文算法最大程度保留了節(jié)點的連接關(guān)系。

圖6 Facebook數(shù)據(jù)集的度分布(k=3)

圖7展示了不同k值下社交網(wǎng)絡(luò)圖匿名前后的介數(shù)中心性變化結(jié)果。本文提出的K-Ca算法對介數(shù)中心性的影響小于K-Da算法,K-Da算法對圖的重構(gòu)嚴(yán)重影響了圖的結(jié)構(gòu),而K-Ca算法在匿名時從節(jié)點本身出發(fā)選取邊的操作引起的圖結(jié)構(gòu)變化非常小。由此可見,K-Ca算法實現(xiàn)匿名的同時最大化地保留了原始圖結(jié)構(gòu)。

圖7 介數(shù)中心性

圖8展示了社交網(wǎng)絡(luò)圖中節(jié)點之間最短路徑的均值變化。可以看出,隨著k值的增加,節(jié)點間的最短路徑都在減小,但是K-Da算法的路徑距離大于原始圖節(jié)點的最短距離,較大程度地影響了節(jié)點間的連接關(guān)系,造成節(jié)點與節(jié)點之間更稀疏,而本文的K-Ca算法縮短了路徑距離,可保持節(jié)點間的連接關(guān)系,并且由于對邊緣節(jié)點的連接關(guān)系的修改,使得源節(jié)點和目標(biāo)節(jié)點之間可以通過更少的節(jié)點進(jìn)行連通。

圖8 最短路徑距離

為更好地說明本文節(jié)點分類匿名算法具有更強(qiáng)的隱私保護(hù)力度,選取LPA快速社區(qū)劃分方法[21]對匿名后的圖數(shù)據(jù)進(jìn)行節(jié)點社區(qū)的重新劃分,判斷匿名前后社區(qū)劃分的結(jié)果是否一致,社區(qū)劃分后節(jié)點的社區(qū)關(guān)系是否發(fā)生變化。通過對比匿名前后的社區(qū)劃分結(jié)果發(fā)現(xiàn)經(jīng)過匿名后的圖在進(jìn)行社區(qū)劃分時社區(qū)內(nèi)的節(jié)點產(chǎn)生了變化,不再是固定的某些節(jié)點劃分到一個社區(qū)中。圖9對比了K-Da算法和K-Ca算法在匿名前后對社區(qū)的影響,K-Da算法只對度進(jìn)行了考慮,卻沒有考慮節(jié)點的社區(qū)結(jié)構(gòu),對節(jié)點的社區(qū)劃分影響較小,攻擊者根據(jù)社區(qū)關(guān)系成功識別節(jié)點和社區(qū)的概率非常大,從而說明K-Da算法對社區(qū)關(guān)系的影響大于K-Ca算法。k值越大,對社區(qū)的影響越大,使得攻擊者進(jìn)行社區(qū)劃分也不會得到原始的社區(qū)結(jié)構(gòu),從而說明攻擊者無法根據(jù)社區(qū)關(guān)系來識別節(jié)點或社區(qū),K-Ca算法對社區(qū)關(guān)系的保護(hù)更強(qiáng)于K-Da算法。

圖9 社區(qū)劃分變化

通過對比不同算法的運行時間來說明算法的時間復(fù)雜度。在圖 10中,當(dāng)k值較小時,K-Ca算法的運行時間低于K-Da算法,但是隨著k值的增加,K-Ca算法的運行時間開始快速增長,超過K-Da算法。由此可知,在一定的k值內(nèi),K-Ca算法優(yōu)于K-Da算法,但是在整體時間復(fù)雜度上,K-Ca算法的時間復(fù)雜度還是過高,導(dǎo)致效率過低,因此K-Ca算法的時間復(fù)雜度仍需做進(jìn)一步優(yōu)化。

圖10 運行時間對比

4 結(jié)束語

本文分析了傳統(tǒng)k度匿名算法中存在的問題并結(jié)合現(xiàn)有攻擊方法,提出基于節(jié)點分類的k度匿名隱私保護(hù)方法。通過引入社區(qū)這一概念,使節(jié)點分成邊緣節(jié)點和一般節(jié)點,將邊緣節(jié)點的社區(qū)序列匿名和社區(qū)內(nèi)節(jié)點的度匿名,從而完成整個社交網(wǎng)絡(luò)的k度匿名。匿名后的圖通過度和社區(qū)關(guān)系的保護(hù)加強(qiáng)匿名效果,同時提升了隱私保護(hù)強(qiáng)度。實驗結(jié)果表明,本文方法能有效地對數(shù)據(jù)進(jìn)行匿名保護(hù),并且能降低數(shù)據(jù)實用性損失,但在對數(shù)據(jù)進(jìn)行匿名保護(hù)時,算法時間復(fù)雜度過高,如何優(yōu)化本文K-Ca匿名算法的時間復(fù)雜度將是下一步研究的重要內(nèi)容。