一種保護(hù)鏈接關(guān)系的分布式匿名算法

張曉琳，何曉玉，于芳名，劉立新，張換香，李卓麟

1(內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭 014010)2 (中國(guó)人民大學(xué) 信息工程學(xué)院，北京 100872)

1 引 言

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，社會(huì)網(wǎng)絡(luò)，無(wú)論是社交網(wǎng)站(Wechat、Facebook、Twitter等)還是用戶交互網(wǎng)絡(luò)(如emails、blogs、文件分享系統(tǒng))已然成為當(dāng)今人們?nèi)粘＞W(wǎng)絡(luò)生活中不可或缺的一部分.用戶主動(dòng)或被動(dòng)提交的好友互動(dòng)記錄、興趣愛好、消費(fèi)信息等包含了大量社會(huì)結(jié)構(gòu)信息和屬性信息，但隨著用戶網(wǎng)絡(luò)形象的進(jìn)一步豐富，能夠用于確定用戶真實(shí)身份的信息也越來(lái)越多，如何保護(hù)網(wǎng)絡(luò)數(shù)據(jù)中隱私信息的安全性成為隱私保護(hù)研究的熱點(diǎn)問(wèn)題.如圖1所示，社會(huì)網(wǎng)絡(luò)表示成簡(jiǎn)單無(wú)向圖，圖中的節(jié)點(diǎn)和邊分別對(duì)應(yīng)社會(huì)網(wǎng)絡(luò)中的個(gè)體以及個(gè)體間的聯(lián)系.社會(huì)網(wǎng)絡(luò)中個(gè)體的屬性信息，如年齡，在圖中則用節(jié)點(diǎn)的標(biāo)簽來(lái)代替.如若節(jié)點(diǎn)具有多個(gè)標(biāo)簽，則將這些標(biāo)簽稱為節(jié)點(diǎn)的標(biāo)簽列表，如(Afri，20)是節(jié)點(diǎn)1的標(biāo)簽列表.

社會(huì)網(wǎng)絡(luò)圖中，節(jié)點(diǎn)的標(biāo)簽信息尤為重要，攻擊者能夠?qū)?biāo)簽信息作為背景知識(shí)對(duì)節(jié)點(diǎn)進(jìn)行重識(shí)別.在圖G中，假如攻擊者獲知目標(biāo)是一個(gè)28歲的亞洲人，由于節(jié)點(diǎn)標(biāo)簽的唯一性，攻擊者很容易從圖G中重識(shí)別出節(jié)點(diǎn)5.

圖1 社會(huì)網(wǎng)絡(luò)圖GFig.1 Social network graph G

為了抵抗通過(guò)節(jié)點(diǎn)標(biāo)簽為背景知識(shí)的重識(shí)別攻擊，研究者提出了不同的隱私保護(hù)技術(shù)[1，2]，通過(guò)標(biāo)簽范化等方法使得社會(huì)網(wǎng)絡(luò)圖節(jié)點(diǎn)的標(biāo)簽不唯一而達(dá)到隱私保護(hù)的目的.文獻(xiàn)[3]指出即使個(gè)體的身份信息被有效的隱藏，攻擊者仍能推測(cè)出個(gè)體的鏈接關(guān)系.以圖G為例，如若攻擊者得知目標(biāo)是一個(gè)25歲的亞洲人，此時(shí)，攻擊者由圖G得到節(jié)點(diǎn)2和3.盡管這種情況下無(wú)法唯一確定目標(biāo)，但由于節(jié)點(diǎn)2和節(jié)點(diǎn)3之間存在邊，無(wú)論兩者誰(shuí)是攻擊目標(biāo)，攻擊者都可以認(rèn)為攻擊目標(biāo)與亞洲人存在聯(lián)系.此外，隨著社會(huì)網(wǎng)絡(luò)的普及與發(fā)展，社會(huì)網(wǎng)絡(luò)數(shù)據(jù)的規(guī)模不斷增大，呈現(xiàn)出海量化的趨勢(shì).對(duì)于大規(guī)模社會(huì)網(wǎng)絡(luò)數(shù)據(jù)，傳統(tǒng)匿名技術(shù)已不能滿足實(shí)際需求，采用并行算法進(jìn)行匿名處理是提高效率的有效途徑.如何對(duì)隱私保護(hù)技術(shù)進(jìn)行并行處理并對(duì)社會(huì)網(wǎng)絡(luò)中個(gè)體提高有效隱私保護(hù)成為亟待解決的問(wèn)題.

2 相關(guān)工作

