鄰居子圖擾動下的k-度匿名隱私保護模型

丁紅發,唐明麗,劉 海 ,蔣合領,傅培旺,于瑩瑩

(1.貴州財經大學 信息學院 貴州省大數據統計分析重點實驗室,貴州 貴陽 550025;2.貴安新區科創產業發展有限公司,貴州 貴陽 550025)

1 引 言

互聯網、移動物聯網的高速發展產生了社交網絡、移動軌跡、引文網絡、郵件網絡等海量圖結構數據,且被廣泛應用于學術研究、數據挖掘、廣告、商業決策支持、疾病傳播研究等領域[1]。此類圖數據在創造巨大社會價值和經濟價值的同時,還涉及大量個人隱私(如身份信息、政治傾向、個人喜好、地理位置等敏感信息),在共享、分析及應用圖數據過程中極易造成隱私泄露,引發了人們對隱私和安全的擔憂。例如,2019年,美國社交媒體臉書(Facebook)超5億用戶的個人數據泄露,其中包括電話號碼、電子郵件等;2022年7月,滴滴因個人軌跡信息、地圖信息等數據安全問題被罰80億人民幣,再次警示從事數據搜集、存儲、傳輸及使用的企業,應當增強數據隱私保護能力,直面圖數據存儲、使用中存在的安全問題,防范信息泄露風險。上述事件均表明社交網絡、個人軌跡等圖數據安全與隱私問題已成為當前社會一個亟待解決的重要問題。因此,研究圖結構數據的隱私保護模型與算法變得尤為重要。

大規模圖數據共享發布過程中,圖數據節點屬性和關系屬性兩類重要隱私信息易受到度信息攻擊、子圖攻擊及鏈接攻擊等結構化攻擊。簡單的匿名方法(例如,刪除圖數據節點的標識符)已經被認為是一種低效的匿名化機制[2],其無法可靠地保護節點的隱私。因此,隱私保護效果更好的各類匿名化隱私保護模型被相繼提出[3-4],以防止圖數據的隱私信息泄露,并防御針對圖數據隱私的惡意分析和提取攻擊。匿名化隱私保護模型通過將具有相同結構性質的節點數擴充至少k個,從而使得攻擊者對圖數據隱私節點的攻擊命中率降低至1/k以下,并且匿名化模型可分別從節點的度、子圖及節點標簽等屬性出發,對圖數據進行隱私保護[5-6]。另一種比較流行的圖數據隱私保護方法是差分隱私[7-10],其在實現過程中具有嚴格的數學理論證明。然而,差分隱私通常適用于發布圖數據的統計信息,無法實現精確的子圖模式匹配以及生成完整圖數據。此外,差分隱私的隱私保護效果往往依賴于經驗選擇一個較優的隱私預算,在實際應用中效果通常難以控制。相比于差分隱私,匿名化由于算法簡單、計算開銷低、隱私保護效果易控制等特性,已被廣泛用于各類商業應用中的圖數據隱私保護[11]。因此,研究匿名化圖數據隱私保護方法具有重要的理論和實踐意義。目前,實現圖數據匿名隱私保護的途徑主要有兩種:基于聚類的匿名化方法[12]和基于圖修改的匿名化方法[13]。

基于聚類的方法[12]是通過對圖的節點、邊或對兩者同時聚類,從而形成不可區分的匿名組。圖數據同一匿名組中的節點泛化后可聚類構成超節點,同一匿名組中的邊可聚類構成超邊,通過超點和超邊構成超圖從而保護待共享發布圖數據的隱私。YAZDANJUE等[14]提出了一種基于節點連接結構和屬性值的屬性圖聚類匿名化方法,綜合節點間的結構和屬性相似度,將社交網絡圖數據所有節點聚類成一些包含節點個數不小于k的超點;LANGARI等[15]提出了一種基于k成員模糊聚類和螢火蟲算法的組合匿名算法,使用模糊c均值來構建至少有k個成員的平衡聚類簇以保護匿名社交網絡圖數據不泄漏身份、屬性和鏈接隱私,并能抵抗相似性攻擊;HONG等[16]通過采用多維排序方案和基于貪婪分區的聚合技術設計了有向社交網絡數據的k度匿名模型。綜上所述,基于聚類的匿名方法通過聚類隱藏了超節點里面節點間的關系,能保護圖數據中的隱私信息,但該方法將使超節點內部的數據效用急劇下降,因此僅適用于不需要公開數據內部結構的大規模圖數據的場景。

