改進的k 度匿名圖構(gòu)造算法①

曾 滔

(華南師范大學(xué) 計算機學(xué)院, 廣州 510631)

1 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展, 在線社交網(wǎng)絡(luò)在全世界普及, 社交網(wǎng)絡(luò)的運營商收集了大量用戶數(shù)據(jù), 如果通過簡單的匿名化處理將用戶數(shù)據(jù)提供給第三方(研究人員、市場營銷等)使用, 就會出現(xiàn)隱私泄漏的風(fēng)險[1,2].因此, 社交網(wǎng)絡(luò)的隱私安全越來越受到人們的關(guān)注, 運營商需要在發(fā)布數(shù)據(jù)之前, 對用戶數(shù)據(jù)進行匿名化處理, 確保用戶隱私不會泄漏[3]; 同時盡可能地保留社交網(wǎng)絡(luò)的結(jié)構(gòu)特性, 從而保證數(shù)據(jù)的實用性[4,5].

基于圖結(jié)構(gòu)變換的匿名方法[6], 能夠有效地解決社交網(wǎng)絡(luò)中用戶的隱私保護問題. Backstrom 等人[7]指出使用無意義的唯一標(biāo)識符替換用戶的身份作匿名化處理, 并不能防止用戶隱私泄漏. Hay 等人[8]發(fā)現(xiàn)利用節(jié)點周圍的結(jié)構(gòu)信息仍然能夠在匿名圖中重新識別該節(jié)點, 這種結(jié)構(gòu)信息與節(jié)點及其鄰居節(jié)點的度有關(guān). Liu 等人[9]基于k匿名性, 提出了k度匿名化模型, 這種匿名保護能夠有效抵御以節(jié)點度數(shù)為背景知識的隱私攻擊,使得每個節(jié)點被重新識別的概率不大于1 /k.

針對k度匿名化問題, Liu 等人[9]基于動態(tài)規(guī)劃思想生成匿名度序列, 根據(jù)該序列通過添加邊的方式去構(gòu)建圖, 由于構(gòu)圖操作并不能保證一定成圖, 所以需要構(gòu)圖測試, 這會增加算法運行時間; 而且構(gòu)圖操作的隨機過程導(dǎo)致原圖結(jié)構(gòu)信息的損失. Lu 等人[10]提出了一種貪心匿名化算法, 在給原圖添加邊的同時進行度序列的匿名化, 直接在原圖上進行加邊能夠避免度序列的構(gòu)圖測試, 但是同步匿名化需要添加較多的邊來實現(xiàn)圖匿名化.

Chester 等人[11,12]提出了加點的匿名化策略, 基于動態(tài)規(guī)劃思想生成匿名度序列, 通過新節(jié)點與原圖節(jié)點連邊滿足節(jié)點匿名要求, 然而加點太多導(dǎo)致原圖結(jié)構(gòu)信息的損失. Ma 等人[13]結(jié)合加邊且可加點的匿名化策略提出匿名化算法, 利用貪心法生成匿名度序列, 并基于社區(qū)結(jié)構(gòu)進行加邊, 這種匿名化方式能較好地保留圖的某些結(jié)構(gòu)特性, 但添加的邊或節(jié)點數(shù)較多. 吳童[14]結(jié)合加邊且可加點的匿名化策略提出了改進算法, 利用Liu 等人[9]提出的動態(tài)規(guī)劃匿名分組算法生成匿名度序列, 根據(jù)該序列貪心加邊; 若加邊不能完成匿名化,則進行加點完成圖匿名化. 由于未充分利用原圖中的點進行加邊, 導(dǎo)致添加的節(jié)點數(shù)較多. Rajabzadeh 等人[15]利用Ma 等人[13]提出的貪心分組算法和基于模塊度的社區(qū)發(fā)現(xiàn)算法[16]確定每個社區(qū)內(nèi)節(jié)點的匿名化代價, 然后通過遺傳算法決定每個社區(qū)內(nèi)的節(jié)點之間如何連邊, 從而實現(xiàn)圖的度匿名化. 本文的主要貢獻包括:

(1) 結(jié)合加邊且可加點的策略, 改進了匿名化方式,分兩個階段進行加邊, 這種匿名方式能有效減少添加的邊或節(jié)點.