為了保護(hù)社會(huì)網(wǎng)絡(luò)中的隱私信息，研究者提出了不同的隱私保護(hù)方案.文獻(xiàn)[4]將屬性視作節(jié)點(diǎn)，利用分割用戶節(jié)點(diǎn)的方法保護(hù)隱私信息.文獻(xiàn)[5]提出 k-degree-l-diversity匿名模型，通過(guò)圖的匿名化操作使得分組內(nèi)的節(jié)點(diǎn)具有相同的度信息且分組所包含的敏感標(biāo)簽不少于L個(gè).文獻(xiàn)[6]利用k-histogram和Full-domain泛化技術(shù)保護(hù)帶權(quán)社會(huì)網(wǎng)絡(luò)中的隱私信息，在匿名圖中，攻擊者通過(guò)節(jié)點(diǎn)權(quán)重包識(shí)別出節(jié)點(diǎn)的概率不大于1/K，通過(guò)節(jié)點(diǎn)標(biāo)簽識(shí)別出節(jié)點(diǎn)的概率不大于1/L.文獻(xiàn)[7]提出一種利用節(jié)點(diǎn)子圖匹配相似度的多敏感屬性t-closenss匿名方案，保持了數(shù)據(jù)的高可用性.文獻(xiàn)[8]提出一種個(gè)性化的敏感屬性(α，k)-匿名模型用于滿足用戶的個(gè)性化需求.文獻(xiàn)[9]考慮到現(xiàn)實(shí)中用戶決定自己敏感信息因人而異的特點(diǎn)，提出一種基于相似性的分組匿名GSGA算法.文獻(xiàn)[10]將用戶交互社會(huì)網(wǎng)絡(luò)抽象成二分圖模型，通過(guò)為用戶產(chǎn)生一個(gè)標(biāo)簽列表的方式抵抗重識(shí)別攻擊.文獻(xiàn)[11]針對(duì)目前的保護(hù)技術(shù)不能夠處理高維數(shù)據(jù)的缺點(diǎn)，提出一種節(jié)點(diǎn)帶標(biāo)簽的二分圖匿名模型.文獻(xiàn)[12]提出一種utility-aware匿名方法，在進(jìn)行k-degree匿名時(shí)同時(shí)考慮最短路徑和鄰居節(jié)點(diǎn)重疊度，提高了匿名圖的數(shù)據(jù)可用性.隨著社會(huì)網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，不少研究者提出了分布式處理的方案.文獻(xiàn)[13，14]提出了利用MapReduce模型在大規(guī)模圖中查找同構(gòu)子圖.文獻(xiàn)[15，16]基于MapReduce模型對(duì)關(guān)系型數(shù)據(jù)進(jìn)行匿名保護(hù).文獻(xiàn)[17]提出基于SMC(Secure Multi-Party)模型的隱私保護(hù)方案.然而，目前的分布式隱私保護(hù)技術(shù)都是針對(duì)關(guān)系型數(shù)據(jù)的，沒(méi)有考慮個(gè)體在社會(huì)網(wǎng)絡(luò)中的圖性質(zhì)特征不能很好地保護(hù)隱私信息.此外MapReduce將中間結(jié)果存放于磁盤，處理過(guò)程中需要反復(fù)遷移數(shù)據(jù)，并不適合處理圖數(shù)據(jù).

GraphX[18，19]是Spark上用于圖和并行圖計(jì)算的處理系統(tǒng)，整個(gè)計(jì)算過(guò)程由若干順序執(zhí)行的超級(jí)步(Superstep)組成.GraphX在編程模型上遵循“節(jié)點(diǎn)為中心”模式，在超級(jí)步S中，圖中節(jié)點(diǎn)匯總從超級(jí)步(S-1)中其他節(jié)點(diǎn)傳遞過(guò)來(lái)的消息，改變自身的狀態(tài)，并向其他節(jié)點(diǎn)發(fā)送消息，這些消息經(jīng)過(guò)同步后，會(huì)在超級(jí)步(S+1)中被其他節(jié)點(diǎn)接收并做出處理.為了便于圖計(jì)算，GraphX引入了擴(kuò)展自Spark RDD的屬性圖，并提供了一組基本功能操作，如圖構(gòu)造操作、圖反轉(zhuǎn)等，以及優(yōu)化的Pregel API.本文所研究的是利用GraphX對(duì)大規(guī)模社會(huì)網(wǎng)絡(luò)進(jìn)行并行處理，保護(hù)隱私的同時(shí)提高算法的執(zhí)行效率，主要工作及貢獻(xiàn)如下：

1) 提出一種分布式節(jié)點(diǎn)分組算法NGM(node group merge)，基于GraphX的消息傳遞機(jī)制將互為N-hop鄰居的節(jié)點(diǎn)分為一組，有效的保護(hù)了敏感鏈接.

2) 提出了保護(hù)鏈接的分布式匿名方法DAPLR (Distributed Anonymous Protecting Link Relationships)，基于GraphX對(duì)NGM產(chǎn)生的分組進(jìn)行標(biāo)簽?zāi)涿沟媚涿麍DG*中，對(duì)于任意節(jié)點(diǎn)，都至少有其它(k-1)個(gè)節(jié)點(diǎn)包含自己的標(biāo)簽.

3 背景知識(shí)及問(wèn)題定義

