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

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

0 概述

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

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

1 相關(guān)定義

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

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

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

(1)

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

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

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

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

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

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

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

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

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

2.1 攻擊模型

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

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

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

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

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

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

圖2 k度匿名流程

Fig.2 Procedure of implementing k degree anonymity

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

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

圖4 2度匿名示意圖

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

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

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

算法1節(jié)點(diǎn)分類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用來(lái)記錄當(dāng)前邊緣節(jié)點(diǎn)的社區(qū)數(shù),初始化節(jié)點(diǎn)社區(qū)編號(hào)的時(shí)間復(fù)雜度為O(n),而后隨機(jī)選擇節(jié)點(diǎn)進(jìn)行社區(qū)數(shù)序列匿名,不斷在社區(qū)間進(jìn)行迭代操作,時(shí)間復(fù)雜度為O(ml)(m是社區(qū)個(gè)數(shù),l是邊緣節(jié)點(diǎn)個(gè)數(shù))。在一般情況下,ml比節(jié)點(diǎn)數(shù)n要大,因此該算法的時(shí)間復(fù)雜度為O(ml)。

2.4 信息損失和實(shí)用性度量

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

(2)

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

3.2 結(jié)果分析

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

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

圖5 信息損失度

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

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

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

圖7 介數(shù)中心性

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

圖8 最短路徑距離

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

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

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

圖10 運(yùn)行時(shí)間對(duì)比

4 結(jié)束語(yǔ)

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