基于圖修改的方法是通過修改圖數據中的部分節點和邊,實現對圖數據中隱私信息進行保護的匿名化技術。LIU等[13]提出了一種運用貪心策略增加邊和噪聲節點的方式來實現圖結構數據的k度匿名算法,使得任何節點均至少與其余k-1個節點度數相同,該方法在能夠抵御節點度攻擊的同時嚴重改變了圖數據的關系結構和連通性;隨后,LIU等[17]設計了一種基于新的度序列劃分算法的社交網絡數據發布隱私保護算法,該方法僅通過增邊和添加節點實現了k度匿名,但其信息損失過大; BAZGAN等[18]證明了利用不改變頂點/邊數的邊旋轉實現圖的k度匿名問題是非確定多項式(Non-deter ministic Pdynomido,NP)困難的; ZHOU等[19]提出了一種比k度匿名保護效果更強的隱私保護模型k鄰居匿名,除了對節點度數實現了k匿名,還對節點的鄰居結構實現了k匿名,但該方法不能抵抗子圖攻擊;CHENG等[20]提出了一種通過實現子圖間同構的圖數據k同構匿名方法,可抵御子圖匹配攻擊;此外,ZOU等[21]提出了基于圖自身同構的圖數據k同構匿名方法,也能抵御子圖匹配攻擊。k同構和k自同構方式實現了更強的隱私保護效果[22-23],但因其破壞圖數據的關系結構會造成巨大的信息損失,顯著降低了匿名后的數據效用。為了提高數據效用,LIANG等[24]將k匿名性定義為數學優化問題,試圖實現圖數據k匿名的同時最大化數據效用;SHAKEEL等[25]使用一種貪婪算法,在原始圖中插入最少數量的虛擬連接來實現防止共同朋友攻擊的k度匿名方法。綜上所述,基于圖修改的匿名方法使用增、刪節點和同構的方式實現k匿名,一定程度上增強了隱私保護效果,但存在信息損失較大和圖結構特性改變較大的問題。

為解決現有圖數據匿名隱私保護方法存在的隱私保護強度不足和信息損失較大的問題,文中提出一種基于鄰居子圖擾動的k度匿名隱私保護模型(k-Degree anonymity privacy protection model based on Neighborhood subgraph Disturbance,NDKD)。該模型利用最小化邊擾動機制實現每個節點的1-鄰居子圖擾動,提高該模型的抗隱私攻擊能力;采用分治法優化匿名組劃分,以減少對圖數據結構的改變從而提高數據效用;此外,該模型引入兩種新的圖匿名修改方法:邊緣添加和邊緣刪除,實現不增刪節點而生成k度匿名圖。通過上述措施,該模型能有效抵御1-鄰居子圖和節點度背景知識攻擊,仍然具有較好的數據效用和圖數據結構特性。具體而言,主要貢獻有:

(1) 提出了一種鄰居擾動后的k度匿名模型,通過改進鄰居匿名和度匿名算法,實現對1-鄰居子圖和節點度的背景知識攻擊的抵御。

(2) 改進了k度匿名算法,采用分治法優化匿名組的劃分,減少匿名過程中節點的信息損失。引入了新的圖匿名化操作方式:邊緣添加和邊緣刪除,在保持原始圖的節點數量條件下將圖數據重構成完全滿足k度匿名的匿名圖。

(3) 在Stanford Network Analysis Project(SNAP)真實數據集上對所提方案及相關k匿名方案進行實驗對比。結果表明,相較于傳統k匿名方案,文中所提匿名模型具有更優的數據效用,且圖結構特性改變更小。

2 相關定義

文中將圖數據建模為無向、無標簽、無加權的簡單圖G=(V,E),V表示圖G中所有節點的集合,E表示圖G中節點之間的關系集合,即邊的集合,且E=V×V。本節介紹圖數據發布匿名化隱私保護相關的概念和定義。

2.1 k度匿名

定義1(圖的k度匿名模型) 給定圖G=(V,E),?vi∈V,在V中至少存在k-1個不同于vi且與節點vi擁有相同度數的節點,則圖G滿足k度匿名。

k度匿名的圖G,滿足圖中任意節點與擁有相同度的其它節點,在度上不可區分,故節點的度攻擊對于k度匿名圖的命中率小于等于1/k。