本文假設(shè)攻擊者所具有的背景知識(shí)是節(jié)點(diǎn)的標(biāo)簽信息，因此，將社會(huì)網(wǎng)絡(luò)表示成節(jié)點(diǎn)帶標(biāo)簽的簡(jiǎn)單無(wú)向圖G=(V，E，L，δ)，其中V是節(jié)點(diǎn)集，每個(gè)節(jié)點(diǎn)表示社會(huì)網(wǎng)絡(luò)中一個(gè)用戶，E是邊的集合，代表網(wǎng)絡(luò)中用戶之間的鏈接關(guān)系，L是節(jié)點(diǎn)標(biāo)簽集，δ：V→L是節(jié)點(diǎn)到標(biāo)簽的映射.

定義1. (分組鏈接泄露) 已知社會(huì)網(wǎng)絡(luò)G=(V，E，L，δ)，C是節(jié)點(diǎn)集V的一個(gè)分組，u、v是分組C中的兩個(gè)節(jié)點(diǎn)，即：u∈C,v∈C，若節(jié)點(diǎn)u、v存在鏈接關(guān)系，則稱分組C存在分組鏈接泄露.

如圖1中，若由節(jié)點(diǎn)1、2、3構(gòu)建分組{1，2，3}，由于分組{1，2，3}內(nèi)節(jié)點(diǎn)1和2，2和3之間存在鏈接關(guān)系，則可知分組{1，2，3}存在分組鏈接泄露.

定義2.(安全分組) 社會(huì)網(wǎng)絡(luò)圖G=(V，E，L，δ)，C是節(jié)點(diǎn)集V中的任意分組，Dist(u,v)表示節(jié)點(diǎn)u、v的最短路徑長(zhǎng)度.如果分組C是安全的，則滿足條件：?u∈C∧?v∈C?Dist(u,v)≥2.

由定義2可知，分組C被認(rèn)為是安全的當(dāng)且僅當(dāng)分組內(nèi)任意兩節(jié)點(diǎn)u，v滿足：Dist(u,v)≥2.以圖G為例，給出一個(gè)安全分組過(guò)程.假設(shè)分組C={1}，并且分組中節(jié)點(diǎn)數(shù)目為3，圖G中滿足定義2的為節(jié)點(diǎn)3，4，5，6，7.若選擇節(jié)點(diǎn)4構(gòu)成分組 C={1，4}，此時(shí)與節(jié)點(diǎn)1，4最短距離均不小于2的只有節(jié)點(diǎn)6，因此生成分組{1，4，6}.從圖G可以看出，分組{1，4，6}不存在分組鏈接泄露.為了說(shuō)明這一點(diǎn)，下面給出嚴(yán)格的數(shù)學(xué)證明.

證明：反證法.假設(shè)分組C內(nèi)存在分組鏈接泄露，即分組C中存在節(jié)點(diǎn)u、v構(gòu)成邊(u，v)，此時(shí)節(jié)點(diǎn)u、v的最短路徑長(zhǎng)度Dist(u,v)=1，這與定義2中安全分組條件相矛盾，故假設(shè)不成立，分組不存在分組鏈接泄露.

定義3. (標(biāo)簽統(tǒng)一列表)已知社會(huì)網(wǎng)絡(luò)圖G=(V，E，L，δ)，C是節(jié)點(diǎn)集V中任意一個(gè)節(jié)點(diǎn)數(shù)目不小于m的分組，p={p0，p1，…，pk-1}是整數(shù)序列{0，1，…，m-1}一個(gè)大小為k(k≤m)的子集，若對(duì) v C， 其標(biāo)簽范化列表generlist.v由下面公式產(chǎn)生[10]：

list(p,i)={u(i+p0)modm,u(i+p1)mod m,…,u(i+pk-1)mod m}

(1)

如圖1中，假分組C={1，2}，并選擇k=2，則節(jié)點(diǎn)1，2的標(biāo)簽統(tǒng)一列表generlist.1={(Afri，20)，(Asi，25)}，generlist.2={(Asi，25) ( Afri，20)}.

4 保護(hù)鏈接關(guān)系的分布匿名算法DAPLR

DAPLR算法的主要思想：首先基于GraphX的消息傳遞機(jī)制，彼此互為N-hop鄰居的節(jié)點(diǎn)分為一組，然后標(biāo)簽?zāi)涿總€(gè)分組，達(dá)到抵抗節(jié)點(diǎn)重識(shí)別攻擊和保護(hù)敏感關(guān)系的目的.

4.1 分布式節(jié)點(diǎn)分組算法NGM

基于GraphX的“節(jié)點(diǎn)為中心”模式以及所提供的圖構(gòu)建操作，提出一種安全分組算法NGM：首先，將節(jié)點(diǎn)劃分為不同的分組；其次，通過(guò)多次迭代執(zhí)行“查找—合并—構(gòu)建新圖”完成安全分組，即初始化時(shí)，為節(jié)點(diǎn)添加一個(gè)被稱為groupid的組信息，用來(lái)描述節(jié)點(diǎn)所在分組，其初始值為節(jié)點(diǎn)的nodeid；節(jié)點(diǎn)通過(guò)傳遞并修改groupid完成分組.在合并分組時(shí)，將Dist(u,v)設(shè)置為2，即只在2-hop鄰居間進(jìn)行分組合并.因此，利用GraphX查找節(jié)點(diǎn)的2-hop鄰居成為問(wèn)題的關(guān)鍵.