(2) 在加邊操作中, 考慮節(jié)點度、社區(qū)結(jié)構(gòu)和節(jié)點距離等因素選擇目標(biāo)節(jié)點進行連邊, 這種操作能夠有效保留原圖的某些結(jié)構(gòu)特性.

(3) 在多個真實數(shù)據(jù)集上進行了大量實驗, 實驗結(jié)果驗證了新算法的有效性.

2 預(yù)備知識

給定無向圖G和正整數(shù)k(δG≤k≤ΔG), 當(dāng)且僅當(dāng)圖中每個節(jié)點至少與k-1 個其他節(jié)點具有相同的度, 則稱圖G是k度匿名圖, 其度序列稱為k度匿名度序列.

設(shè)圖G不是k度匿名圖, 通過在圖G中添加邊得到新圖G′, 使得G′是k度匿名圖, 稱序列dG′ ={dG′(v1),···,dG′(vn)} 為 圖G′的k度匿名度序列. 令dCost={dG′(v1)-dG(v1),···,dG′(vn)-dG(vn)}為匿名代價序列. 為了方便操作, 不妨假設(shè)匿名代價序列為非遞增序列, 其中,dG′(vi)-dG(vi) 表示節(jié)點vi的匿名化代價.

圖匿名問題可描述如下: 給定無向圖G和正整數(shù)k(δG≤k≤ΔG), 構(gòu)造圖G的k度匿名圖G′滿足G?G′,且使得diff(M(G),M(G′)) 可能小. 其中,M(G)表 示圖G的某個結(jié)構(gòu)特性(平均路徑長度等), 而diff(M(G),M(G′))表示兩個圖在某個結(jié)構(gòu)特性上的差異程度. 即要求圖G的k度匿名圖G′滿足minG?G′diff(M(G),M(G′)). 由于圖的結(jié)構(gòu)特性的多樣性, 本文將圖的3 種典型的結(jié)構(gòu)特性(平均路徑長度、平均聚類系數(shù)、傳遞系數(shù))作為匿名效果的度量指標(biāo), 使得匿名圖與原圖在這3 種結(jié)構(gòu)特性上的差異盡可能小.

3 算法模型

新算法包括如下子算法: 匿名分組算法、加邊算法、加點算法、層次社區(qū)發(fā)現(xiàn)算法. 新算法思想是利用貪心匿名分組算法生成匿名度序列, 基于層次社區(qū)結(jié)構(gòu)加邊, 優(yōu)先滿足匿名代價大于平均匿名代價的節(jié)點的匿名要求; 然后再次利用貪心匿名分組算法得到匿名度序列, 通過同樣的加邊操作滿足未匿名節(jié)點的匿名要求;若加邊不能完成匿名化, 則通過加點實現(xiàn)圖匿名化.

3.1 匿名分組算法

本文采用Liu 等人[9]提出的貪心匿名分組算法, 首先形成一個包含前k個最高度節(jié)點的組, 并把組內(nèi)節(jié)點的度賦值為dG(v1) , 然后考慮兩個匿名代價Cmerge和Cnew, 計算公式如下:

通過該算法得到匿名度序列, 每個組中至少有k個度相同的節(jié)點, 滿足k匿名性原則.

3.2 加邊算法

加邊算法包括兩個階段: 優(yōu)先加邊和普通加邊. 優(yōu)先加邊階段盡量滿足匿名代價大于平均匿名代價的節(jié)點的匿名要求, 按照匿名代價降序遍歷節(jié)點, 基于層次社區(qū)結(jié)構(gòu)選擇目標(biāo)節(jié)點進行連邊, 每次加邊操作更新匿名代價序列. 在加邊操作中, 從當(dāng)前節(jié)點所在的社區(qū)開始遍歷, 考慮兩類節(jié)點: 1)節(jié)點度比當(dāng)前節(jié)點度小;2)節(jié)點度比當(dāng)前節(jié)點度大且匿名代價大于0. 將符合條件的節(jié)點標(biāo)識為目標(biāo)節(jié)點, 并優(yōu)先選擇與當(dāng)前節(jié)點距離近的目標(biāo)節(jié)點進行連邊. 若標(biāo)記的目標(biāo)節(jié)點數(shù)仍不能滿足當(dāng)前節(jié)點的匿名要求, 則向高級別社區(qū)遍歷,找到足夠多的目標(biāo)節(jié)點進行連邊.

