基于信息損失量估計的匿名圖構(gòu)造方法

蘇潔，劉帥，羅智勇，孫廣路

?

基于信息損失量估計的匿名圖構(gòu)造方法

蘇潔，劉帥，羅智勇，孫廣路

（哈爾濱理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150080）

首先分析了在進化的社會網(wǎng)絡(luò)序列中，攻擊者利用節(jié)點度信息，通過識別目標節(jié)點的方法對局部社會網(wǎng)絡(luò)進行攻擊過程，分析了利用匿名方法對該類攻擊進行隱私保護時存在的信息損失問題，針對該問題，提出了一種基于信息損失量估計的匿名圖流構(gòu)造方法，通過子圖節(jié)點屬性泛化、子圖內(nèi)部結(jié)構(gòu)的泛化控制圖重構(gòu)的信息損失，通過禁止子圖內(nèi)部擾動阻止網(wǎng)絡(luò)攻擊。定義匿名過程中由于圖重構(gòu)造成的節(jié)點和結(jié)構(gòu)信息損失的估算方法，建立了基于貪婪聚類算法的網(wǎng)絡(luò)節(jié)點的匿名聚類算法，根據(jù)信息損失估計實現(xiàn)匿名分組，在進化的社會網(wǎng)絡(luò)中以最小信息損失量構(gòu)造匿名社會網(wǎng)絡(luò)，在醫(yī)療診斷數(shù)據(jù)集上的實驗表明所提方法能夠較理想地控制信息損失量。

社會網(wǎng)絡(luò)；隱私保護；匿名；信息損失估計

1 引言

隨著社會網(wǎng)絡(luò)分析方法在各個社會研究領(lǐng)域中的廣泛應(yīng)用，越來越多的研究人員開始關(guān)注社會網(wǎng)絡(luò)相關(guān)問題[1]，其中，社會網(wǎng)絡(luò)的隱私保護成為該研究領(lǐng)域的關(guān)鍵問題之一。發(fā)布社會網(wǎng)絡(luò)時，需要保護私人的敏感信息和社會關(guān)系，而社會網(wǎng)絡(luò)的攻擊方試圖通過數(shù)據(jù)挖掘等技術(shù)發(fā)現(xiàn)社會網(wǎng)絡(luò)中的敏感信息。社會網(wǎng)絡(luò)通常以圖的形式發(fā)布，網(wǎng)絡(luò)中的節(jié)點表示個體，邊表示個體間的關(guān)系。在社會網(wǎng)絡(luò)圖中，每個節(jié)點由實體—屬性集合描述，有唯一的標識符，由于對社會網(wǎng)絡(luò)的研究可以利用圖工具實現(xiàn)，越來越多的研究人員通過研究圖匿名方法來解決隱私保護問題。文獻[2]將匿名方法進行了分類，分析了圖的匿名方法，指出由于動態(tài)社會網(wǎng)絡(luò)需要定期發(fā)布網(wǎng)絡(luò)數(shù)據(jù)來支持動態(tài)分析，因此會造成信息的泄露。文獻[3, 4]提出了基于群和分類的匿名圖，文獻[5]提出了一種社會網(wǎng)絡(luò)中數(shù)據(jù)和結(jié)構(gòu)化匿名的聚類方法，文獻[6]介紹了在圖中怎樣保護敏感關(guān)系，文獻[7]提出一種基于差分隱私模型的隨機擾動方法，實現(xiàn)邊及邊權(quán)重的強保護，文獻[8]驗證了匿名圖中節(jié)點的再識別問題，文獻[9]提出了通過發(fā)布和分析合成圖的方法來保護社會網(wǎng)絡(luò)中的個人社會關(guān)系，文獻[10]提出一種在共享有意義的圖形數(shù)據(jù)集的同時保護個人隱私的解決方案，文獻[11, 12]研究了進化社會網(wǎng)絡(luò)中的匿名圖問題。然而，隱私保護技術(shù)仍然處于研究的初級階段，網(wǎng)絡(luò)的攻擊方仍然能夠在發(fā)布的匿名圖中根據(jù)背景知識找到社會網(wǎng)絡(luò)中感興趣的個體和相關(guān)信息，文獻[13, 14]證明現(xiàn)有的圖匿名方法并未取得匿名方法的理想結(jié)果。

