基于信息損失量估計的匿名圖構造方法

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

?

基于信息損失量估計的匿名圖構造方法

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

（哈爾濱理工大學計算機科學與技術學院，黑龍江哈爾濱150080）

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

社會網絡；隱私保護；匿名；信息損失估計

1 引言

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

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

在分析匿名方法的基礎上，針對社會網絡發布過程中潛在的安全問題及匿名過程中的信息損失問題，本文利用匿名圖工具，提出了在進化的社會網絡中通過信息損失估計的方法，利用邊的泛化構造匿名圖。本文創新之處如下。

1) 在社會網絡發布過程中，利用信息損失估計方法構建匿名子圖，在節點信息損失、結構信息損失和社會網絡安全級別方面取得折衷的最優值。

2) 利用節點信息、子圖結構信息泛化構建的匿名子圖，避免了擾動攻擊對網絡安全的威脅。

3) 在發布的社會網絡中，通過判斷網絡結構圖的變化選擇構建子圖方法，提出以極小的信息損失代價平衡網絡子圖構建的時間復雜性的方法，最大程度保證動態網絡的穩定性。

2 基于節點度的社會網絡攻擊

上述分析表明，利用邊擾動的方法實現動態社會網絡匿名，攻擊者可以利用收集到的節點信息實現局部網絡攻擊。雖然Facebook、Twitter等社會網絡已經限定網絡用戶的訪問范圍，但是基于應用的需要，攻擊者仍然能夠利用上述方法攻擊局部開放網絡。

采用鄰域匿名方法能夠有效控制攻擊者利用已知目標節點的鄰接子圖信息進行的網絡攻擊，但是構建匿名圖的過程中會有大量信息損失，3.1節中給出了利用貪婪圖調整算法生成節點標簽，通過構建信息損失量估計算法，預估計構建匿名子圖的損失量，實現最小信息損失匿名圖構造。

3 構建社會網絡的匿名子圖

3.1 基于泛化的匿名

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

為了構建匿名子圖，既要對節點信息泛化，也要對子圖內部結構和子圖間的聯系泛化。表示子圖之間的關系的邊顯示了網絡的結構特征，以實現某些應用。匿名網絡結構中，子圖內部不允許使用擾動方法，有效防止了基于節點度的攻擊。利用節點信息、子圖內部關系和子圖間的關系，通過估計信息損失，構造匿名圖。

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

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

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

3.2 基于信息損失估計的匿名圖重構方法

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

(2)

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

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

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

(4)

(6)

(7)

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

輸入 圖；

參數、參數和參數；

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

2)=||; //初始值

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

4) Seed= v,v有當前最大度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

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

圖G中節點及邊的結構變化定義如式（9）和式（10）所示。

(9)

(11)

3.3 匿名子圖信息損失評價

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

(13)

(15)

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

對于初始的社會網絡，采用聚類算法得到分組后，聚類分組對應的節點核記為，，是類內生成對，，。匿名社會網定義為

算法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) 網絡結構變化明顯，對整體網絡匿名分組

20) end else

在社會網絡更新過程中，采用基于圖的變化率的圖流聚類算法，計算圖流的結構變化，通過估算最小信息損失量方法實現匿名聚類。

4 仿真實驗

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

表1 診斷的病歷數據

圖2為根據診斷數據和社會關系構建的社會網絡，0時刻的網絡表示為圖0，1時刻的網絡表示為圖1，層次結構屬性1、2、3，如圖3所示。表2給出了取3、6，分別取0、0.6、1時的聚類分組結果。

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

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

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

聚類分組誤差定義為

(19)

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

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

5 結束語

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

[1] 韓毅, 方濱興, 賈焰,等. 基于密度估計的社會網絡特征簇挖掘方法[J]. 通信學報, 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] 蘭麗輝, 鞠時光. 基于差分隱私的權重社會網絡隱私保護[J]. 通信學報, 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

黑龍江省自然科學基金資助項目（No.A201301）；黑龍江省教育科學規劃課題基金資助項目(No.GBC1211062)；黑龍江省普通高等學校新世紀優秀人才培養計劃基金資助項目(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-），女，山東淄博人，哈爾濱理工大學副教授、碩士生導師，主要研究方向為智能信息處理。

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

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

孫廣路（1979-），男，黑龍江哈爾濱人，哈爾濱理工大學教授、碩士生導師，主要研究方向為計算機網絡與信息安全、機器學習。