定義2(遞減度序列) 若圖G=(V,E)中的節點集V=(v0,v1,…,vn-1)中所有節點按照遞減度的偏序關系排列,即dseq={d(vi)≥d(vi+1)|vi∈V,0≤i

2.2 k鄰居匿名

定義4(1-鄰居子圖) 圖G中節點v的1-鄰居子圖,定義為G中包括v在內的所有與v直接相連的節點,以及這些節點之間的所有邊構成的子圖,如圖1所示。圖1(b)為節點v在圖1(a)的1-鄰居子圖。

(a) 圖G

定義5(k鄰居匿名) 若圖G的任意一個節點vi∈V,在節點集V中至少存在k-1個不同于vi且與vi擁有相同1-鄰居子圖的節點,則圖G滿足k鄰居匿名。

定義6(邊的鄰接點) 給定圖G=(V,E),vi∈V,vj∈V。若V中存在節點v,使得e∈E,e∈E,則v稱為邊e的鄰接點。

3 NDKD隱私保護模型和算法設計

針對圖結構數據發布場景的隱私保護,文中提出了一種基于鄰居擾動的k度匿名的隱私保護模型NDKD。為便于理解,首先在節3.1描述所提NDKD隱私保護模型的具體框架,其次在節3.2闡述該模型框架中各步驟的算法原理。

3.1 NDKD隱私保護模型框架

所提NDKD隱私保護模型由鄰居擾動、度序列匿名和重構圖3個模塊構成,具體框架如圖2所示。在圖2中,NDKD隱私保護模型的3個模塊即匿名化隱私保護的3個核心環節,按照鄰居擾動、度序列匿名和重構圖的順序對原始圖數據進行處理。

圖2 NDKD匿名化隱私保護模型框架

(a) 原始圖數據

NDKD模型的基本思想是:① 對原始圖數據中的節點進行鄰居擾動,使得擾動后的圖數據不能被基于1-鄰居子圖的背景知識準確識別。同時,鄰居擾動保留了原始圖數據中大量節點的度值,即圖數據中的絕大多數節點的度值未發生變化,但是這也使鄰居擾動后的圖數據依然無法抵御節點度攻擊?；诖藛栴},對鄰居擾動的圖數據進行基于最大鄰居差劃分的k度匿名,結合匿名參數k,對鄰居擾動后的圖數據節點的遞減度序列進行處理,生成節點集的匿名組。② 按照匿名組中節點度對鄰居擾動后的圖數據進行圖修改操作,重構成k度匿名的圖數據,使得重構后的圖數據不能被基于節點度的背景知識準確識別。③ 將匿名后的圖數據進行共享發布。

該模型的3個模塊又分為若干個具體的步驟。鄰居擾動模塊首先將原始圖數據的節點集映射到節點的遞減度序列,遍歷遞減度序列中的節點,并找到與遍歷的節點有最多鄰居節點的另一節點;然后,改變兩個節點之間邊的狀態。重復上述操作,直至原始圖數據中每個節點的1-鄰居子圖都進行了擾動。度序列匿名模塊首先根據參數k的值,采用分治思想,找到每個度序列之間的最大鄰居差,用最大鄰居差值將節點度序列劃分為長度更小的度序列,直到所有的度序列的長度介于k-1至2k之間;其次,根據度序列匿名的信息損失,在最小信息損失的約束下,為每個度序列設置目標度,實現節點度序列的匿名化。重構圖模塊在增、刪和移邊操作的基礎上,進行邊緣添加和邊緣刪除操作,重構成匿名化的圖數據。

為了進一步提高對圖2所示的NDKD匿名化隱私保護模型框架的理解,圖3以一個具體的簡單圖為例,結合所提出的隱私保護模型框架,闡述實現匿名參數k為3時的匿名化隱私保護過程。

第1步,對原始圖數據進行鄰居擾動。首先,將原始圖數據(如圖3(a))節點的度按照遞減排序,遞減度序列為dseq=[6,5,4,4,4,3,2,2,2,1,1,0,0,0]。其次,對所有節點按照遞減度序列的順序進行鄰居擾動。最大度節點10的邊e<2,10>擁有3個鄰居節點,因此刪除邊e<2,10>。此時,1-鄰居子圖發生擾動的節點有5個,即節點2、節點4、節點5、節點7和節點10。排除這5個節點,繼續對剩下的節點進行擾動。擾動后,最終得到圖3(b),其中虛線代表刪除邊,粗線代表增加邊。由于度為0的節點僅能通過節點度進行匹配,因此鄰居擾動過程不對度為0的節點做處理。

第2步,對節點度序列進行匿名化。首先,采用分治法對圖3(b)的遞減度序列dseq=[5,5,4,4,3,3,3,3,2,2,2,0,0,0]進行劃分。具體而言,在遞減度序列的第3個數和倒數第3個數之間找到最大鄰居差值,并在最大鄰居差為2處對遞減度序列進行劃分,得到兩個度序列[5,5,4,4,3,3,3,3,2,2,2],[0,0,0]。對序列長度大于2×3-1的序列繼續進行上述操作,直至所有度序列均符合長度大于等于k且小于等于2k-1的條件,最后劃分的度序列為[5,5,4,4],[3,3,3,3],[2,2,2],[0,0,0]。其次,分別計算各劃分后的度序列的目標度,并賦值給各度序列,得到匿名組[4,4,4,4],[3,3,3,3],[2,2,2],[0,0,0]。

第3步,根據匿名組對擾動后的圖進行圖重構。根據前一步所得到的匿名組度數,對第1步所得到的擾動圖進行重構。具體而言,對圖3(b)中兩個度數為5的節點4和10減少其度數。如圖3(c)所示,這兩個度為5的節點之間存在邊,采用刪邊操作刪除邊e<4,10>,得到符合匿名組度數要求的圖,如圖3(d)所示。