算法 1. 優(yōu)先加邊算法(pre_edges_addition)輸入: 圖 , 匿名代價序列 , 層次社區(qū)L輸出: 圖G'G dCost 1. initialize //目標(biāo)節(jié)點集合vertex v {v|dCost(v)＞avg_cost,v∈V}T=? 2. FOR in DO C←find_community(L,v)3.4. FOR DO FOR node n∈V DO community c∈C 5. //選擇目標(biāo)節(jié)點n∈c∧n?T ∧n≠v ∧(n,v)?E 6. IF THEN dG(n)＜dG(v)7. IF THEN T←T∪{n}8.

9. ELSE IF THEN T←T∪{n}dG(n)＞dG(v)∧dCost(n)＞0 10.11. END IF 12. END IF 13. END FOR|T|≥dCost(v)14. IF THEN 15. BREAK//目標(biāo)節(jié)點數(shù)滿足當(dāng)前節(jié)點匿名要求16. END IF 17. END FOR T path(Ti,v),i∈(0,|T|)∞18. sort according to the shortest in the ascending order//若節(jié)點不可達, 則距離為dCost(v)＞0 ∧|T|＞0 19. WHILE DO//加邊操作E∪{(Ti,v)},i∈(0,|T|)20.21.T←TTi 22.23. END WHILE dCost(v)←dCost(v)-1

再次通過貪心匿名分組得到匿名度序列, 普通加邊階段根據(jù)該序列盡量滿足所有節(jié)點的匿名要求. 采用與優(yōu)先加邊階段同樣的加邊操作, 僅考慮匿名代價大于0 的節(jié)點, 并優(yōu)先選擇與當(dāng)前節(jié)點距離近的目標(biāo)節(jié)點進行連邊.

蘇教版第六冊《我應(yīng)該感到自豪才對》這篇課文中有這么一句話：“第二天，小駱駝跟著媽媽走進了茫茫的大沙漠?！?/p>

算法 2. 普通加邊算法(edges_addition)G′ dCost L輸入: 圖 , 匿名代價序列 , 層次社區(qū)輸出: 圖G'', 匿名代價序列d′Cost 1. initialize //目標(biāo)節(jié)點集合vertex v {v|dCost(v)＞0,v∈V}T=? 2. FOR in DO C←find_community(L,v)3.4. FOR DO node n {n|dCost(n)＞0,n∈V}community c∈C 5. FOR in DO n∈c∧n?T ∧n≠v ∧(n,v)?E 6. IF THEN T←T∪{n}7.8. END IF 9. END FOR···10. //省略部分參考算法1 11. END FOR G′′,d′Cost 12. RETURN

3.3 層次社區(qū)發(fā)現(xiàn)算法

圖1 層次化社區(qū)樹

算法 3. 層次社區(qū)發(fā)現(xiàn)算法(find_community)輸入: 層次社區(qū) , 當(dāng)前節(jié)點v C L v輸出: 包含 的層次社區(qū)1. initialize hierarchy_community hc∈L C=? 2. FOR DO community c∈hc 3. FOR DO v∈c 4. IF THEN C∪{c}5.6. BREAK 7. END IF 8. END FOR 9. END FOR C∪{V}10. //添加最高級別社區(qū)C 11. RETURN

3.4 圖匿名化算法

圖匿名化算法整合如下算法: 匿名分組算法、層次社區(qū)發(fā)現(xiàn)算法、加邊算法和加點算法, 原圖經(jīng)過加邊和加點操作生成滿足k度匿名化的圖.

算法 4. 圖匿名化算法(graph_anonymization)輸入: 圖 , 參數(shù)G(V,E) k G′′′輸出: 匿名圖1.L←G.community_multilevel(return_level←T)2.G′←pre_edges_addition(G,dCost,L)3.dCost←anonymize_partition(G′,k)4.G′′,d′Cost←edges_addition(G′,dCost,L)5.{v|d′Cost(v)＞0,v∈V}≠? 6. IF THEN//是否加點G′′′←nodes_addition(G′′,d′Cost,k)7.dCost←anonymize_partition(G,k)8. END IF G′′′←G′′9.G′′′10. RETURN

