社會網絡數據中一種基于k-degree-l-diversity匿名的個性化隱私保護方法

焦佳

（長沙民政職業技術學院，長沙　410004）

社會網絡數據中一種基于k-degree-l-diversity匿名的個性化隱私保護方法

焦佳

（長沙民政職業技術學院，長沙410004）

近年來關于社會網絡數據的隱私保護方法中，大部分將社會網絡中的所有個體考慮為具有相同等級的隱私保護需求，沒有考慮其隱私需求是多樣化和個性化的，故會對某些個體存在過度保護，造成數據不必要的失真?；诖耍趉-degree-l-diversity匿名方法的基礎上提出了個性化-（k，l）匿名方法。實驗證明，該個性化匿名方法能減少數據的損失，提高數據的可用性。

個性化匿名；隱私保護；社會網絡

0　引言

如今，隨著網絡技術的發展，越來越多的用戶加入不同的在線社會網絡，如Facebook、QQ空間和新浪微博等。當發布這些極具分析價值的社會網絡數據時，卻因攻擊者具備某些個體的背景知識時，造成這些個體的個人隱私信息泄露。因此，怎樣使發布的社會網絡數據具有實用性的同時保護個人的隱私信息已成為目前研究熱點之一。

已存在的關于社會網絡的研究中，研究者一般用一個圖來表示社會網絡數據。圖中的節點代表社會網絡中的個體，圖中的邊代表個體之間的聯系［1-2］。目前許多關于社會網絡隱私保護的方法已存在。在攻擊者具有節點度的背景知識下，為了抵御個體的重識別，Liu等人［3］提出了k-degree匿名方法。為了抵御個體和個體標簽的重識別，在k-degree匿名的基礎上，Yuan等人［4］引入了k-degree-l-diversity匿名的方法。但是kdegree-l-diversity匿名方法沒有考慮個體的隱私需求是多樣化和個性化的，基于此我們提出了個性化-（k，l）匿名方法。

1　問題描述

本文，我們研究的是節點帶一個敏感標簽和一個隱私屬性的無權的無向的簡單圖的隱私保護問題。且攻擊者所具有的背景知識是某個節點的度，其想要重識別某個節點或某個節點的敏感屬性。

定義1社會網絡圖：一個社會網絡是一個四元組G=（V，E，L，λ），其中V是圖G節點的集合，E?V×V是圖G節點之間邊的集合，L是節點標簽的集合，λ：V→L是節點和其標簽間的映射函數。

對任意在L中的la，la是一個三元組，即la=（id，s，r），其中id是節點的標識符，s是節點id的敏感標簽，r是節點id的隱私需求。隱私需求分為三個層次，即r2，r1，r0，且隱私需求從r2到r0是依次從高到低。

定義2度序列X：一個有n個節點的圖G的度序列X是一個n元祖，且其中任一元素X［i］=（id［i］，d［i］，s［i］，r［i］）（1≤i≤n），其中id［i］是第i個節點的標識符，d［i］是第i個節點的度，s［i］是第i個節點的敏感標簽，r［i］是第i個節點的隱私需求。度序列中的元素先按節點度（X［i］.d）從大到小排列，其次按節點隱私需求（X［i］.r）從高到低排列。

圖1　兩種匿名方法的發布圖

如圖1（a），其度序列XG1=｛（1，4，感冒，r2），（3，4，鼻炎，r1），（7，4，癌癥，r2），（0，2，感冒，r1），（2，2，癌癥，r2），（4，2，鼻炎，r0），（5，2，感冒，r1），（6，2，感冒，r0）｝

定義3 k-degree匿名：對于圖中任意一節點v，同一至少存在k-1個其他節點與v有相同的度。如圖1（a）所示，圖G1是滿足2-degree-2-diversity的匿名圖，其中節點和節點間紅色的線即為滿足匿名條件所添加的邊（如節點5和節點6間的邊）。

定義4 k-degree-l-diversity匿名：對于圖中任意一結點v，同一分組中存在至少k-1個頂點和v有相同的度，且具有相同度的這些頂點至少包含l個不同的敏感標簽值。如圖1（a）所示，圖G1也是滿足2-degree-2-diversity的匿名圖。

定義5個性化-（k，l）匿名：對于圖中任意一隱私需求為r2的節點，滿足k-degree-l-diversity匿名；對于圖中任意一隱私需求為r1的節點，滿足k-degree匿名；對于圖中隱私需求為r0的節點，可無需匿名。如圖1（b）所示，圖G2是滿足個性化2-degree-2-diversity的匿名圖。