現(xiàn)有的圖的匿名方法分為3類：1）基于匿名的方法，通過調(diào)整圖的結(jié)構(gòu)保護敏感信息[15, 16]，采用匿名方法，網(wǎng)絡(luò)節(jié)點無法識別子圖內(nèi)的?1個節(jié)點；2）基于概率的方法，通過隨機添加/刪除邊或切換邊的方法保護敏感信息[17]；3）基于泛化的方法，通過隱藏個人細節(jié)信息的隱私保護方法[4,5]。在社會網(wǎng)絡(luò)發(fā)布過程中，通過更換節(jié)點的識別信息或者通過增加/刪減邊來改變結(jié)構(gòu)信息，實現(xiàn)社會網(wǎng)絡(luò)隱私保護。由于存在大量可獲取的歷史發(fā)布數(shù)據(jù)和節(jié)點度信息，社會網(wǎng)絡(luò)攻擊者會在某一時刻插入一個目標節(jié)點，在發(fā)布網(wǎng)絡(luò)序列中利用背景信息識別該目標節(jié)點，實現(xiàn)網(wǎng)絡(luò)攻擊。針對該類攻擊的匿名方法包括：1）采用節(jié)點度泛化的匿名方法，針對攻擊者利用指定個體社會關(guān)系的先驗知識對網(wǎng)絡(luò)進行的攻擊，通過插入或刪除邊的方法實現(xiàn)基于度匿名圖的重構(gòu)，使每個節(jié)點至少與?1個節(jié)點有相同的度；2）采用鄰域匿名方法，利用貪婪圖調(diào)整算法生成節(jié)點標簽，插入邊，使每個鄰接節(jié)點能夠區(qū)分?1個節(jié)點，該方法避免了攻擊者根據(jù)已知目標節(jié)點的鄰接子圖進行的網(wǎng)絡(luò)攻擊；3）利用子圖同構(gòu)的匿名方法，重構(gòu)圖至少包含個子圖的同構(gòu)子圖，避免攻擊者通過識別指定個體的任意子圖進行的網(wǎng)絡(luò)攻擊。利用此類方法保護社會網(wǎng)絡(luò)需要重構(gòu)社會網(wǎng)絡(luò)圖，在此過程中產(chǎn)生的信息損失既包括節(jié)點屬性信息損失，又包括結(jié)構(gòu)信息損失。

在分析匿名方法的基礎(chǔ)上，針對社會網(wǎng)絡(luò)發(fā)布過程中潛在的安全問題及匿名過程中的信息損失問題，本文利用匿名圖工具，提出了在進化的社會網(wǎng)絡(luò)中通過信息損失估計的方法，利用邊的泛化構(gòu)造匿名圖。本文創(chuàng)新之處如下。

1) 在社會網(wǎng)絡(luò)發(fā)布過程中，利用信息損失估計方法構(gòu)建匿名子圖，在節(jié)點信息損失、結(jié)構(gòu)信息損失和社會網(wǎng)絡(luò)安全級別方面取得折衷的最優(yōu)值。

2) 利用節(jié)點信息、子圖結(jié)構(gòu)信息泛化構(gòu)建的匿名子圖，避免了擾動攻擊對網(wǎng)絡(luò)安全的威脅。

3) 在發(fā)布的社會網(wǎng)絡(luò)中，通過判斷網(wǎng)絡(luò)結(jié)構(gòu)圖的變化選擇構(gòu)建子圖方法，提出以極小的信息損失代價平衡網(wǎng)絡(luò)子圖構(gòu)建的時間復(fù)雜性的方法，最大程度保證動態(tài)網(wǎng)絡(luò)的穩(wěn)定性。

2 基于節(jié)點度的社會網(wǎng)絡(luò)攻擊