經過上述基于鄰居子圖擾動的3度匿名化過程,圖3(a)中任意節點的1-鄰居子圖都無法在圖3(d)中進行匹配;匿名后的圖數據(如圖3(d))中的任意節點度都至少與其它2個節點度數相同,節點度的攻擊命中率降低到1/3以下。

3.2 NDKD隱私保護模型的算法設計

基于圖2中匿名隱私保護模型的3個模塊,設計實現核心功能的具體算法。節3.2.1提出鄰居擾動模塊中的節點1-鄰居子圖擾動算法,該算法確保每次擾動的邊所涉及的1-鄰居子圖包含盡可能多的節點,從而在滿足原始圖數據節點1-鄰居子圖擾動的前提下使得圖中擾動邊的數量最少。節3.2.2首先提出度序列匿名模塊中最大鄰居差劃分度序列步驟的算法和計算度序列的目標度步驟的計算公式,最大鄰居差劃分度序列算法通過分治法查找度序列的最大鄰居差來劃分度序列,避免同一度序列出現節點度的差值較大的情況。其次,對匿名組度數之和不為偶數時的操作進行了說明。節3.2.3提出重構圖模塊中的圖數據邊修改算法,利用增、刪和移邊以及邊緣添加、邊緣刪除生成匿名圖數據。

3.2.1 節點1-鄰居子圖擾動的算法

在對圖數據進行k度匿名之前,若存在圖數據或圖中大部分節點原本就滿足k度匿名的情況,則k度匿名后的圖數據的大部分節點會保留原始圖數據中的結構信息。根據定義1,k度匿名后的圖數據可以使攻擊者不能根據節點的度信息對某個節點進行唯一識別,但是攻擊者若掌握了某節點的1-鄰居子圖信息,則依然可以根據節點的1-鄰居子圖唯一識別該節點。因此,文中在k度匿名之前,對圖數據進行1-鄰居子圖的擾動,使得任意情況的圖數據在匿名之后,均無法被攻擊者所掌握的1-鄰居子圖信息唯一識別。

由定義4和定義6可知,若某條邊e在節點v的1-鄰居子圖中,那么節點v一定在邊e的鄰接點中。圖中的任意一條邊e的修改,都會改變e的鄰接點的1-鄰居子圖?；趫D數據的該特性,本節提出最少邊的數量改動的1-鄰居子圖的擾動方式。通過對每次計算得到的擁有最多鄰接點的邊進行擾動,保證在圖數據中任意節點的1-鄰居子圖至少有1條邊進行了擾動的前提下,擾動的邊數最少。具體如算法1所示。

算法1節點1-鄰居子圖擾動的算法。

輸入:原始圖數據G

輸出:鄰居擾動后的圖數據G′

① forviindseq：//dseq為圖G的節點集的遞減度序列

②vj=Search_Max_NNeighbor(vi)//vj為與節點vi有最多鄰居節點的節點,且i≠j

③ ife∈G

④ deletee

⑤ else:

⑥ adde

⑦ ife∈Gande∈G：//vm為滿足條件的所有節點

⑧ deleteNNeighbor[vi],NNeighbor[vj],NNeighbor[vm] //NNeighbor為G未修改1-鄰接子圖節點的鄰接矩陣

⑨ returnG′

算法1按圖G的遞減度序列進行遍歷,對所有節點的1-鄰居子圖的至少1條邊進行修改,直至所有V中所有節點的1-鄰居子圖都進行了修改。由于度為0的節點不具有1-鄰居子圖,因此此步驟中不考慮度為0的節點。在擾動完成后的圖中,原始圖數據中任意節點的1-鄰居子圖都無法進行匹配。算法1在進行鄰居擾動過程中會使部分節點的度值發生變化,造成圖數據的部分信息損失,但是該算法保證了進行擾動的邊盡可能地少,所以對算法2的匿名過程中數據效用損失的影響非常小。

對圖數據進行1-鄰居子圖擾動的過程中,若每次計算全圖中邊鄰接點數量,則會造成O(n3)的時間開銷比較大?？紤]到邊e的鄰接點數量等于邊兩端節點vi和vj的共同鄰接點數量,也就是說,若某條邊e的鄰接點數量較多,則該邊兩端節點vi和vj的共同鄰接點數量較多,而節點vi和vj的度數一定大于它們的共同鄰接點數量,所以,邊的端節點度數大是該邊擁有較多鄰接點的必要條件。從另一方面來看,較小度節點所在邊的鄰接點數量一定小于該節點的度,若從度數最小的節點開始遍歷,則每次擾動邊的的鄰接點數量較少,就會使得圖數據1-鄰居子圖擾動過程中擾動邊的數量過多,從而造成較大的數據效用損失。為了降低計算開銷,對于擁有最多鄰接點的邊的遍歷可以替換為最大度數節點的遍歷。綜上,在算法1中采用一種貪婪的算法,每次只對未擾動最大度的節點所在的邊進行計算。步驟①對節點的遞減度序列進行遍歷,遍歷的每個節點都是當前未擾動的最大度值的節點。步驟②是查找遍歷的節點vi擁有最多鄰接點的鄰邊。步驟①～②,使得每次擾動的邊,包含了盡可能多的節點,從而降低擾動邊的數量。步驟③～⑥,對vi、vj之間的邊的狀態進行擾動。步驟⑦～⑧,引入了圖G的鄰接矩陣NNeighbor,該鄰接矩陣記錄未擾動1-鄰居子圖的節點,并將發生擾動的節點從該矩陣刪除,避免對同一個節點的1-鄰居子圖重復擾動。重復上述操作,直至NNeighbor為空。最后返回鄰居擾動后的圖G′。

