基于節點分類的k度匿名隱私保護方法

金 葉,丁曉波,龔國強,呂 科

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

0 概述

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

在傳統k度匿名保護方法中,匿名算法雖然能快速構建出一個滿足k度序列的社交網絡圖,但是因為對圖進行重構,在很大程度上造成了圖結構的損壞,節點間的結構關系受到嚴重破壞,并且該方法在攻擊者只擁有節點的度這一先驗知識時是具有保護效用的,但當攻擊者擁有更強的先驗知識時,如節點的一跳鄰居結構、節點的社區關系等信息,k度匿名保護方法則無法抵抗這些攻擊。本文提出一種改進的k度匿名保護方法,從節點本身出發優化節點的度及圖的結構。

1 相關定義

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

對一個原始的社交網絡圖數據,本文首先對其進行預處理,將節點劃分到不同的社區中,并采用模塊度這一概念判斷當前節點劃分的有效性。

定義1(模塊度) 模塊度又稱模塊化度量值,是一種常用的衡量網絡社區結構強度的方法[15]。式(1)為模塊度的數學表達式:

(1)

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

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

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

根據邊緣節點的定義可知,多個社區之間通過不同邊緣節點連接,一個邊緣節點可能與多個社區存在連接關系,統計該邊緣節點所連的社區號,則可以得到各個社區的連接關系。

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

由定義3可知,邊緣節點的社區數其實也是邊緣節點的度,與度不相同的是這些節點所連的社區之間的關系不同,對這些社區數匿名就相當于對社區關系匿名。

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

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

2 基于節點分類的隱私保護方法

2.1 攻擊模型

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

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

圖1 社區關系攻擊示意圖

2.2 基于節點分類的k度匿名保護模型

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

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

圖2 k度匿名流程

Fig.2 Procedure of implementing k degree anonymity

圖3 基于節點分類的匿名流程

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

圖4 2度匿名示意圖

2.3 基于節點分類的匿名算法

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

本文使用的節點匿名算法首先要將節點進行社區劃分,然后分別進行節點的匿名保護,算法在執行時會多次遍歷,通過改變k值可以增加匿名強度。

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

輸入G=(V,E),M={C1,C2,…,Cm},社區序列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用來記錄當前邊緣節點的社區數,初始化節點社區編號的時間復雜度為O(n),而后隨機選擇節點進行社區數序列匿名,不斷在社區間進行迭代操作,時間復雜度為O(ml)(m是社區個數,l是邊緣節點個數)。在一般情況下,ml比節點數n要大,因此該算法的時間復雜度為O(ml)。

2.4 信息損失和實用性度量

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

(2)

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

3 實驗結果與分析

本文通過實驗驗證社區劃分算法和匿名算法的準確性并對其實驗結果進行分析。所有實驗均在Windows10系統下完成,配置為16 GB的RAM和3.40 GHz的8核處理器。

3.1 數據集

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

3.2 結果分析

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

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

圖5 信息損失度

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

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

圖7展示了不同k值下社交網絡圖匿名前后的介數中心性變化結果。本文提出的K-Ca算法對介數中心性的影響小于K-Da算法,K-Da算法對圖的重構嚴重影響了圖的結構,而K-Ca算法在匿名時從節點本身出發選取邊的操作引起的圖結構變化非常小。由此可見,K-Ca算法實現匿名的同時最大化地保留了原始圖結構。

圖7 介數中心性

圖8展示了社交網絡圖中節點之間最短路徑的均值變化?？梢钥闯?隨著k值的增加,節點間的最短路徑都在減小,但是K-Da算法的路徑距離大于原始圖節點的最短距離,較大程度地影響了節點間的連接關系,造成節點與節點之間更稀疏,而本文的K-Ca算法縮短了路徑距離,可保持節點間的連接關系,并且由于對邊緣節點的連接關系的修改,使得源節點和目標節點之間可以通過更少的節點進行連通。

圖8 最短路徑距離

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

圖9 社區劃分變化

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

圖10 運行時間對比

4 結束語

本文分析了傳統k度匿名算法中存在的問題并結合現有攻擊方法,提出基于節點分類的k度匿名隱私保護方法。通過引入社區這一概念,使節點分成邊緣節點和一般節點,將邊緣節點的社區序列匿名和社區內節點的度匿名,從而完成整個社交網絡的k度匿名。匿名后的圖通過度和社區關系的保護加強匿名效果,同時提升了隱私保護強度。實驗結果表明,本文方法能有效地對數據進行匿名保護,并且能降低數據實用性損失,但在對數據進行匿名保護時,算法時間復雜度過高,如何優化本文K-Ca匿名算法的時間復雜度將是下一步研究的重要內容。