對于一些特殊情況, 新算法僅通過加邊無法滿足節(jié)點匿名化要求. 所以, 通過Chester 等人[11,12]提出的加點算法, 將原圖中未匿名的節(jié)點依次與新節(jié)點相連來滿足節(jié)點的匿名化要求; 同時, 新節(jié)點也需要進行匿名化處理, 并最終實現(xiàn)圖的匿名化. 新節(jié)點個數(shù)m滿足如下關(guān)系,mc表示節(jié)點的最大匿名代價.

3.5 算法復(fù)雜性分析

Liu 等人[9]提出的貪心匿名分組算法的時間復(fù)雜度為 O (nk). 由匿名分組算法確定的未匿名節(jié)點個數(shù)不會超過 (n-n/k),n/k表示匿名分組數(shù). 優(yōu)先加邊算法的時間復(fù)雜度為 O (lmn),l表 示層次化社區(qū)樹的高度,m表示匿名代價大于平均匿名代價的節(jié)點個數(shù); 當(dāng)節(jié)點匿名代價很大時, 可能需要遍歷全圖尋找目標(biāo)節(jié)點. 普通加邊算法的時間復(fù)雜度為 O ((n-n/k)×l×mc), 雖然此階段需要匿名處理的節(jié)點數(shù)較多, 但是節(jié)點最大匿名代價mc較 小,mc?n. Louvain 算法[16]的時間復(fù)雜度是線性階的, 層次社區(qū)發(fā)現(xiàn)算法的時間復(fù)雜度也是線性階的. 通過Floyed 算法[19]計算所有節(jié)點的路徑長度,將其輸出作為算法輸入, 該時間復(fù)雜度為 O (n3). 因此,新算法的時間復(fù)雜度為O (n2).

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

實驗環(huán)境為Windows 10 專業(yè)版, 運行環(huán)境采用PyCharm 2020 (Python 語言), PC 機主頻3.6 GHz, 內(nèi)存8 GB. 新算法命名為KDVEM21, 在5 個真實數(shù)據(jù)集上進行實驗, 同5 個經(jīng)典算法比較, 對比算法僅包含加邊或加點的多項式時間復(fù)雜度算法: 包括Priority 算法[9]、FKDA 算法[10]、V_ADD 算法[11,12]、KDVEM15 算法[13]和KDVEM18 算法[14], 分別從匿名效果和匿名代價兩個方面評估算法的性能, 并對實驗結(jié)果進行分析.

4.1 數(shù)據(jù)集描述

本文實驗數(shù)據(jù)采用斯坦福大學(xué)提供的公開數(shù)據(jù)集(SNAP), 表1 給出了數(shù)據(jù)集的詳細介紹, 實驗數(shù)據(jù)集都是無向的、簡單的、無標(biāo)記的.

表1 數(shù)據(jù)集描述

4.2 評價方法

徐恪等人[20]概述了典型的社交網(wǎng)絡(luò)拓撲參數(shù), Ji等人[21]討論了圖數(shù)據(jù)匿名化的研究演變和匿名度量的有效性, Zhao 等人[22]指出組合多個度量指標(biāo)作為隱私度量更具可比性, 趙蕙等人[23]認(rèn)為社交網(wǎng)絡(luò)匿名化度量方法的多樣和復(fù)雜, 匿名算法研究者難以找到合適的方法評估自己的創(chuàng)新研究. 因此, 實驗采用典型的3 個圖的結(jié)構(gòu)特性作為匿名效果的度量指標(biāo).

(1) 平均路徑長度(average path length)

平均路徑長度計算公式如下,SPL是節(jié)點u和v之間的最短距離,CP表示所有可連接的節(jié)點對.

4.3 結(jié)果分析

實驗參數(shù)k的取值范圍{5, 10, 15, 20, 25, 50}, 在復(fù)現(xiàn)Priority 算法時, 構(gòu)圖操作中采用了隨機選點的策略,因而在每個參數(shù)上運算10 次取平均值作為實驗結(jié)果.V_ADD 算法和KDVEM15 算法由作者提供源代碼. 將實驗結(jié)果繪制成點線圖, 其中, 橫軸表示參數(shù)k, 縱軸表示度量指標(biāo)的取值范圍. 水平線表示原圖的度量指標(biāo),其余分別表示對比算法在對應(yīng)參數(shù)下輸出匿名圖結(jié)構(gòu)特性的度量指標(biāo). 圖2-圖6 分別表示各個真實數(shù)據(jù)集在對應(yīng)參數(shù)k生成匿名圖的結(jié)構(gòu)特性.