在算法1中,NNeighbor的大小從2m跳躍式地遞減,遞減速度受圖數據結構的影響,其中m為圖G=(V,E)中邊的數量。若NNeighbor從2m跳躍式地遞減到0需要a次,則遍歷次數為a,所以遍歷次數取決于NNeighbor的遞減速度。因此算法1的時間復雜度最好的情況為O(m),最壞的情況為O(m2),平均情況為O(m)。算法1的空間復雜度為O(m)。

3.2.2 最大鄰居差劃分度序列算法和計算度序列的目標度的方法

1) 最大鄰居差劃分度序列算法

在劃分匿名組的過程中,度序列的兩個鄰居之間的差異會影響劃分結果。例如,1個度序列dseq=[9,9,8,7,7,3,3,2,2],包含9個節點的度。鄰居差是指節點度的差值。若匿名參數k為4,則度數為7與度數為3的兩個相鄰節點的度差異最大為4。在最小信息變化量和匿名參數k的約束下,最優的匿名劃分為[9,9,8,7]和[3,3,2,2]。

度序列最大鄰居差的劃分采用了分治的思想,同時為了避免采用遞歸方法造成空間復雜度開銷過大的問題,算法2采用非遞歸方法實現,在O(n2)的時間復雜度內解決節點子序列的劃分問題。對整個節點集合V′子序列的劃分,等價于節點度遞減序列的劃分,將遞減度序列鄰居差異的劃分問題,分解為幾個匿名子序列劃分的問題。對于每個長度大于2k-1的匿名子序列,都可以劃分為兩個或兩個以上的子序列。因此,每次查找最大鄰居差需要在匿名序列的第k個元素和2k-1個元素內尋找。具體如算法2所示。

算法2最大鄰居差劃分度序列算法。

輸入:匿名參數k和圖G′的遞減度序列dseq

輸出:匿名序列劃分的最大鄰居差下標Neig_diff

①i=Max_Neig_Division(dseq,k)//k為匿名參數,i為dseq最大鄰居差節點的下標

② Neig_diff.append(0,i,n)//將最大鄰居差的節點的下標以及0,n添加到Neig_diff

③ while flag==True: //flag記錄下標之間是否還存在距離大于2k的情況

④ flag=False

⑤ forp,qin Neig_diff: //p,q為已記錄的最大鄰居差下標的兩個相鄰下標

⑥ ifq-p+1≥2k：

⑦i=Max_Neig_Division(p,q,k)

⑧ Neig_diff.append(i),flag=True

⑨ return Neig_diff

算法2中,首先將鄰居擾動之后的圖數據,按定義2進行節點度序列的降序排序。然后根據匿名化參數k和最大鄰居差,將圖G′劃分為滿足k匿名的度序列。該算法的劃分從全圖的度序列開始,避免了將鄰居差過大的節點劃分到同一匿名組,從而造成信息損失過大的問題。其次,該算法采用了非遞歸的算法,避免了遞歸方法中空間復雜度開銷過大的問題。

2) 計算度序列的目標度的方法

由于使用遍歷搜索來選擇匿名節點的目標度數對于大規模圖數據時間復雜度的開銷過大,因此文中使用一種貪婪的方法[28]來降低搜索的復雜性。該方法將度序列的節點平均值作為該序列的目標度,但是度序列的節點平均值可能不是整數,因此引入兩個值mj1,mj2。其中,mj1是節點集gj的度序列與屬于該組的所有節點度的平均值的差值的總和,使用下取整函數將平均值四舍五入。mj2以同樣的方式計算,但使用了上取整函數。mj1與mj2的計算方法由式(1)、式(2)給出:

(1)

(2)

然后,使用Pj1,Pj2分別來計算gj的目標度為〈gj〉下取整和上取整的概率。概率值越大,信息損失就越小,該值作為該節點集gj的目標度就越優。Pj1,Pj2的計算方法由公式(3)、式(4)給出:

(3)

(4)