定理1.G=(V,E,L,δ)是簡(jiǎn)單無(wú)向圖，其中?u∈V，?v∈V，節(jié)點(diǎn)u、v間的最短路徑長(zhǎng)度用Dist(u,v)表示，w∈{s|s∈V∧Dist(u,s)=1}，?w∈V且w∈{z|z∈V∧Dist(v,z)=1}.如果節(jié)點(diǎn)w是節(jié)點(diǎn)u的2-hop鄰居，即Dist(u,w)=2，則節(jié)點(diǎn)w滿足條件：

w∈{g|g∈V∧g≠u∧Dist(u,g)≠1}

證明：反證法.假設(shè)節(jié)點(diǎn)u、w不是2-hop鄰居，則u、w關(guān)系分三種情況：(1)Dist(u,w)>2；(2)u=2；(3)Dist(u,w)=1.若情況(1)成立，由題設(shè)Dist(u,v)=1，則此時(shí)節(jié)點(diǎn)v，w應(yīng)滿足Dist(v,w)>1，這種情況下與定理1中的條件w∈{z|z∈V∧Dist(v,z)=1}相矛盾，故不成立.情況(2)和情況(3)，如果兩者成立，可知此時(shí)與定理1中的條件w∈{g|g∈V∧g≠u∧Dist(u,g)≠1}相矛盾，故也不成立.綜上所述，假設(shè)不成立，節(jié)點(diǎn)w是節(jié)點(diǎn)u的2-hop鄰居.

這樣，利用GraphX通過(guò)兩次迭代找出2-hop鄰居節(jié)點(diǎn).第一次迭代，所有節(jié)點(diǎn)向鄰居節(jié)點(diǎn)發(fā)送一個(gè)帶有自身groupid的消息，收到消息的節(jié)點(diǎn)生成1-hop鄰居列表；第二次迭代，所有節(jié)點(diǎn)將1-hop鄰居列表再轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)，收到消息的節(jié)點(diǎn)遍歷所有列表，利用定理1找出所有2-hop鄰居，具體如算法1所示.

Algorithm1.Search 2-hop neighborhood

Input：messages

Output： The list of 2-hop neighborhood of vertex u

1 THNList←?；

2 long step = getSuperstep()；

3 if step = = 0 then

4 for each vertex u do

5 sendMessToNeighbors (vertext.groupid)；

6 else if step= =1 then

7 long neighborhoodlist=getValue(messages)；

8 sendMessToNeighbors(neighborhoodlist)；

9 else if step= =2 then；

10 for each messages do；

11 if the groupid isnot vertext u′s groupid then；

12 select groupid NotExistIN vertext u′s neighborhoodlist Into THNList；

13 return THNList；

以原始圖G為例，算法1如圖2所示，為了便于表述圖中省略了節(jié)點(diǎn)的nodeid，僅標(biāo)出了groupid.

當(dāng)Superstep=0時(shí)，節(jié)點(diǎn)向鄰居節(jié)點(diǎn)發(fā)送自己的groupid，即圖2(a)所示；如圖2(b)，當(dāng)Superstep=1時(shí)，節(jié)點(diǎn)收到消息后生成1-hop列表并將列表再次轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)，如節(jié)點(diǎn)2生成1-hop鄰居列表{1，3}，并將{1，3}轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)；在圖2(c)中，即Superstep=2時(shí)，節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)的列表，然后遍歷所有的列表，列表中不是自己1-hop鄰居且不是自己groupid的值就是自己的 2-hop鄰居，如節(jié)點(diǎn)4，收到列表{2，4}，{4}和{4，6}，除去1-hop列表{3，5，7}和4，剩余的2，6就是自己的2-hop鄰居.經(jīng)過(guò)兩次迭代后的最終結(jié)果如圖2(c)所示.

圖2 查找2-hop鄰居Fig.2 Search for 2-hop neighbors

完成2-hop鄰居查找后，利用“中間人”策略來(lái)進(jìn)行分組合并.所謂的“中間人”是指節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，如圖3(a)中，節(jié)點(diǎn)2就是節(jié)點(diǎn)節(jié)點(diǎn)1和3共同的“中間人”.其思想是：節(jié)點(diǎn)從2-hop鄰居列表中選出最小的groupid，將自己的groupid與此值以(key，value)形式發(fā)送給“中間人”， “中間人”根據(jù)收到的消息判斷哪些互為2-hop鄰居的節(jié)點(diǎn)能夠合并分組，具體如算法2所示.

Algorithm2.Group merge

Input：messages

1 long step = getSuperstep()；

2 if step = = 0 then

3 for each vertex u do