上述分析表明，利用邊擾動的方法實現(xiàn)動態(tài)社會網(wǎng)絡(luò)匿名，攻擊者可以利用收集到的節(jié)點信息實現(xiàn)局部網(wǎng)絡(luò)攻擊。雖然Facebook、Twitter等社會網(wǎng)絡(luò)已經(jīng)限定網(wǎng)絡(luò)用戶的訪問范圍，但是基于應(yīng)用的需要，攻擊者仍然能夠利用上述方法攻擊局部開放網(wǎng)絡(luò)。

采用鄰域匿名方法能夠有效控制攻擊者利用已知目標節(jié)點的鄰接子圖信息進行的網(wǎng)絡(luò)攻擊，但是構(gòu)建匿名圖的過程中會有大量信息損失，3.1節(jié)中給出了利用貪婪圖調(diào)整算法生成節(jié)點標簽，通過構(gòu)建信息損失量估計算法，預(yù)估計構(gòu)建匿名子圖的損失量，實現(xiàn)最小信息損失匿名圖構(gòu)造。

3 構(gòu)建社會網(wǎng)絡(luò)的匿名子圖

3.1 基于泛化的匿名

匿名是隱私保護的經(jīng)典方法，每個數(shù)據(jù)組至少包含個無法區(qū)分的節(jié)點。傳統(tǒng)方法通過插入或刪除邊的擾動方法保護節(jié)點不被識別，該匿名方法構(gòu)造過程中會造成信息損失，影響數(shù)據(jù)的可信性。基于屬性泛化的方法能夠降低對原圖結(jié)構(gòu)的破壞，降低信息損失。

為了構(gòu)建匿名子圖，既要對節(jié)點信息泛化，也要對子圖內(nèi)部結(jié)構(gòu)和子圖間的聯(lián)系泛化。表示子圖之間的關(guān)系的邊顯示了網(wǎng)絡(luò)的結(jié)構(gòu)特征，以實現(xiàn)某些應(yīng)用。匿名網(wǎng)絡(luò)結(jié)構(gòu)中，子圖內(nèi)部不允許使用擾動方法，有效防止了基于節(jié)點度的攻擊。利用節(jié)點信息、子圖內(nèi)部關(guān)系和子圖間的關(guān)系，通過估計信息損失，構(gòu)造匿名圖。

1) 每個分組至少包含個節(jié)點；

2) 估計聚類的信息損失，降低匿名過程的信息損失量。

因此，需要定義一種信息損失的估算方法。

3.2 基于信息損失估計的匿名圖重構(gòu)方法

基于信息損失估計的匿名圖重構(gòu)方法將具有相似屬性且具有最小信息損失的個節(jié)點聚為一個集合，聚類分組過程中，用于損失估計的信息包括圖重構(gòu)信息和節(jié)點與分組的結(jié)構(gòu)信息。

(2)

其中，節(jié)點間的距離、節(jié)點與聚類集合間的距離取值為[0, 1]。

在圖中選擇度最大的節(jié)點作為聚類集合的中心節(jié)點，選擇?1個與當(dāng)前聚類集合有最小距離但未分配的節(jié)點來構(gòu)造新的聚類集合。節(jié)點間的距離和結(jié)構(gòu)距離分別表示為和。

根據(jù)節(jié)點屬性計算聚類分組過程的信息損失包括泛化信息損失和結(jié)構(gòu)信息損失[14]。泛化信息損失用于計算節(jié)點描述性信息的損失[20]，定義泛化信息損失為

(4)

(6)

(7)

算法1 基于信息損失估計的匿名聚類算法

輸入 圖；

參數(shù)、參數(shù)和參數(shù)；

1)=||=0; // 聚類分組數(shù)

2)=||; //初始值

//遍歷節(jié)點找出最大度節(jié)點作為聚類的種子節(jié)點

4) Seed= v,v有當(dāng)前最大度d;

5)s={ v}; //v加入到分組中

6)=?v;

7) while(|s|<)

12) return;

13) end if

14) end while

15) if(|s|<)

18) else

20)=+1;

21) end if