圖2 ca-GrQc 數(shù)據(jù)集上匿名圖的結(jié)構(gòu)特性

圖3 ca-HepTh 數(shù)據(jù)集上匿名圖的結(jié)構(gòu)特性

圖6 ca-CondMat 數(shù)據(jù)集上匿名圖的結(jié)構(gòu)特性

圖4 ca-HepPh 數(shù)據(jù)集上匿名圖的結(jié)構(gòu)特性

圖5 ca-AstroPh 數(shù)據(jù)集上匿名圖的結(jié)構(gòu)特性

Rajabzadeh 等人[15]認(rèn)為3 個度量指標(biāo)具有同等的重要性, 取3 個度量指標(biāo)的平均值作為算法的綜合評價. 隨著參數(shù)k的增大, 需要添加的邊就越多, 若將相近節(jié)點相連, 則路徑長度會變小; 簡單的加邊使得原圖的社區(qū)結(jié)構(gòu)變得交錯, 從而傳遞系數(shù)和平均聚類系數(shù)變化較大, 而基于原圖社區(qū)結(jié)構(gòu)加邊, 一定程度保留了社區(qū)結(jié)構(gòu), 使得傳遞系數(shù)和平均聚類系數(shù)變化較小. KDVEM21 算法基于層次化社區(qū)結(jié)構(gòu), 優(yōu)先與距離近的目標(biāo)節(jié)點連邊, 使得平均路徑長度的變化較小, 從表2 可以看出, KDVEM21 算法在平均路徑長度的相對變化較小; 正是考慮社區(qū)結(jié)構(gòu)的原因, 傳遞系數(shù)和平均聚類系數(shù)的變化較小, 在ca-GrQc、ca-HepTh、ca-HepPh 和ca-AstroPh 數(shù)據(jù)集上的綜合評價最好. 但對于節(jié)點較多且最大度較大的數(shù)據(jù)集, 采用優(yōu)先加邊的操作時, 可能需要遍歷高級別社區(qū), 這一定程度上破壞了小規(guī)模社區(qū)的結(jié)構(gòu), 加劇了傳遞系數(shù)的變化.

表2 匿名圖的結(jié)構(gòu)特性

Zhang 等人[24]通過對比添加邊和節(jié)點來評估算法的匿名代價, 如表3、表4 所示. KDVEM21 算法采用兩階段加邊操作, 充分利用原圖的節(jié)點進行加邊, 減少了添加的節(jié)點. 對比加邊且可加點類算法, KDVEM21算法添加的邊或節(jié)點更少.

表3 ca-HepPh 數(shù)據(jù)集上邊和節(jié)點數(shù)的變化量

表4 ca-AstroPh 數(shù)據(jù)集上邊和節(jié)點數(shù)的變化量

5 總結(jié)與展望

社交網(wǎng)絡(luò)匿名化是復(fù)雜網(wǎng)絡(luò)領(lǐng)域中一個重要的研究方向. 解決社交網(wǎng)絡(luò)匿名化問題需要平衡用戶隱私保護和圖數(shù)據(jù)實用性二者的關(guān)系. 本文利用經(jīng)典算法的優(yōu)勢提出了改進算法, KDVEM21 算法采用加邊且可加點的匿名化策略, 分兩個階段進行加邊, 并結(jié)合節(jié)點特性和社區(qū)結(jié)構(gòu)對加邊操作進行了優(yōu)化. 在5 個真實網(wǎng)絡(luò)上測試KDVEM21 算法的有效性, 實驗結(jié)果表明, 對比5 個經(jīng)典算法, 大多數(shù)情況下, KDVEM21 算法能更好地保留圖的幾種典型的結(jié)構(gòu)特性(平均路徑長度、平均聚類系數(shù)和傳遞系數(shù)), 并且對比加邊且可加點類算法, 添加邊或節(jié)點更少; 但新算法的時間復(fù)雜度并不具備優(yōu)勢. 未來工作: 對算法時間復(fù)雜度進行優(yōu)化; 探索算法在其它圖結(jié)構(gòu)特性度量下的匿名效果; 減少圖匿名化的代價.