4 long min=getMinValue(THNList)；

5 sendMessToNeighbors ((vertext.groupid，min))；

6 else if step= =1 then

7 long mergerlist=getValue(messages)；

8 if IsExist (u.groupid=v.min and v.groupid = u.min) IN mergerlist then

9 sendMessToNeighbors(mergerlist)；

10 else if step= =2 then

11 u.groupid=min{u.group，u.min}；

以原始圖G為例，算法2如圖3所示.如圖3(a)，算法執(zhí)行3-5行，節(jié)點(diǎn)從2-hop鄰居列表中選出最小groupid，并以(key，value)形式發(fā)送給“中間人”；如圖3(b)，執(zhí)行7-9行，“中間人”判斷是否轉(zhuǎn)發(fā)消息，節(jié)點(diǎn)2滿足第8行，轉(zhuǎn)發(fā){(3，1)(1，3)}給鄰居；圖3(c)中，執(zhí)行第11行，節(jié)點(diǎn)3將自己的groupid為修改為groupid=1，節(jié)點(diǎn)4修改groupid為groupid=2.

每完成一次分組合并利用Spark提供的RDD(Resilient Distributed Datasets，RDD)構(gòu)建一個(gè)新圖.當(dāng)前圖的邊信息保存在edgeRdd，同時(shí)，將節(jié)點(diǎn)的nodeid和節(jié)點(diǎn)相應(yīng)的groupid信息以的形式保存在groupRdd.利用上述信息通過(guò)Graphx系統(tǒng)執(zhí)行兩次leffOuterJoin操作就可以得到新圖的邊信息，有了新圖的邊信息后利用GraphX系統(tǒng)中提供的Graph.fromEdgeTuples構(gòu)建出一個(gè)新圖，如此經(jīng)過(guò)多次迭代，完成節(jié)點(diǎn)的分組.以圖1為例，經(jīng)過(guò)多次迭代最后的分組結(jié)果為{1，3，5，7}，{2，4，6}.

圖3 節(jié)點(diǎn)分組合并Fig.3 Grouping and merging of nodes

4.2 節(jié)點(diǎn)標(biāo)簽?zāi)涿?/h3>

GraphX的編程遵循“節(jié)點(diǎn)為中心”模式，即以節(jié)點(diǎn)為中心，通過(guò)彼此間的消息傳遞來(lái)獨(dú)立完成任務(wù).因此，提出一種基于GraphX的節(jié)點(diǎn)標(biāo)簽?zāi)涿惴ǎ渌枷胧牵菏紫?，為每個(gè)分組產(chǎn)生一個(gè)相應(yīng)的虛擬節(jié)點(diǎn)，其鄰接節(jié)點(diǎn)是分組中各節(jié)點(diǎn)；其次，分組節(jié)點(diǎn)以(key，value)的形式發(fā)送自己的nodeid和標(biāo)簽列表給虛擬節(jié)點(diǎn)，虛擬節(jié)點(diǎn)收到消息后為分組中的節(jié)點(diǎn)產(chǎn)生標(biāo)簽統(tǒng)一列表，并將標(biāo)簽統(tǒng)一列表發(fā)送給分組節(jié)點(diǎn)；最后分組節(jié)點(diǎn)用標(biāo)簽統(tǒng)一列表替換原有標(biāo)簽列表完成匿名.如此，利用3個(gè)Superstep就能夠完成整個(gè)過(guò)程.

1)始狀態(tài)，左側(cè)的分組節(jié)點(diǎn)處于Active狀態(tài)，右側(cè)的虛擬節(jié)點(diǎn)處于Inactive狀態(tài).

2)Superstep=0，左側(cè)分組節(jié)點(diǎn)以(key，value)形式發(fā)送nodeid和標(biāo)簽列表給右側(cè)的虛擬節(jié)點(diǎn).

3)Superstep=1，虛擬節(jié)點(diǎn)收到消息，根據(jù)定義4為分組中節(jié)點(diǎn)產(chǎn)生標(biāo)簽統(tǒng)一列表，并將標(biāo)簽統(tǒng)一列表轉(zhuǎn)發(fā)給右側(cè)分組節(jié)點(diǎn).

4)Superstep=2，用戶節(jié)點(diǎn)收到消息后，將原有標(biāo)簽列表修改為標(biāo)簽統(tǒng)一列表.

具體如算法3所示.

Algorithm3.Generate Lable list

Input：messages

1 long step = getSuperstep()；

2 if step = = 0 then

3 for each vertex u do

4 if isLeft() then

5 sendMessToNeighbors((vertext.nodeid，vertext.labellist))；

6 else if step= =1 then

7 if notisLeft() then

8 long list=getValue(messages) ；

9 for vertext u in list do

10 new= (vertext.nodeid，vertext.generalizationlabellist)；

11 sendMessToNeighbors(new)；

12 else if step==2 then

13 if isLeft() then

14 long Anolabel=getValue(message)；

15 setValue(Anolabel)；

