焦佳

（長(zhǎng)沙民政職業(yè)技術(shù)學(xué)院，長(zhǎng)沙　410004）

社會(huì)網(wǎng)絡(luò)數(shù)據(jù)中一種基于k-degree-l-diversity匿名的個(gè)性化隱私保護(hù)方法

焦佳

（長(zhǎng)沙民政職業(yè)技術(shù)學(xué)院，長(zhǎng)沙410004）

近年來(lái)關(guān)于社會(huì)網(wǎng)絡(luò)數(shù)據(jù)的隱私保護(hù)方法中，大部分將社會(huì)網(wǎng)絡(luò)中的所有個(gè)體考慮為具有相同等級(jí)的隱私保護(hù)需求，沒(méi)有考慮其隱私需求是多樣化和個(gè)性化的，故會(huì)對(duì)某些個(gè)體存在過(guò)度保護(hù)，造成數(shù)據(jù)不必要的失真?；诖耍趉-degree-l-diversity匿名方法的基礎(chǔ)上提出了個(gè)性化-（k，l）匿名方法。實(shí)驗(yàn)證明，該個(gè)性化匿名方法能減少數(shù)據(jù)的損失，提高數(shù)據(jù)的可用性。

個(gè)性化匿名；隱私保護(hù)；社會(huì)網(wǎng)絡(luò)

0　引言

如今，隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，越來(lái)越多的用戶加入不同的在線社會(huì)網(wǎng)絡(luò)，如Facebook、QQ空間和新浪微博等。當(dāng)發(fā)布這些極具分析價(jià)值的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)時(shí)，卻因攻擊者具備某些個(gè)體的背景知識(shí)時(shí)，造成這些個(gè)體的個(gè)人隱私信息泄露。因此，怎樣使發(fā)布的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)具有實(shí)用性的同時(shí)保護(hù)個(gè)人的隱私信息已成為目前研究熱點(diǎn)之一。

已存在的關(guān)于社會(huì)網(wǎng)絡(luò)的研究中，研究者一般用一個(gè)圖來(lái)表示社會(huì)網(wǎng)絡(luò)數(shù)據(jù)。圖中的節(jié)點(diǎn)代表社會(huì)網(wǎng)絡(luò)中的個(gè)體，圖中的邊代表個(gè)體之間的聯(lián)系［1-2］。目前許多關(guān)于社會(huì)網(wǎng)絡(luò)隱私保護(hù)的方法已存在。在攻擊者具有節(jié)點(diǎn)度的背景知識(shí)下，為了抵御個(gè)體的重識(shí)別，Liu等人［3］提出了k-degree匿名方法。為了抵御個(gè)體和個(gè)體標(biāo)簽的重識(shí)別，在k-degree匿名的基礎(chǔ)上，Yuan等人［4］引入了k-degree-l-diversity匿名的方法。但是kdegree-l-diversity匿名方法沒(méi)有考慮個(gè)體的隱私需求是多樣化和個(gè)性化的，基于此我們提出了個(gè)性化-（k，l）匿名方法。

1　問(wèn)題描述

本文，我們研究的是節(jié)點(diǎn)帶一個(gè)敏感標(biāo)簽和一個(gè)隱私屬性的無(wú)權(quán)的無(wú)向的簡(jiǎn)單圖的隱私保護(hù)問(wèn)題。且攻擊者所具有的背景知識(shí)是某個(gè)節(jié)點(diǎn)的度，其想要重識(shí)別某個(gè)節(jié)點(diǎn)或某個(gè)節(jié)點(diǎn)的敏感屬性。

定義1社會(huì)網(wǎng)絡(luò)圖：一個(gè)社會(huì)網(wǎng)絡(luò)是一個(gè)四元組G=（V，E，L，λ），其中V是圖G節(jié)點(diǎn)的集合，E?V×V是圖G節(jié)點(diǎn)之間邊的集合，L是節(jié)點(diǎn)標(biāo)簽的集合，λ：V→L是節(jié)點(diǎn)和其標(biāo)簽間的映射函數(shù)。

對(duì)任意在L中的la，la是一個(gè)三元組，即la=（id，s，r），其中id是節(jié)點(diǎn)的標(biāo)識(shí)符，s是節(jié)點(diǎn)id的敏感標(biāo)簽，r是節(jié)點(diǎn)id的隱私需求。隱私需求分為三個(gè)層次，即r2，r1，r0，且隱私需求從r2到r0是依次從高到低。

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

圖1　兩種匿名方法的發(fā)布圖