其中,Pj1為匿名組gj使用均值下界作為目標度的概率,Pj2為匿名組gj使用均值上界作為目標度的概率。

為劃分好的度序列賦值目標度后得到匿名組。匿名后所有節點目標度的和必須是偶數,因為每條邊在度序列中被計數兩次。在匿名度序列劃分以及計算出各匿名組的目標度之后,如果出現圖的節點目標度之和為奇數的情況,則對劃分的匿名組進行回溯,找到擁有最小奇數差值的鄰居差值的匿名組gi,gj。在兩個匿名滿足式(5)的條件下,更改匿名組gi的最后一個節點放入gj中,或者將gj第1個節點放入gi中,實現最小信息損失的滿足匿名圖中節點度數必須為偶數的要求:

Min_Diff={min(d(vi)-d(vj))|i

((|gi|>k)∩|gj|<(2k-1))∪(|gi|<(2k-1)∩|gj|>k)} ,

(5)

其中,|gj|為匿名組gj的節點個數。

3.2.3 重構圖算法

圖G′的節點與其在匿名組中的關系有3種:① 節點vi小于其在匿名組v′i度數,即d(vi)d(v′i);③ 節點vi等于其在匿名組v′i度數,即d(vi)=d(v′i)。圖中任意邊的修改狀態由邊兩端的節點狀態共同決定。

對于原圖中邊的兩端節點度數同時大于或小于其在匿名序列中節點目標度的情況,采用刪邊和增邊,使其邊兩端節點度接近或達到其在匿名序列中的目標度,如圖4(a)所示。而對于邊的兩端節點d(vi)d(v′j)的情況,引入第3個節點vp,先刪除e之間的邊,再添加e之間的邊,也就是移邊。在移邊過程中第3個節點vp的度數不變。如圖4(b)所示,其中虛線邊代表刪除的邊,粗線代表增加的邊。

(a) 增邊、刪邊

需要注意的是,在重構簡單圖過程中,單個節點不能單獨增加邊;已存在邊的兩個節點不能再增加邊;不存在邊的兩個節點不能刪除邊。僅依靠增邊、刪邊和移邊3種方式,并不能保證圖G′能夠完全重構成滿足匿名序列節點的圖。例如,當圖重構過程中,可能出現僅剩的節點vi和vj之間不存在邊e,同時d(vi)>d(v′i)且d(vj)>d(v′j)時,則無法用刪邊或移邊策略。同理,在圖重構的過程中僅剩的節點vi和vj之間存在邊e,同時d(vi)

為了解決上述問題,在重構圖的過程中,引入另外兩個不同于節點vi和vj的節點vp和vq,并采用邊緣添加和邊緣刪除策略,如圖5所示。

(a) 邊緣添加

在采用邊緣添加和邊緣刪除時,需要避免某個節點匿名前后的度變化過大。因此,創建一個序列Change_d記錄每個節點匿名前后的度值變化的大小,并將序列按度值變化大小遞減排序。

算法3重構圖算法。

輸入:鄰居擾亂后的圖G′=(V′,E′)和匿名后度發生變化的節點集合Change_d

輸出:滿足鄰居子圖擾動下的k度匿名的圖G″=(V″,E″)

① forvi,vjin Change_d：

② ifd(vi)>d(v′i) andd(vj)>d(v′j):

③ deletee

④ ifd(vi)

⑤ adde

⑥ ifd(vi)>d(v′i) andd(vj)

⑦ deletee and adde

⑧ forvi,vjin Change_d：

⑨ ifd(vi)>d(v′i) andd(vj)>d(v′j):

⑩ ife∈E′ ande∈E′:

算法3中,步驟①對節點集合Change_d進行遍歷,按照匿名前后節點度改變量大小的順序對節點進行步驟②～⑦的增、刪和移邊的操作,消除了匿名前后度變化過大的節點,從而保證邊緣添加和邊緣刪除的匿名操作方式能生成完全滿足k匿名的圖。步驟⑧遍歷未達到匿名目標度的節點,步驟⑨～采用邊緣添加和邊緣刪除,對這些節點進行操作,在圖數據G′節點的數量上,完全重構成符合k度匿名的圖數據。

4 模型分析與實驗對比

首先將所提出的NDKD隱私模型與TSRAM[26]、NaFa4KDA[27]模型進行分析對比,從理論層面分析不同圖數據匿名隱私保護模型的差異;其次,利用Facebook、Wiki和Github真實數據集進行實驗,從匿名隱私保護算法對圖數據的邊變化、信息損失、節點平均度和聚類系數的影響進行對比,量化對比不同匿名隱私保護算法的效用與隱私影響。

4.1 模型分析

所提NDKD模型主要的空間開銷在鄰居擾動階段。該階段的時間開銷受圖數據邊的稀疏程度的影響,時間復雜度在最好情況下為O(m),在最壞情況下為O(m2),空間復雜度為O(m)。在度序列匿名階段和重構圖階段時間復雜度均為O(n2),空間復雜度為O(n)。