由于4.1節(jié)在分組時(shí)，并沒(méi)有考慮分組中節(jié)點(diǎn)的數(shù)目m的值，這個(gè)需要根據(jù)實(shí)際情況進(jìn)行相應(yīng)的調(diào)整.同樣以原始圖G為例，為了方便表述，原始圖G中節(jié)點(diǎn)1，2， …，7各自的標(biāo)簽列表，分別用相應(yīng)的符號(hào)t1，t2，…，t7來(lái)表示.以k=m=2為例，即分組中節(jié)點(diǎn)數(shù)目為2，因此，需要對(duì)4.1節(jié)產(chǎn)生的分組{1，3，5，7}，{2，4，6}做出相應(yīng)的調(diào)整，這里將原分組結(jié)果調(diào)整為{1，3}，{2，4，6}，{5，7}，則算法3的執(zhí)行過(guò)程如圖4所示.

圖4 標(biāo)簽?zāi)涿鸉ig.4 Label anonymous

4.3 算法安全性分析

DAPLR算法包括節(jié)點(diǎn)安全分組和節(jié)點(diǎn)標(biāo)簽?zāi)涿虼?，?duì)算法的安全性從這兩部分進(jìn)行分析.

定理2.已知圖G*是社會(huì)網(wǎng)絡(luò)圖G=(V，E，L，δ)由DAPLR算法得到的匿名圖，則當(dāng)攻擊者以節(jié)點(diǎn)標(biāo)簽為背景知識(shí)時(shí)，從匿名圖G*中識(shí)別出目標(biāo)的概率為1/k.

證明：由4.2節(jié)可知，對(duì)于任意節(jié)點(diǎn)u，在匿名圖G*中都有其余(k-1)個(gè)節(jié)點(diǎn)包含u的標(biāo)簽，因此當(dāng)攻擊者以節(jié)點(diǎn)標(biāo)簽為背景知識(shí)時(shí)，從G*中識(shí)別出目標(biāo)的概率不大于1/k.

定理3.已知圖G*是社會(huì)網(wǎng)絡(luò)圖G=(V，E，L，δ)由DAPLR算法得到的匿名圖，則匿名圖G*不存在分組鏈接泄露.

分析DAPLR算法可知，需要證明NGM算法產(chǎn)生的分組內(nèi)不存在鏈接，而定義2和定理1證明了NGM算法在分組合并中不會(huì)導(dǎo)致分組存在鏈接，因此只需要證明，新圖的構(gòu)建不會(huì)導(dǎo)致分組內(nèi)有鏈接存在.

證明：NGM算法的第i次構(gòu)建的圖用Gi來(lái)表示，Si是圖Gi中的一個(gè)節(jié)點(diǎn).根據(jù)算法1和算法2可知，Si是圖Gi-1中兩個(gè)互為2-hop的節(jié)點(diǎn)u和v構(gòu)成的超級(jí)節(jié)點(diǎn)，因此節(jié)點(diǎn)Si的鏈接關(guān)系繼承點(diǎn)u、v的鏈接關(guān)系，即在圖Gi-1中節(jié)點(diǎn)u和v的1-hop鄰居節(jié)點(diǎn)，都會(huì)轉(zhuǎn)變成節(jié)點(diǎn)Si在圖Gi的1-hop鄰居節(jié)點(diǎn)，因此在第(i+1)迭代中不會(huì)將鏈接引入分組.

圖5 構(gòu)建的新圖G1Fig.5 New graph G1

以圖1為例，NGM算法首次構(gòu)建的圖5所示，在圖G1中，圖中圓圈中數(shù)字表示groupip，花括號(hào)中數(shù)字表示分組包含的節(jié)點(diǎn).對(duì)比圖1可知，節(jié)點(diǎn)2、4將1-hop鄰居節(jié)點(diǎn)轉(zhuǎn)變成圖G1中節(jié)點(diǎn)2的1-hop鄰居，節(jié)點(diǎn)1、3亦是如此.通過(guò)實(shí)例也說(shuō)明了NGM算法不會(huì)將鏈接引入分組.

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

5.1 數(shù)據(jù)集與實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)對(duì)DAPLR方法進(jìn)行性能分析和評(píng)價(jià)，采用真實(shí)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集com-LiveJournl，其中com-LiveJournal數(shù)據(jù)集包含3，997，962個(gè)節(jié)點(diǎn)和34，681，189條邊.DAPLR隱私保護(hù)方法涉及到節(jié)點(diǎn)標(biāo)簽而數(shù)據(jù)集并不包含標(biāo)簽信息，因此實(shí)驗(yàn)中人工生成節(jié)點(diǎn)標(biāo)簽列表信息.每個(gè)節(jié)點(diǎn)的標(biāo)簽列表由3個(gè)屬性構(gòu)成：國(guó)籍(80個(gè)國(guó)家)、性別(男或女)、年齡(15～75)，所有的值滿足同一分布.