經過個性化-（k，l）匿名處理后的發布圖，個體重識別的概率不大于1/k，個體敏感標簽識別的概率不超過1/l，且滿足個體個性化的隱私需求。

2　算法

通過上述定義，實現個性化-（k，l）匿名的算法的偽代碼如算法1所示：

算法1個性化-（k，l）匿名的算法

輸入：圖G的度序列XG，整數k，l（k≥2，l≥2）

輸出：滿足個性化-（k，l）匿名圖G2

1for（v=1；v＜=n；v++）

2if（r（v）=r2）

3合并節點v后面的m個節點，使節點v滿足k-degree-l-diversity匿名

4將這m+1個節點的追加存入匿名圖G2的度序列X_G2；

5v=v+m；

6if（r（v）=r1）

7合并節點v后面的n個節點，使節點v滿足k-degree匿名

8將這n+1個節點的追加存入匿名圖G2的度序列XG2；

9v=v+n；

10for（任一兩節點vi，vj，vi，vj滿足（XG2（v）.d-XG（v）.d≠0））

11在vi，vj間添加邊，直至XG2（v）.d-XG（v）. d=0

3　實驗

實驗環境采用Windows 8.1中文版操作系統，CPU為2.5Ghz的Intel Core i5，編程語言為C++，運行平臺為Microsoft Visual Studio.NET 2010。我們在真實數據集Citation做實驗。數據集Citation（http：//www.datatang. com/data/17310）包含2555個節點和6101條邊，我們用節點的17個出版年份作為節點的敏感屬性，且按r2：r1：r0=3：3：4的比例隨機分配節點的隱私需求。

圖2（a）是數據集Citation在不同的k值（l=5）下兩種匿名方法節點度增加代價Costa，因為個性化的匿名方法為了達到匿名要求，不需對所有節點進行度增加，故在相同k和l下Costa更小。圖2（b）是數據集Citation在不同k值 （l=5）下按兩種匿名方法發布圖后的APL與原圖的比較，據圖可知在相同的k和l下，個性化匿名方法發布后圖的APL與原圖的APL較非個性化匿名發布后圖的APL更接近，即個性化匿名方法發布的圖更有實用性。

4　結語

本文基于k-degree-l-diversity匿名方法，提出了滿足社會網絡個體個性化隱私需求的個性化-（k，l）匿名方法，設計并實現了個性化-（k，l）匿名算法。實驗表明，我們的方法能減少代價，提高發布數據的實用性。

圖2　數據集Citation：不同k值下的Costa和APL

［1］Wasserman S.Social Network Analysis：Methods and Applications［M］.Cambridge University Press，1994

［2］Liu K，Das K，Grandison T，et al.Privacy-Preserving Data Analysis on Graphs and Social Networks［M］.Next Generation of Data Mining.CRC Press，2008：419-437

［3］Liu K，Terzi E.Towards Identity Anonymization on Graphs［C］.Proceedings of the 2008 ACM SIGMOD International Conference on Management of data.ACM，2008：93-106

［4］Yuan M，Chen L，Yu P S，Yu T.Protecting Sensitive Labels in Social Network Data Anonymization［J］.IEEE Transactions on Knowledge and Data Engineering，vol.25，no.3，pp.633-647，March 2013，doi：10.1109/TKDE.2011.259

Personalized Anonymity；Privacy Preserving；Social Network

A Personalized Privacy Preserving Method Based on k-degree-l-diversity Anonymity for Social Network Data

JIAO Jia
（Changsha Social Work College，Changsha 410004）

In recent research about privacy preserving for social network，most of the methods focus on the same level privacy requirement for all individuals，and do not consider that individuals’privacy requirement is various and personalized.Thus can cause“excessive protection”to some individuals，and then bring unnecessary data distortion.Motivated by this，proposes the personalized-（k，l）anonymity method based on k-degree-l-diversity anonymity method.The experiment shows that the personalized anonymous method can reduce the data distortion and improve the utility of the data.

1007-1423（2016）29-0045-04

10.3969/j.issn.1007-1423.2016.29.010

焦佳（1987-），女，湖南岳陽人，碩士，助教，研究方向為數據安全、隱私保護

2016-08-26

2016-10-10

1007-1423（2016）29-0048-05

10.3969/j.issn.1007-1423.2016.29.011