相較于傳統的k度匿名,文中所提出的NDKD模型增加了1個鄰居擾動模塊。該模塊會增加一定的時間開銷和空間開銷,但能進一步增加模型的抗隱私攻擊能力。此外,在度序列匿名階段和重構圖階段,所提模型采用的方法與另外兩種匿名模型均存在差異。在度序列匿名階段,NDKD采用最大鄰居差劃分匿名組;在重構圖階段,則引入兩種匿名化操作方式。具體對比如表1所示。

表1 不同k度匿名模型對比

由表1可知,NDKD、TSRAM和NaFa4KDA此3個不同的匿名隱私保護模型均實現了圖數據的度匿名隱私保護。然而,在時間和空間復雜度等計算開銷、度序列匿名和重構圖操作等匿名原理以及安全性方面,3個模型各有不同。

在計算開銷方面,NDKD模型相比于NaFa4KDA模型,時間復雜度從O(n2+mlogm)降低至O(m+n2);NDKD模型相比于TSRAM和NaFa4KDA模型,空間復雜度從O(l+n2)和O(n2)降低至O(m+n)。時間復雜度降低的主要原因是,NDKD模型采用分治法在O(n2)的時間內進行匿名組的劃分;空間復雜度降低的主要原因是,TSRAM和NaFa4KDA的主要開銷在圖重構階段,二者都采用了計算邊緣得分的方式來進行邊的修改,每次圖修改都要對兩個節點之間的邊緣的分進行計算,為了降低對圖數據結構特性的改變而增加了空間復雜度開銷;而NDKD模型采用了兩類圖修改操作模式來進行重構圖,不計算節點間的邊緣得分,降低了空間復雜度的開銷。NDKD模型的整體空間復雜度為O(m+n)。

在安全性方面,TSRAM和NaFa4KDA僅能抵抗節點度攻擊,而NDKD模型能同時抗節點度攻擊和1-鄰居子圖攻擊。這是由于NDKD模型采用了基于1-鄰居子圖擾動的邊擾動模式,擾亂了圖中節點的1-鄰居子圖,使得原始圖數據節點的1-鄰居子圖無法在鄰居擾動后的圖數據中進行匹配,同時對擾動后的圖數據進行了k度匿名隱私保護,提高了去匿名化攻擊的難度,增強了模型的隱私安全性。

4.2 實驗對比

為了評價所提NDKD模型的數據效用,將所提NDKD模型與TSRAM、 NaFa4KDA模型在真實圖數據集上進行實驗來對比算法性能。實驗數據集選取SNAP上3個公開數據集,分別是Facebook、Wiki和Github,3者均為無向無權簡單圖。表2中給出了所選數據集的主要特征。將分別在k取值為10、20、30、40、50、60、70、80、90和100時[13,28-29],對比所提NDKD模型與TSRAM、NaFa4KDA模型的度量效用。文中實驗均在11th Gen Intel(R) Core(TM) i5-11400H @ 2.70 GHz 2.69 GHz、16 GB RAM和Windows 11上進行測試,通過Python3.10實現。

表2 數據集特征

4.2.1 圖屬性度量實驗分析

從邊數變化的百分比、圖中節點的信息損失量和圖中節點平均度的變化這3個圖數據屬性指標對NDKD模型與TSRAM和NaFa4KDA模型進行效用對比。其中,邊變化百分比反映了匿名過程中原始圖數據中任意兩個節點之間的結構變化;信息損失量通過計算各個節點匿名前后度的差值,衡量了對原始圖數據的影響程度;網絡節點平均度衡量了匿名前后圖的整體節點度的變化程度。從數據效用方面看,匿名隱私保護模型對圖數據的這3個屬性指標的影響越小,隱私保護模型的數據效用越高。

不同匿名隱私保護模型作用在圖數據上,邊數變化百分比的對比結果如圖6所示。由圖6可知,在Facebook數據集中,TSRAM模型使得匿名隱私保護后的圖數據邊變化百分比最大,NaFa4KDA模型其次,NDKD模型的邊數變化百分比最小。特別是,當k值在10～60區間時,NDKD模型具有明顯的數據效用優勢,相比于TSRAM和NaFa4KDA模型的邊數變化百分比分別降低了26.84%和5.60%。同樣地,在Wiki數據集中,邊數變化分別降低30.21%和32.11%;在Github數據集中,NDKD模型的邊數變化百分比同樣最小,邊數變化分別降低8.37%、9.46%。

(a) Facebook圖數據