為了便于對(duì)比，實(shí)驗(yàn)將數(shù)據(jù)集隨機(jī)等分為5份并按1∶2∶3∶4∶5重新整合數(shù)據(jù)，產(chǎn)生5個(gè)數(shù)據(jù)集，即split1-split5；然后，利用三種算法對(duì)每個(gè)split進(jìn)行匿名：1) 將社會(huì)網(wǎng)絡(luò)圖轉(zhuǎn)化為二分圖，在單工作站環(huán)境下利用文獻(xiàn)[10]進(jìn)行匿名，運(yùn)行結(jié)果記做“Bipartite”，2) 在單工作站環(huán)境下利用安全分組和標(biāo)簽統(tǒng)一列表對(duì)社會(huì)網(wǎng)絡(luò)進(jìn)行匿名，實(shí)驗(yàn)結(jié)果記做 “Sequential”，3) 利用DAPLR算法匿名社會(huì)網(wǎng)絡(luò)圖，記為“DAPLR”.

實(shí)驗(yàn)分別在單工作站和分布式環(huán)境匿名數(shù)據(jù)split1-split5，下面是兩種不同測(cè)試環(huán)境下的軟硬件配置：

單工作站環(huán)境：Intel Core i7-2720QM，CPU 2.2Ghz，16G RAM；操作系統(tǒng)：win7 旗艦版；編程語(yǔ)言：VC++2010

分布式環(huán)境：11個(gè)計(jì)算節(jié)點(diǎn)，Hadoop 2.7.2，Spark1.6.3； CPU 1.8GHz，16GB RAM，編程語(yǔ)言：Scala 2.10.4.

5.2 算法性能分析

實(shí)驗(yàn)從兩個(gè)方面對(duì)DAPLR算法進(jìn)行性能分析和評(píng)價(jià)：計(jì)算開銷以及算法的復(fù)雜度.

5.2.1 運(yùn)行時(shí)間

實(shí)驗(yàn)采用執(zhí)行時(shí)間作為評(píng)測(cè)DAPLR算法計(jì)算開銷的評(píng)測(cè)標(biāo)準(zhǔn)，并與單工作站環(huán)境下的“Bipartite”和“Sequential”做對(duì)比，實(shí)驗(yàn)結(jié)果如圖6所示.

圖6 運(yùn)行時(shí)間Fig.6 Run time

圖7 運(yùn)行時(shí)間隨worker數(shù)量的變化Fig.7 Running time varies with the number of workers

圖6展示了單工作站環(huán)境下“Bipartite”和“Sequential”方法，以及DAPLR算法消耗時(shí)間的對(duì)比圖.從圖中可以看出，“Sequential”方法所消耗的時(shí)間要高于“Bipartite”，這是因?yàn)樗岢龅陌踩纸M條件使得“Sequential”方法需要對(duì)圖進(jìn)行多次遍歷，需要說(shuō)明的是，實(shí)驗(yàn)中“Bipartite”并未考慮社會(huì)網(wǎng)絡(luò)圖轉(zhuǎn)化為二分圖時(shí)所產(chǎn)生的消耗.同時(shí)，實(shí)驗(yàn)結(jié)果顯示 “Sequential”和“Bipartite”消耗的時(shí)間要高于DAPLR方法，并且隨著數(shù)據(jù)集的增大，這種趨勢(shì)愈加明顯.從實(shí)驗(yàn)結(jié)果中可以看出，所提出的DAPLR算法在處理大規(guī)模數(shù)據(jù)上更具優(yōu)勢(shì).

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

實(shí)驗(yàn)采用兩個(gè)方法來(lái)評(píng)測(cè)DAPLR算法的復(fù)雜度：

1)保持?jǐn)?shù)據(jù)規(guī)模不變，逐漸增加計(jì)算節(jié)點(diǎn)(worker)數(shù)目；

2)規(guī)模擴(kuò)展性(Scalability).

圖7顯示了DAPLR算法處理數(shù)據(jù)集split3時(shí)，隨著worker數(shù)目增加處理時(shí)間的變化情況.實(shí)驗(yàn)結(jié)果顯示，隨著worker數(shù)目的遞增，處理數(shù)據(jù)所消耗的時(shí)間逐漸減少，大致呈線性變化.但在worker=9時(shí)，處理時(shí)間變化不再明顯，這是因?yàn)殡S著worker數(shù)量的增加，worker彼此間通信量增加，產(chǎn)生更多的額外開銷.

規(guī)模擴(kuò)展性是評(píng)價(jià)并行算法的一個(gè)重要方法，方法是：保持計(jì)算數(shù)目不變，擴(kuò)大數(shù)據(jù)規(guī)模，是用來(lái)測(cè)試算法時(shí)間復(fù)雜度的一個(gè)方法，其計(jì)算公式：

(2)

圖8 規(guī)模擴(kuò)展性Fig.8 Scalability

圖9 查詢錯(cuò)誤率Fig.9 Query error rate