22) end while

社會網(wǎng)絡(luò)在進化過程中，會有新用戶加入，或者舊用戶退出，在網(wǎng)絡(luò)圖中表現(xiàn)為插入新的節(jié)點和邊或者刪除某些節(jié)點和邊，由此造成的社會網(wǎng)絡(luò)結(jié)構(gòu)的變化定期更新發(fā)布。更新時間間隔表示為，圖流序列表示為0,1,…,G，時刻的圖結(jié)構(gòu)變化定義為如式（8）所示。

圖G中節(jié)點及邊的結(jié)構(gòu)變化定義如式（9）和式（10）所示。

(9)

(11)

3.3 匿名子圖信息損失評價

利用基于信息損失估計的匿名聚類算法將社會網(wǎng)絡(luò)圖劃分成分組集合，結(jié)構(gòu)信息損失由類內(nèi)結(jié)構(gòu)損失和類間結(jié)構(gòu)損失2部分組成[21]，定義如(12)所示。

(13)

(15)

3.4 基于圖的變化率的圖流聚類算法

對于初始的社會網(wǎng)絡(luò)，采用聚類算法得到分組后，聚類分組對應(yīng)的節(jié)點核記為，，是類內(nèi)生成對，，。匿名社會網(wǎng)定義為

算法2 基于圖的變化率的圖流聚類算法

輸入G?1,G；

7) end for

11) if(|s|<)

14) end if

15) end for

16) end if

17) end if

18) else

19) 網(wǎng)絡(luò)結(jié)構(gòu)變化明顯，對整體網(wǎng)絡(luò)匿名分組

20) end else

在社會網(wǎng)絡(luò)更新過程中，采用基于圖的變化率的圖流聚類算法，計算圖流的結(jié)構(gòu)變化，通過估算最小信息損失量方法實現(xiàn)匿名聚類。

4 仿真實驗

表1提供了用于急性髓細胞白血病診斷的病歷數(shù)據(jù)。0時刻圖0的節(jié)點集合為。病患資料的個人信息中，SSN和駕駛證等已經(jīng)被隱藏，表中給出了年齡、性別、郵政編碼、婚姻狀況等近似標識符。為了保護病人的隱私，采用本文匿名方法，屬性集定義為，，，={Gender, Zip code, Marriage}。

表1 診斷的病歷數(shù)據(jù)

圖2為根據(jù)診斷數(shù)據(jù)和社會關(guān)系構(gòu)建的社會網(wǎng)絡(luò)，0時刻的網(wǎng)絡(luò)表示為圖0，1時刻的網(wǎng)絡(luò)表示為圖1，層次結(jié)構(gòu)屬性1、2、3，如圖3所示。表2給出了取3、6，分別取0、0.6、1時的聚類分組結(jié)果。

表2 基于信息損失估計的聚類分組

圖4給出了取2~10，取0~1時節(jié)點的泛化信息損失和結(jié)構(gòu)信息損失情況。圖4數(shù)據(jù)表明，最終發(fā)布的匿名數(shù)據(jù)集中包含的匿名組數(shù)目越多，值越小，信息損失越少，匿名化的數(shù)據(jù)越接近真實數(shù)據(jù)，該數(shù)據(jù)集的可信任度越高。=1時的節(jié)點泛化信息損失高于=0時的泛化信息損失；=0時的結(jié)構(gòu)信息損失低于=1時的結(jié)構(gòu)信息損失。

在1時刻插入新的節(jié)點如圖2(b)所示。,1結(jié)構(gòu)變化率，，取=4，分別為0和1時，采用算法2聚類分組結(jié)果為A1，對1采用基于完全信息算是估計的聚類分組結(jié)果為A2，如表3所示，A1和A2的聚類分組信息損失如圖5所示。

聚類分組誤差定義為

(19)

該數(shù)據(jù)表明，最終發(fā)布的匿名數(shù)據(jù)集中包含的匿名組越多，該數(shù)據(jù)集包含的信息越豐富，且數(shù)據(jù)集的平均匿名組規(guī)模越小，信息損失越小，匿名化的數(shù)據(jù)越接近原來的真實數(shù)據(jù)，該數(shù)據(jù)集的可用性越高。