不同匿名隱私保護模型作用在圖數據上,信息損失的對比結果如圖7所示。由圖7可知,對比結果與圖6保持一致。在Facebook數據集中,TSRAM模型的信息損失最大,NDKD模型的信息損失最小,NDKD模型與TSRAM和NaFa4KDA模型相比,信息損失分別降低了29.24%和6.60%;在Wiki數據集中,NDKD模型與TSRAM和NaFa4KDA模型相比,信息損失分別降低34.14%和39.72%;在Github數據集上的實驗結果也相對一致,NDKD模型的信息損失最小,與TSRAM和NaFa4KDA模型相比分別降低了 4.74% 和11.85%的信息損失。圖8與圖7的結果保持一致的原因是,圖數據的信息損失是基于邊的變化量計算得到的,兩個屬性值相關性較高。

(a) Facebook圖數據

(a) Facebook圖數據

在圖6和圖7中,NDKD模型能夠保持較小的邊數變化量和信息損失,是因為基于最大鄰居差值的匿名序列劃分避免了擁有較大差值的節點分到同一個匿名組,而造成過大信息損失的問題。TSRAM算法通過度序列構建樹劃分匿名組,在不斷合并最佳鄰居分組時,會產生額外的信息損失,而導致發生變化邊的數量增多。在Wiki數據集中,節點度數的差異更大,導致NDKD的優勢更加明顯。在Github數據集中,由于數據集的節點平均度數較小,導致NDKD中鄰居擾動步驟的邊數變化和信息損失有所增加,這導致NDKD在邊數變化和信息損失方面的優勢有所降低。

不同匿名隱私保護模型作用在圖數據上,平均節點度變化的對比結果如圖8所示。由圖8可知,在Facebook、Wiki和Github這3個數據集中,相同的k值情況下,NDKD模型的平均節點度變化值都要顯著低于TSRAM和NaFa4KDA模型,說明NDKD模型作用于圖數據上時,保留了原始圖數據更多的節點度信息相關的數據效用。具體而言,在Facebook數據集中,NDKD模型與TSRAM和NaFa4KDA模型相比,節點平均度的變化分別降低77.74%和79.67%;在Wiki數據集中,節點平均度的變化分別降低86.53%和88.12%;在Github數據集中,節點平均度的變化分別降低29.67%和52.27%。

在圖8中,NDKD模型能夠保留更多原始圖數據的節點度數據效用的原因是,NDKD模型在匿名組劃分的過程中利用最大鄰居差劃分度序列的方法,避免了同一匿名組出現較大的度差值,進而在圖數據重構階段進行的圖修改過程對節點度的影響降低,使得圖數據節點保持較低的節點平均度數變化。

4.2.2 平均聚類系數度量實驗分析

為了進一步分析不同匿名隱私保護模型對圖數據結構數據效用的影響,本節通過對比匿名模型作用于圖數據前后對圖數據聚類系數的變化影響,以分析不同匿名隱私保護算法的數據效用。

不同匿名隱私保護模型作用在圖數據上,平均聚類系數變化的對比結果如圖9所示。由圖9可知,在Facebook數據集中,當k值在10～30之間時,NDKD模型的平均聚類系數變化量小,當k值大于30,3種匿名方法所造成的聚類系數變化趨向于相同,都保持了較小的平均聚類系數的變化;在Wiki數據集和Github數據集中,由于數據集的規模的增大,NDKD模型在保持圖數據結構數據效用方面的優勢顯著,相比于TSRAM和NaFa4KDA模型,該模型的平均聚類系數變化顯著降低?？傮w而言,NDKD模型保留圖數據的結構性數據效用顯著提升。與TSRAM和NaFa4KDA模型相比,在Facebook數據集中,NDKD模型的平均聚類系數變化分別降低了3.45%和1.75%;在Wiki數據集中,分別降低2.86%和62.64%;在Github數據集中,分別降低了38.46%和38.46%。

(a) Facebook圖數據

NDKD模型能顯著提升圖數據的結構性數據效用的原因是,文中提出的匿名組劃分方式比TSRAM的度序列構建樹和NaFa4KDA的匿名組劃分方式造成的信息損失更小,從而保留了更多的數據效用。在此基礎上,NDKD進行的邊緣添加和邊緣刪除的匿名操作方式相比增加噪音節點圖修改的方式,對圖數據結構關系造成的影響更小。

5 結束語

匿名隱私保護模型在圖數據共享發布場景中有著廣泛的應用。而現有的匿名隱私保護模型無法均衡圖數據的隱私保護和數據效用沖突。文中基于鄰居子圖擾動提出一種高安全強度的k度匿名隱私保護模型,該模型通過鄰居子圖擾動算法以及度序列的匿名化算法,實現了對基于1-鄰居子圖和節點度的背景知識攻擊的防御。同時,該模型采用最大鄰居差劃分匿名組并利用圖修改操作重構圖數據,降低了匿名化圖數據的信息損失,提升了匿名圖數據的數據效用。相比于已有的圖數據k度匿名隱私保護模型,所提模型計算效率和安全性方面有了大幅度提升,同時在圖數據的屬性效用和結構效用方面也有了顯著提升。