其中，T(*)是處理相應(yīng)數(shù)據(jù)集消耗的時(shí)間，實(shí)驗(yàn)將split1作為DB，并用split1-split5 這5個(gè)數(shù)據(jù)集作為 m×DB，并在集群運(yùn)行，所得結(jié)果如圖8所示.由公式可知，理想情況下sizeup應(yīng)不大于數(shù)據(jù)規(guī)模比例，從圖8中可知，算法在split1-split3具有很好的規(guī)模擴(kuò)展性，而從split4開始，sizeup則逐漸大于數(shù)據(jù)規(guī)模比例，其主要原因是受限于服務(wù)器的CPU計(jì)算能力，另外就是隨著數(shù)據(jù)規(guī)模的增大，數(shù)據(jù)輸入的時(shí)間會(huì)有所增加.

5.3 數(shù)據(jù)可用性分析

社會(huì)網(wǎng)絡(luò)圖匿名化處理的目的在于通過(guò)圖修改操作來(lái)防止用戶隱私信息泄露，同時(shí)保證匿名圖在社會(huì)網(wǎng)絡(luò)分析和圖查詢方面的數(shù)據(jù)可用性.DAPLR算法在對(duì)社會(huì)網(wǎng)絡(luò)圖進(jìn)行匿名處理時(shí)并沒(méi)有修改圖結(jié)構(gòu)，因此針對(duì)圖結(jié)構(gòu)的查詢?nèi)缙骄疃搪窂健⒕奂禂?shù)、節(jié)點(diǎn)可達(dá)性等都會(huì)與在原圖上查詢結(jié)果相一致.因此，實(shí)驗(yàn)通過(guò)查詢準(zhǔn)確性來(lái)評(píng)價(jià)算法在數(shù)據(jù)可用性上的表現(xiàn).

圖10 單跳查詢錯(cuò)誤率圖11 雙跳查詢錯(cuò)誤率Fig.10 Single-hop queryFig.11 Dual-hop query error rateerror rate

針對(duì)查詢操作，實(shí)驗(yàn)采用文獻(xiàn)[10]所提出的單跳查詢和雙跳查詢作為評(píng)測(cè)方法，并用查詢相對(duì)誤差率作為度量標(biāo)準(zhǔn).相對(duì)誤差計(jì)算公式為|N-N*|/N，其中N表示原始圖數(shù)據(jù)上的查詢結(jié)果， 表示匿名圖數(shù)據(jù)上查詢結(jié)果.實(shí)驗(yàn)采用不同的屬性進(jìn)行多次查詢計(jì)算誤差率，取查詢誤差的平均值.實(shí)驗(yàn)結(jié)果如圖9、圖10和圖11所示.

圖9是為了評(píng)測(cè)算法查詢準(zhǔn)確性所提出查詢 “在不同年齡段，A國(guó)用戶和B國(guó)用戶間存在多少朋友關(guān)系”所得到的平均相對(duì)誤差.從圖中可以看出，在不同年齡段隨著閾值k、m的變化平均誤差有所變化，但都能維持在10%左右，匿名后的圖數(shù)據(jù)仍具有較好地可用.

圖10和圖11分別展示了單跳查詢和雙跳查詢隨分組中節(jié)點(diǎn)數(shù)目m變化的情況.從實(shí)驗(yàn)結(jié)果中可以看出，隨著分組中節(jié)點(diǎn)數(shù)目m值的增加，查詢誤差率隨之增大，因?yàn)殡S著分組中節(jié)點(diǎn)數(shù)目增多使得節(jié)點(diǎn)的候選標(biāo)簽數(shù)隨之增加，從而導(dǎo)致查詢結(jié)果的相對(duì)誤差變大.

6 結(jié)束語(yǔ)

針對(duì)當(dāng)前社會(huì)網(wǎng)絡(luò)隱私保護(hù)方法忽視節(jié)點(diǎn)敏感鏈接，以及處理大規(guī)模圖數(shù)據(jù)存在極大局限性的問(wèn)題，提出一種利用分布式圖處理系統(tǒng)GraphX的DAPLR社會(huì)網(wǎng)絡(luò)隱私保護(hù)方法.DAPLR方法依據(jù)分布式圖處理系統(tǒng)GraphX編程遵循“節(jié)點(diǎn)為中心”模式的特點(diǎn)，通過(guò)節(jié)點(diǎn)間的消息傳遞進(jìn)行安全分組和標(biāo)簽?zāi)涿?，在提供隱私保護(hù)的同時(shí)保證了數(shù)據(jù)的可用性.真實(shí)社會(huì)網(wǎng)絡(luò)中，隨著時(shí)間的演變，用戶之間會(huì)建立新的鏈接關(guān)系或取消彼此間的聯(lián)系，有的用戶甚至?xí)顺錾鐣?huì)網(wǎng)絡(luò)，DAPLR方法并沒(méi)有考慮社會(huì)網(wǎng)絡(luò)的這種動(dòng)態(tài)演變的特性，因此，接下來(lái)將考慮利用GraphX對(duì)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)進(jìn)行隱私保護(hù).