如圖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匿名：對(duì)于圖中任意一節(jié)點(diǎn)v，同一至少存在k-1個(gè)其他節(jié)點(diǎn)與v有相同的度。如圖1（a）所示，圖G1是滿足2-degree-2-diversity的匿名圖，其中節(jié)點(diǎn)和節(jié)點(diǎn)間紅色的線即為滿足匿名條件所添加的邊（如節(jié)點(diǎn)5和節(jié)點(diǎn)6間的邊）。

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

定義5個(gè)性化-（k，l）匿名：對(duì)于圖中任意一隱私需求為r2的節(jié)點(diǎn)，滿足k-degree-l-diversity匿名；對(duì)于圖中任意一隱私需求為r1的節(jié)點(diǎn)，滿足k-degree匿名；對(duì)于圖中隱私需求為r0的節(jié)點(diǎn)，可無(wú)需匿名。如圖1（b）所示，圖G2是滿足個(gè)性化2-degree-2-diversity的匿名圖。

經(jīng)過(guò)個(gè)性化-（k，l）匿名處理后的發(fā)布圖，個(gè)體重識(shí)別的概率不大于1/k，個(gè)體敏感標(biāo)簽識(shí)別的概率不超過(guò)1/l，且滿足個(gè)體個(gè)性化的隱私需求。

2　算法

通過(guò)上述定義，實(shí)現(xiàn)個(gè)性化-（k，l）匿名的算法的偽代碼如算法1所示：

算法1個(gè)性化-（k，l）匿名的算法

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

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

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

2if（r（v）=r2）

3合并節(jié)點(diǎn)v后面的m個(gè)節(jié)點(diǎn)，使節(jié)點(diǎn)v滿足k-degree-l-diversity匿名

4將這m+1個(gè)節(jié)點(diǎn)的追加存入匿名圖G2的度序列X_G2；

5v=v+m；

6if（r（v）=r1）

7合并節(jié)點(diǎn)v后面的n個(gè)節(jié)點(diǎn)，使節(jié)點(diǎn)v滿足k-degree匿名

8將這n+1個(gè)節(jié)點(diǎn)的追加存入匿名圖G2的度序列XG2；

9v=v+n；

10for（任一兩節(jié)點(diǎn)vi，vj，vi，vj滿足（XG2（v）.d-XG（v）.d≠0））

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

3　實(shí)驗(yàn)

實(shí)驗(yàn)環(huán)境采用Windows 8.1中文版操作系統(tǒng)，CPU為2.5Ghz的Intel Core i5，編程語(yǔ)言為C++，運(yùn)行平臺(tái)為Microsoft Visual Studio.NET 2010。我們?cè)谡鎸?shí)數(shù)據(jù)集Citation做實(shí)驗(yàn)。數(shù)據(jù)集Citation（http：//www.datatang. com/data/17310）包含2555個(gè)節(jié)點(diǎn)和6101條邊，我們用節(jié)點(diǎn)的17個(gè)出版年份作為節(jié)點(diǎn)的敏感屬性，且按r2：r1：r0=3：3：4的比例隨機(jī)分配節(jié)點(diǎn)的隱私需求。

圖2（a）是數(shù)據(jù)集Citation在不同的k值（l=5）下兩種匿名方法節(jié)點(diǎn)度增加代價(jià)Costa，因?yàn)閭€(gè)性化的匿名方法為了達(dá)到匿名要求，不需對(duì)所有節(jié)點(diǎn)進(jìn)行度增加，故在相同k和l下Costa更小。圖2（b）是數(shù)據(jù)集Citation在不同k值 （l=5）下按兩種匿名方法發(fā)布圖后的APL與原圖的比較，據(jù)圖可知在相同的k和l下，個(gè)性化匿名方法發(fā)布后圖的APL與原圖的APL較非個(gè)性化匿名發(fā)布后圖的APL更接近，即個(gè)性化匿名方法發(fā)布的圖更有實(shí)用性。

4　結(jié)語(yǔ)

本文基于k-degree-l-diversity匿名方法，提出了滿足社會(huì)網(wǎng)絡(luò)個(gè)體個(gè)性化隱私需求的個(gè)性化-（k，l）匿名方法，設(shè)計(jì)并實(shí)現(xiàn)了個(gè)性化-（k，l）匿名算法。實(shí)驗(yàn)表明，我們的方法能減少代價(jià)，提高發(fā)布數(shù)據(jù)的實(shí)用性。

圖2　數(shù)據(jù)集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-），女，湖南岳陽(yáng)人，碩士，助教，研究方向?yàn)閿?shù)據(jù)安全、隱私保護(hù)

2016-08-26

2016-10-10

1007-1423（2016）29-0048-05

10.3969/j.issn.1007-1423.2016.29.011