表3 基于聚類分組信息損失估計的聚類分組(k=4)

5 結(jié)束語

針對社會網(wǎng)絡(luò)發(fā)布過程中的安全問題，本文分析了基于擾動的攻擊過程及相應(yīng)的解決方法，建立了基于信息損失估計的匿名方法，通過子圖節(jié)點屬性信息泛化和子圖結(jié)構(gòu)信息泛化構(gòu)建子圖，在降低重構(gòu)圖的信息損失的同時，阻止擾動攻擊。在社會網(wǎng)絡(luò)更新過程中，首先判斷網(wǎng)絡(luò)結(jié)構(gòu)變化，在網(wǎng)絡(luò)變化率較小的情況下，通過損失部分信息的方法平衡網(wǎng)絡(luò)計算時間復(fù)雜性，同時減少網(wǎng)絡(luò)結(jié)構(gòu)的破壞。后續(xù)研究工作中，將繼續(xù)研究在動態(tài)的社會網(wǎng)絡(luò)中如何以最少的信息損失取得最優(yōu)的匿名級別問題。

[1] 韓毅, 方濱興, 賈焰,等. 基于密度估計的社會網(wǎng)絡(luò)特征簇挖掘方法[J]. 通信學(xué)報, 2012, 33(5):38-48.

HAN Y, FANG B X, JIA Y, et al. Mining characteristic clusters: a density estimation approach[J]. Journal on Communications, 2012, 33(5):38-48.

[2] WU X, YING X, LIU K. A survey of privacy-preservation of graphs and social networks[M]. Managing and mining graph data. Springer US, 2010: 421-453.

[3] CASAS-ROMA J, HERRERA-JOANCOMARTí J, TORRA V. Anonymizing graphs: measuring quality for clustering[J]. Knowledge & Information Systems, 2015, 44(3):1-22.

[4] BHAGAT S, CORMODE G, KRISHNAMURTHY B. Class based graph anaonymization for social network data[C]//35th International Conference on Very Large Data Base. c2009: 766-777.

[5] WANG R, ZHANG M, FENG D, et al. A clustering approach for privacy-preserving in social networks[C]//Information Security and Cryptology-ICISC 2014. Springer International Publishing, c2014: 193-204.

[6] JING Y, GOSSWEILER III R C. Using visualization techniques for adjustment of privacy settings in social networks[P]. US8832567. 2014.

[7] AGGARWAL C C, LI Y, YU P S. On the anonymizability of graphs[J]. Knowledge & Information Systems, 2015, 45(3):571-588.

[8] 蘭麗輝, 鞠時光. 基于差分隱私的權(quán)重社會網(wǎng)絡(luò)隱私保護[J]. 通信學(xué)報, 2015, 36(9):145-159.

LAN L H, JU S G. Privacy preserving based on differential privacy for weighted social networks[J]. Journal on Communications, 2015, 36(9):145-159.

[9] KARWA V, SLAVKOVIC A B, KRIVITSKY P N. Differentially private exponential random graphs[C]//Privacy in Statistical Database-UNESCO Chair in Data Privacy, International Conference, PSD 2014. Ibiza, Spain, c2014: 143-155.

[10] SALA A, ZHAO X, WILSON C. Sharing graphs using differentially private graph models[C]//The 2011 ACM SIGCOMM Conference on Internet Measurement, ACM, c2011: 81-98.

[11] MEDFORTH N, WANG K. Privacy risk in graph stream publishing for social network data[C]//The 2011 IEEE 11th International Conference on Data Mining. c2011: 437-446.

[12] ROSSI L, MUSOLESI M, TORSELLO A. On the-anonymization of time-varying and multi-layer social graphs[J]. arXiv preprint arXiv: 1503. 06497, 2015.

[13] ZHOU B, PEI J. The-anonymity and-diversity approaches for privacy preservation in social networks against neighborhood attacks[J]. Knowledge and Information Systems, 2011, 28(1): 47-77.

[14] LIU C G, LIU I H, YAO W S, et al.-anonymity against neighborhood attacks in weighted social networks[J]. Security & Communication Networks, 2015, 18(8): 3864-3882.

[15] LIU K, TERZI E. Towards identity anonymization on graphs[C]//The 2008 ACM SIGMOD International Conference on Management of Data. ACM, c2008: 93-106.

[16] CHENG J, FU A W, LIU J.-isomorphism: privacy preserving network publication against structural attacks[C]//The 2010 ACM SIGMOD International Conference on Management of Data. ACM, c2010: 459-470.

[17] MICHEAL H, GEROME M, DAVID J. Resisting structural re-identification in anonymized social networks[J]. Proceedings of the VLDB Endowment, 2008, 1(1): 102-114.

[18] FUNG B C M, JIN Y, LI J, et al. Anonymizing social network data for maximal frequent-sharing pattern mining[M]//Recommendation and Search in Social Networks. Springer International Publishing, 2015:77-100.

[19] SWEENEY L.-anonymity: a model for protecting privacy[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(05): 557-570.

[20] BYUN J W, KAMRA A, BERTINO E, et al. Efficient-anonymization using clustering techniques[C]//Dasfaa. Springer Berlin Heidelberg, c2007: 188-200.

[21] HAN J, KAMBER M. Data mining: comcepts and techniques[J]. San Francisco, 2006, 29(1): 1 - 25.

Method of constructing an anonymous graph based on information loss estimation

SU Jie, LIU Shuai, LUO Zhi-yong, SUN Guang-lu

（School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China）

A potential attack based on degree information by re-identifying target vertexes from a sequence of published graphs was analyzed. To deal with this kind of attack, a-anonymous graph stream constructing method based on information loss estimation was provided. Information loss caused by re-constructing graph was controlled by using the method of attributes generalization of nodes and the structure generalization of sub-graph. The disturbance in sub-graph was forbidden to prevent the attack. The method of measuring the information loss of nodes and structures during the anonymous process due to re-construction of graph was defined. A-anonymity cluster algorithm based on greedy clustering algorithm was build, which realized anonymous partition according to the information loss. Finally, a method of constructing anonymous social network for the evolving social network with the least information loss was provided. The experiments on medical diagnostic data set show that the algorithm of constructing anonymous graph based on the information loss estimation can be used to control the loss of information.

social network, privacy protection,-anonymity, information loss estimation

TP309.2

A

10.11959/j.issn.1000-436x.2016116

2015-11-12；

2016-04-26

黑龍江省自然科學(xué)基金資助項目（No.A201301）；黑龍江省教育科學(xué)規(guī)劃課題基金資助項目(No.GBC1211062)；黑龍江省普通高等學(xué)校新世紀優(yōu)秀人才培養(yǎng)計劃基金資助項目(No.1155-ncet-008)；黑龍江省博士后基金資助項目（No.LBH-Z12082）

The Natural Science Foundation of Heilongjiang Province(No.A201301), Scientific Planning Issues of Education in Heilongjiang Province(No.GBC1211062), Research Fund for the Program of New Century Excellent Talents in Heilongjiang Provincial University (No.1155-ncet-008), Post Doctoral Fund of Heilongjiang Province(No.LBH-Z12082)

蘇潔（1979-），女，山東淄博人，哈爾濱理工大學(xué)副教授、碩士生導(dǎo)師，主要研究方向為智能信息處理。

劉帥（1988-），男，山東濟寧人，哈爾濱理工大學(xué)碩士生，主要研究方向為智能信息處理。

羅智勇（1978-），男，黑龍江大慶人，哈爾濱理工大學(xué)副教授、碩士生導(dǎo)師，主要研究方向為智能信息處理。

孫廣路（1979-），男，黑龍江哈爾濱人，哈爾濱理工大學(xué)教授、碩士生導(dǎo)師，主要研究方向為計算機網(wǎng)絡(luò)與信息安全、機器學(xué)習(xí)。