張曉琳，何曉玉，張換香，李卓麟

內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭 014010

1 引言

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，社會網(wǎng)絡(luò)分析在眾多領(lǐng)域獲得廣泛關(guān)注和應(yīng)用。社會網(wǎng)絡(luò)分析需要將網(wǎng)絡(luò)數(shù)據(jù)發(fā)布給第三方，由于社會網(wǎng)絡(luò)數(shù)據(jù)包含用戶的隱私信息，如何在發(fā)布數(shù)據(jù)的同時保護(hù)用戶的隱私信息成為研究的熱點(diǎn)。社會網(wǎng)絡(luò)通常被表示成簡單圖，圖中的節(jié)點(diǎn)和邊分別對應(yīng)社會網(wǎng)絡(luò)中的個體以及個體間的聯(lián)系，個體的屬性信息，如年齡則表示成節(jié)點(diǎn)的標(biāo)簽，如圖1所示。

Fig.1 Social network graphG圖1 社會網(wǎng)絡(luò)原始圖G

重識別(re-identification)攻擊[1]，是指攻擊者通過與攻擊目標(biāo)相關(guān)的背景知識(如度、鄰居子圖等)，從網(wǎng)絡(luò)中識別出目標(biāo)的過程。為了抵抗重識別攻擊，研究者提出了不同的社會網(wǎng)絡(luò)圖匿名化技術(shù)，通過修改圖結(jié)構(gòu)防止隱私信息泄露，如k-degree匿名[2]?，F(xiàn)實(shí)中，攻擊者能夠很輕易地獲取到與目標(biāo)相關(guān)的多種背景知識，簡單地通過修改圖結(jié)構(gòu)并不能很好地保護(hù)個體的隱私。

Fig.2 Two anonymized versions forG圖2 圖G的兩個匿名圖

為此，提出一種分布式社會網(wǎng)絡(luò)匿名方法，目的是在提高處理大規(guī)模社會網(wǎng)絡(luò)效率的同時，得到匿名圖，如圖2（b）所示。在圖中，即使攻擊者獲知節(jié)點(diǎn)的度和標(biāo)簽，也無法準(zhǔn)確推測出被攻擊者的身份及鏈接關(guān)系。例如攻擊者獲知Bob在社會網(wǎng)絡(luò)中擁有3個朋友，27歲且來自America，圖中節(jié)點(diǎn)2和4均符合條件，則攻擊者準(zhǔn)確識別出Bob的概率不大于1/2，且由于節(jié)點(diǎn)2和4不存在鏈接，攻擊者也無法推測出Bob的鏈接關(guān)系。

2 相關(guān)工作

隨著在線社會網(wǎng)絡(luò)的發(fā)展和普及，社會網(wǎng)絡(luò)隱私信息的安全性成為研究學(xué)者關(guān)注的熱點(diǎn)，并提出了多種保護(hù)方法。文獻(xiàn)[4]引入屬性-社交網(wǎng)絡(luò)模型將屬性信息視作節(jié)點(diǎn)，通過分割節(jié)點(diǎn)屬性鏈接和社交鏈接保護(hù)用戶隱私。文獻(xiàn)[5]提出一種基于kdegree匿名的隱私保護(hù)模型SimilarGraph，采用動態(tài)規(guī)劃的方法對節(jié)點(diǎn)進(jìn)行最優(yōu)簇劃分，在保護(hù)隱私的同時保持社會網(wǎng)絡(luò)圖結(jié)構(gòu)性質(zhì)。文獻(xiàn)[6]提出一種kweighted-degree匿名方法，在匿名圖中，對任意節(jié)點(diǎn)，至少存在（k-1）個其他節(jié)點(diǎn)與其度相同且在閾值t范圍內(nèi)具有相同的權(quán)重序列。文獻(xiàn)[7]提出一種utilityaware匿名方法，在進(jìn)行k-degree匿名時同時考慮最短路徑和鄰居節(jié)點(diǎn)重疊程度，提高了匿名圖的數(shù)據(jù)可用性。文獻(xiàn)[8]指出即使個體的身份信息被有效隱藏，攻擊者仍能推測出個體的鏈接關(guān)系，為此設(shè)計了一種L-opacity匿名模型，通過opacity矩陣在保護(hù)個體身份的同時保護(hù)鏈接關(guān)系。文獻(xiàn)[9]將用戶交互社會網(wǎng)絡(luò)抽象成二分圖模型，通過為用戶產(chǎn)生一個標(biāo)簽列表的方式抵抗重識別攻擊。文獻(xiàn)[10]針對敏感鏈接關(guān)系設(shè)計一個LinkMirage模型，模糊社會網(wǎng)絡(luò)圖中的社交拓?fù)浣Y(jié)構(gòu)并提供帶有模糊社交關(guān)系視圖的不受信任的外部應(yīng)用，從而抵抗重識別攻擊。文獻(xiàn)[11]提出添加偽節(jié)點(diǎn)，并在真實(shí)節(jié)點(diǎn)和偽節(jié)點(diǎn)間添加邊的k-degree匿名方法。文獻(xiàn)[12-13]提出了基于社區(qū)的圖匿名模型，在k-degree匿名的同時，提高匿名圖的數(shù)據(jù)可用性。文獻(xiàn)[14]提出一種基于單變量微聚合的k-degree匿名方案，通過建立差矩陣Mp×2提高數(shù)據(jù)的可用性。文獻(xiàn)[15]提出了基于SMC（secure multi-party computation）模型的隱私保護(hù)方案，“數(shù)據(jù)代理”通過分布匿名協(xié)議實(shí)現(xiàn)標(biāo)簽屬性和存儲位置的l-diversity匿名。文獻(xiàn)[16]提出一種基于SMC模型的semi-honest的交換加密技術(shù)，保護(hù)隱私信息。文獻(xiàn)[17]提出基于MapReduce模型的隱私保護(hù)方案，通過兩個階段實(shí)現(xiàn)k-匿名。文獻(xiàn)[18-19]則利用Map-Reduce框架在大規(guī)模圖中檢索同構(gòu)子圖。

可以看出，目前的隱私保護(hù)技術(shù)多關(guān)注匿名數(shù)據(jù)的可用性，忽略了攻擊者可能具有多種背景知識的情況。此外，現(xiàn)有的分布式隱私保護(hù)技術(shù)針對的是關(guān)系型數(shù)據(jù)，未考慮個體在社會網(wǎng)絡(luò)中的圖性質(zhì)特征，不能很好地保護(hù)個體的隱私，并且MapReduce將中間結(jié)果存放于磁盤，處理過程中需要反復(fù)遷移數(shù)據(jù)，并不適合處理圖數(shù)據(jù)。為此，提出一種分布式匿名方法 PLRD-（k,m）（distributedk-degree-m-label anonymity with protecting link relationships），該方法基于GraphX系統(tǒng)[20-21]，在保護(hù)隱私的同時提高算法的執(zhí)行效率。

3 背景知識及問題定義

社會網(wǎng)絡(luò)表示成節(jié)點(diǎn)帶標(biāo)簽的簡單無向圖G=(V,E,L,δ)，其中節(jié)點(diǎn)集V代表社會網(wǎng)絡(luò)中的用戶，E是邊集合代表用戶間的聯(lián)系，社會網(wǎng)絡(luò)中個體的屬性信息用節(jié)點(diǎn)標(biāo)簽L表示，函數(shù)δ表示節(jié)點(diǎn)與標(biāo)簽之間的映射δ:V→L。

定義1（標(biāo)簽鏈接泄露）已知G*是社會網(wǎng)絡(luò)圖G=(V,E,L,δ)的匿名圖，C是攻擊者通過標(biāo)簽信息得到的一組節(jié)點(diǎn)，對?u∈C，?v∈C，若攻擊者能以一定概率推測出u、v存在鏈接，則稱C存在標(biāo)簽鏈接泄露。

以圖2（a）為例，攻擊者通過目標(biāo)27歲，得到節(jié)點(diǎn)3和4，此時，能推測節(jié)點(diǎn)3和4存在鏈接，因此{(lán)3,4}存在標(biāo)簽鏈接泄露。

定義2（PLR-（k,m）匿名）已知G*是社會網(wǎng)絡(luò)圖G=(V,E,L,δ)的匿名圖，若圖G*是PLR-（k,m）匿名，則滿足：

（1）圖G*是k-degree匿名圖，即攻擊者通過節(jié)點(diǎn)的度，識別出目標(biāo)節(jié)點(diǎn)的概率不大于1/k。

（2）圖G*是m-標(biāo)簽?zāi)涿麍D，即攻擊者通過節(jié)點(diǎn)標(biāo)簽，識別出目標(biāo)節(jié)點(diǎn)的概率不大于1/m。

（3）匿名圖G*不存在標(biāo)簽鏈接泄露。

定義3（最大缺失值）已知社會網(wǎng)絡(luò)圖G=(V,E,L,δ)，Ci(i=1,2,…,k)是包含k個節(jié)點(diǎn)的分組，且Ci∧Ci+1=? ，Δi是分組Ci內(nèi)節(jié)點(diǎn)度最大值與最小值的差，若M是最大缺失值，則M=max{Δ1,Δ2,…,Δi,Δi+1,…,Δn}[11]。

以圖1為例，若分組C1={3,5,1,7},C2={4,2,6}，則此時最大缺失值M=max{(2-1),(3-1)}=2。

定義4（無向完全圖）若圖G={V,E}是無向完全圖，則滿足條件：

?u∈V,?v∈V?(u,v)∈E

4 分布式隱私保護(hù)算法PLRD-(k,m)

GraphX是Spark上用于圖和并行圖計算的處理系統(tǒng)，編程模型上遵循“節(jié)點(diǎn)為中心”模式，計算過程由若干順序執(zhí)行的超級步（superstep）組成，在超級步S中，節(jié)點(diǎn)匯總從超級步(S-1)中其他節(jié)點(diǎn)傳遞過來的消息，改變自身的狀態(tài)，并向其他節(jié)點(diǎn)發(fā)送消息，消息經(jīng)過同步后，會在超級步(S+1)中被其他節(jié)點(diǎn)接收并做出處理。同時，GraphX引入了擴(kuò)展自Spark RDD的屬性圖，并提供了一組基本功能操作，如圖構(gòu)造操作、圖反轉(zhuǎn)等，以及優(yōu)化的PregelAPI。

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

為了滿足定義2中的條件（3），提出一個節(jié)點(diǎn)安全分組條件SGC（safety grouping condition）。若設(shè)C是包含k個節(jié)點(diǎn)的分組，若分組C滿足SGC，則對?u∈C,?v∈C，兩節(jié)點(diǎn)的最短路徑長度應(yīng)滿足dist(u,v)≥2。

定理1已知社會網(wǎng)絡(luò)圖G=(V,E,L,δ)，C是節(jié)點(diǎn)集V中k個節(jié)點(diǎn)構(gòu)成的分組，dist(u,v)表示節(jié)點(diǎn)u、v的最短路徑長度，若?u∈C，?v∈C，滿足dist(u,v)≥ 2，則分組C不存在鏈接。

證明反證法。假設(shè)分組C存在鏈接，則分組C內(nèi)必存在節(jié)點(diǎn)u、v滿足條件dist(u,v)=1，這與?u∈C，?v∈C，滿足dist(u,v)≥2相矛盾，假設(shè)不成立，故定理1成立。

基于定理1和模塊化社區(qū)發(fā)現(xiàn)的思想[22]，提出一種分布式節(jié)點(diǎn)分組算法FUG（fast unfolding of group），基本步驟如下：

（1）初始化，為節(jié)點(diǎn)添加分組信息groupid，將節(jié)點(diǎn)劃分在不同的分組。

（2）節(jié)點(diǎn)搜索2-hop鄰居，并修改groupid合并分組。

（3）構(gòu)建新圖，新圖中的節(jié)點(diǎn)是步驟（2）產(chǎn)生的不同分組。

重復(fù)步驟（2）和（3），直至構(gòu)建的新圖是完全圖，程序結(jié)束。FUG算法分為兩個階段（phase），如圖3。圖3中，圓圈內(nèi)數(shù)字是groupid，花括號內(nèi)數(shù)字是分組所包含的節(jié)點(diǎn)（nodeid）。

Fig.3 Fast unfolding of group圖3 FUG算法

由圖3可以看出，在Phase1階段，節(jié)點(diǎn)搜索2-hop鄰居，并修改groupid合并分組，而Phase2階段則構(gòu)建新圖并進(jìn)入下一輪迭代。

定理2已知社會網(wǎng)絡(luò)圖G=(V,E,L,δ)，對 ?u∈V，?v∈V，dist(u,v)表示節(jié)點(diǎn)u和v的最短路徑長度，v滿足v∈{s|s∈V∧dist(u,s)=1}，w∈V且w∈{z|z∈V∧dist(v,z)=1}，若w是u的2-hop鄰居節(jié)點(diǎn)，即dist(u,w)=2，則節(jié)點(diǎn)w滿足：

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

證明反證法。假設(shè)節(jié)點(diǎn)w不是節(jié)點(diǎn)u的2-hop節(jié)點(diǎn)，則u、w的關(guān)系分為三種情形：（1）dist(u,w)≥2；（2）u=w；（3）dist(u,w)=1。若情形（1）成立，由題設(shè)v∈{s|s∈V∧dist(u,s)=1}，則dist(v,w)＞1，這與w∈{z|z∈V∧dist(v,z)=1}矛盾，故情形（1）不成立；若（2）和（3）成立，則與w∈{g|g∈V∧g≠u∧dist(u,g)≠1}相矛盾，故（2）和（3）不成立。綜上所述，假設(shè)不成立，節(jié)點(diǎn)w是節(jié)點(diǎn)u的2-hop鄰居節(jié)點(diǎn)。□

基于定理2，利用GraphX系統(tǒng)通過兩次迭代,節(jié)點(diǎn)便能搜索到2-hop鄰居節(jié)點(diǎn)。第一次迭代，節(jié)點(diǎn)向鄰居節(jié)點(diǎn)發(fā)送groupid，收到消息的節(jié)點(diǎn)生成1-hop鄰居列表；第二次迭代，節(jié)點(diǎn)將1-hop鄰居列表發(fā)送給鄰居節(jié)點(diǎn)，收到消息的節(jié)點(diǎn)遍歷列表，依據(jù)定理2生成2-hop鄰居列表，具體如算法1所示。

算法1搜索2-hop鄰居

Input：messages.

Output：The list of 2-hop neighborhood of vertexu.

1.THNList;//初始化2-hop鄰居節(jié)點(diǎn)列表

2.longstep=getsuperstep();//取出超級步

3.ifstep==0 then

4.for each vertexudo

5.sendMessToNeighbors(vertext.groupid);//超級步為0時，節(jié)點(diǎn)發(fā)送groupid給鄰居節(jié)點(diǎn)

6.else ifstep==1 then

7.longneighborhoodlist=getValue(messages);//取出消息，生成1-hop鄰居節(jié)點(diǎn)列表

8.sendMessToNeighbors(neighborhoodlist);//發(fā)送1-hop鄰居列表給鄰居節(jié)點(diǎn)

9.else ifstep==2 then

10.for each message do//處理所有1-hop鄰居節(jié)點(diǎn)列表

11.if the groupid in messages meet the conditions{groupid≠u.groupid}∧{groupid?u.neighborhoodlist}

12.THNList←groupid;//添加2-hop鄰居列表

13.returnTHNList;

以圖1為例，算法1如圖4所示。為了便于表述，圖中省略了nodeid，僅標(biāo)出了groupid。

Fig.4 2-hop neighbor search圖4 2-hop鄰居搜索

當(dāng)superstep=0時，節(jié)點(diǎn)向鄰居節(jié)點(diǎn)發(fā)送自己的groupid，如圖4（a）；當(dāng)superstep=1時，節(jié)點(diǎn)收到消息后生成1-hop鄰居列表，并將列表轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)，例如節(jié)點(diǎn)2根據(jù)消息1和3，生成列表{1,3}，并將{1,3}轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)，如圖4（b）；當(dāng)superstep=2 時，收到消息的節(jié)點(diǎn)遍歷所收到的列表，依據(jù)定理2產(chǎn)生2-hop鄰居列表，例如節(jié)點(diǎn)4收到列表{2,4}，{4}和{4,6}，依據(jù)定理2，排除1-hop列表{3,5,7}和自身groupid=4，則THNList={2,6}，如圖4（c）。

從圖4（c）可以看出，若隨機(jī)修改groupid，可能無法合并分組。以3、5、7為例，若3修改為5，5修改為7，7修改為3，此時分組未發(fā)生變化。為此，提出一種W&N（will-negotiation）策略。在W&N策略中，節(jié)點(diǎn)是鄰居節(jié)點(diǎn)的“調(diào)解人”，如圖5（a），節(jié)點(diǎn)4是節(jié)點(diǎn)3和5的“調(diào)解人”，思想是：

（1）節(jié)點(diǎn)u從2-hop鄰居列表中選出最小的groupid，連同自身groupid以（u.groupid,u.min）形式發(fā)送給“調(diào)解人”。

（2）若消息存在節(jié)點(diǎn)u和v滿足：u.groupid=v.min∧v.groupid=u.min，則“調(diào)解人”返回（u.groupid,v.groupid）給節(jié)點(diǎn)u、v。

（3）節(jié)點(diǎn)u、v收到消息后，將自身groupid修改為（u.groupid,v.groupid）中最小的值。

具體如算法2所示。

算法2Group merge

Input：messages.

1.longstep=getsuperstep();//取出超級步

2.ifstep==0 then

3.for each vertexudo

4.longu.min=getMinValue(THNList);//選擇最小groupid

5.sendMessToNeighbors((u.groupid,u.min));//節(jié)點(diǎn)u發(fā)送(u.groupid,u.min)給“調(diào)解人”

6.else ifstep==1 then

7.longmergerlist=getValue(messages);

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

9.sendMessToNeighbors(u.groupid,v.groupid);//“調(diào)解人”返回消息給鄰居節(jié)點(diǎn)

10.else ifstep==2 then

11.u.groupid=min{u.groupid,v.groupid};//修改groupid

以圖1為例，算法2如圖5所示。當(dāng)superstep=0時，節(jié)點(diǎn)從2-hop鄰居列表中選出最小groupid，并以（u.groupid,u.min.groupid）的形式發(fā)送給“調(diào)解人”，如圖5（a）；當(dāng)superstep=1時，“調(diào)解人”判斷是否轉(zhuǎn)發(fā)消息，例如節(jié)點(diǎn)2滿足算法第8行，則轉(zhuǎn)發(fā){(3,1)(1,3)}給節(jié)點(diǎn)1和3，如圖5（b）；當(dāng)superstep=2 時，算法執(zhí)行第11行，節(jié)點(diǎn)3將自身groupid修改為groupid=1，節(jié)點(diǎn)4修改為groupid=2，如圖5（c）。

Fig.5 Grouping merged圖5 分組合并

由圖3可知，在Phase1結(jié)束后，F(xiàn)UG算法轉(zhuǎn)入Phase2階段構(gòu)造新圖，使用RDD（resilient distributed datasets）很方便實(shí)現(xiàn)。FUG算法將當(dāng)前圖的邊信息＜srcid,dstid＞保存在edgeRdd。節(jié)點(diǎn)的nodeid和相應(yīng)的groupid信息，以 ＜nodeid,groupid＞的形式保存在groupRdd，然后執(zhí)行兩次leffOuterJoin操作得到新圖的邊信息，最后通過GraphX系統(tǒng)的Graph.fromEdge-Tuples從新圖的邊信息后構(gòu)建出新圖，首次構(gòu)建的新圖如圖3（c）所示。

如此，經(jīng)過3次循環(huán)迭代，圖G的最終分組結(jié)果為：group1={1,3,5,7}和group2={2,4,6}。

4.2 分布式k-degree匿名

為了不向分組引入鏈接，k-degree匿名采用添加節(jié)點(diǎn)和邊的方式實(shí)現(xiàn)，并要求添加的邊(u,v)滿足條件：u∈V∧v∈V*，其中V*是添加的節(jié)點(diǎn)集，而V*中節(jié)點(diǎn)的數(shù)目可以通過式（1）得出[11]。

其中，k是分組中節(jié)點(diǎn)數(shù)目，M是最大缺失值。

定理3FUG算法收斂，且當(dāng)算法收斂時，構(gòu)建的新圖Gn是無向完全圖。

證明反證法。（1）假設(shè)Gn是無向完全圖時，F(xiàn)UG未收斂。根據(jù)定義4，在圖Gn中，任意節(jié)點(diǎn)u和v，滿足dist(u,v)=1，由算法1，此時節(jié)點(diǎn)u和v轉(zhuǎn)變?yōu)镮nActive狀態(tài)，F(xiàn)UG算法收斂，假設(shè)不成立。（2）假設(shè)FUG算法收斂時，圖Gn不是無向完全圖，由定義4可知，此時圖Gn中，存在節(jié)點(diǎn)u和v滿足dist(u,v)≥2，節(jié)點(diǎn)仍處于Active狀態(tài)，F(xiàn)UG算法會繼續(xù)執(zhí)行，未收斂，假設(shè)不成立。綜上所述，定理3成立。

由于Gn是完全圖，節(jié)點(diǎn)彼此間可以通信，因此通過GraphX可以很容易地計算出最大缺失值M。節(jié)點(diǎn)分組時，F(xiàn)UG算法并未考慮參數(shù)k。因此，計算M值時，首先要對4.1節(jié)產(chǎn)生的分組進(jìn)行分割，方法是：將分組節(jié)點(diǎn)按度值降序排列，每k個節(jié)點(diǎn)劃分成一個子分組（subgroup），若最后一個子分組節(jié)點(diǎn)數(shù)目不足k，則與前一個子分組合并。計算最大缺失值M的步驟如下：

（1）初始化，分組劃分成若干子分組，子分組計算subi=|dmax-dmin|，即節(jié)點(diǎn)度最大值與最小值的差，令M=max{sub1,sub2,…,subn} 。

（2）superstep%2=0時，發(fā)送M值給鄰居節(jié)點(diǎn)。

（3）superstep%2=1時，節(jié)點(diǎn)將消息對比自身M值。若大于自身值，則更新為收到的M值，保持Active狀態(tài)，否則轉(zhuǎn)為InActive狀態(tài)。

（4）重復(fù)（2）（3），直至節(jié)點(diǎn)處于InActive狀態(tài)。

具體如算法3所示。

算法3Computing max deficiency

Input：messages,k.

Output：Max deficiencyM.

1.Initialization;//初始化，將group劃分成若干subgroup，并計算M值

2.longstep=getsuperstep();//取出超級步

3.ifstep%2==0 then

4.sendMessToNeighbors(M);//發(fā)送M給鄰居節(jié)點(diǎn)

5.ifstep%2==1 then

6.longValue=getValue(messages);//取出M值

7.ifValue＞M;

8.setM=Value;//更新自己的M值

9.else

10.voteToHalt();//轉(zhuǎn)為InActive狀態(tài)

11.returnM;

以4.1節(jié)產(chǎn)生的分組{5,3,1,7}和{2,4,6}為例，并假設(shè)k=2，算法3如圖6。初始化時，分組{5,3,1,7}被劃分為子分組{5,3}和{1,7}，并計算sub1={5,3}=0，sub2={1,7}=0，因此分組{5,3,1,7}相應(yīng)的M值為0，同理{2,4,6}的M值為2。當(dāng)superstep=0時，節(jié)點(diǎn)處于Active狀態(tài)并向鄰居節(jié)點(diǎn)發(fā)送值M，如圖6（b）；當(dāng)supertep=1時，節(jié)點(diǎn)將消息對比自身M值，若大于自身值則更新并保持Active狀態(tài)，反之轉(zhuǎn)為InActive狀態(tài)，如圖6（c），節(jié)點(diǎn)1將M值更新為2，并保持Active狀態(tài)，而節(jié)點(diǎn)2轉(zhuǎn)為InActive狀態(tài)。最終，得出最大缺失值M=2。

Fig.6 Computing max deficiency圖6 計算M值

分組內(nèi)節(jié)點(diǎn)不存在鏈接，不能通過傳遞消息確定目標(biāo)度。因此，為分組創(chuàng)建相應(yīng)的虛擬節(jié)點(diǎn)作為“中樞”，其鄰接節(jié)點(diǎn)是分組內(nèi)的各個節(jié)點(diǎn)，如圖7（a）所示。分組節(jié)點(diǎn)與虛擬節(jié)點(diǎn)構(gòu)成二分圖結(jié)構(gòu)，兩者通過消息傳遞，經(jīng)過3個superstep完成k-degree匿名，基本步驟如下：

（1）superstep=0時，分組節(jié)點(diǎn)為Active狀態(tài)，并發(fā)送（nodeid,degree）給虛擬節(jié)點(diǎn)，其中nodeid是節(jié)點(diǎn)的編號，degree是節(jié)點(diǎn)的度。

（2）superstep=1時，虛擬節(jié)點(diǎn)為Active狀態(tài)，對分組節(jié)點(diǎn)按度降序排列，并令最大度為目標(biāo)度，計算Δdi和num，Δdi是節(jié)點(diǎn)vi要添加的邊的數(shù)目，num是節(jié)點(diǎn)vi前i-1個節(jié)點(diǎn)添加邊的總數(shù)目，發(fā)送（vir.id,Δdi,num）給分組節(jié)點(diǎn)，vir.id是虛擬節(jié)點(diǎn)的編號（vir.id=0,1,2…）。

（3）superstep=2時，分組節(jié)點(diǎn)收到消息后，利用參數(shù)vir.id、Δdi、num以及k、M添加偽邊。方法是：利用式（1）計算添加節(jié)點(diǎn)數(shù)目N；然后建立Δdi×2的矩陣，矩陣的第0列是節(jié)點(diǎn)的nodeid，第1列按行依次寫入pesudo[(vir.id+num+X)modN]，其中X={1,2,…,Δdi}；最后以（nodeid,pesudo[i]）的形式將矩陣存入edgeRDD。

Fig.7k-degree anonymity圖7 k-degree匿名

具體如算法4所示。

算法4Generate pseudo edge

Input：messages,k,M.

Output：the pseudo edge list ofu.

1.PseudoedgeList←? ;

2.longstep=getsuperstep();

3.ifstep==0 then

4.for each vertexudo

5.if isLeft()then

6.sendMessToNeighbors((vertext.nodeid,vertext.degree));//節(jié)點(diǎn)發(fā)送消息給虛擬節(jié)點(diǎn)

7.if step==1 then

8.if notisLeft()then

9.longList=getValue(messages);//取出消息

10.Set max degree as target degree;//設(shè)置目標(biāo)度

11.for every nodeuin List

12.ComputingΔdi、num;//節(jié)點(diǎn)計算Δdi、num

13.sendMessToNeighbors(virid,Δdi,num);

14.ifstep==2 then

15.if isLeft()then

16.Add pseudoedge(nodeid,pesudo[i]);//添加偽邊

17.returnPseudoedgeList；

以算法3產(chǎn)生的分組{1,7}、{5,3}、{2,4,6}為例，算法4如圖7所示。當(dāng)superstep=0時，分組節(jié)點(diǎn)向虛擬節(jié)點(diǎn)發(fā)送nodeid和度，如圖7（a）。當(dāng)superstep=1時，虛擬節(jié)點(diǎn)找出目標(biāo)度，并為節(jié)點(diǎn)計算Δdi和num。以虛擬節(jié)點(diǎn)1為例，并假設(shè)節(jié)點(diǎn)降序排列為{4,2,6}，則目標(biāo)度為3，節(jié)點(diǎn)2前一個節(jié)點(diǎn)是節(jié)點(diǎn)4，則Δdi=(3-2)=1，num=0，故返回消息（1,1,0)，同理節(jié)點(diǎn)6，Δdi=(3-1)=2，num=0+1=1，故返回消息（1,2,1)，如圖7（b）。當(dāng)superstep=2時，分組節(jié)點(diǎn)根據(jù)消息以及N添加偽邊，以分組{4,2,6}為例，節(jié)點(diǎn) 2消息為（1,1,0），則(vir.id+num+X) modN=(1+0+1）mod3=2，添加邊（2,pseudo[2])，節(jié)點(diǎn)6根據(jù)消息（1,2,1），依次添加偽邊（6,pseudo[(1+1+1)mod3])，即偽邊（6,pseudo[0]）以及偽邊（6,pseudo[(1+1+2)mod 3])，即（6,pseudo[1]）。

添加的偽邊信息被保存到edgeRDD中，然后通過Graph.fromEdgeTuples操作從edgeRDD構(gòu)建出包含N個偽節(jié)點(diǎn)的匿名圖，用8、9、10替換pseudo[i]（i=0,1,2），匿名圖如圖2（b）所示，并且N個偽節(jié)點(diǎn)的度為d或(d+1)，具體證明請參考文獻(xiàn)[11]。

4.3 分布式m-標(biāo)簽?zāi)涿?/h3>

m-標(biāo)簽?zāi)涿捎媒y(tǒng)一標(biāo)簽列表匿名[9]，其生成的方法是：假設(shè)C是由算法3產(chǎn)生的含有k個節(jié)點(diǎn)的分組，p={p0,p1,…,pm-1}是整數(shù)序列{0,1,2,…,k-1}的子集，其大小為m(m≤k)，對 ?v∈C，u表示節(jié)點(diǎn)v的標(biāo)簽列表，則其統(tǒng)一標(biāo)簽列表由式（2）產(chǎn)生：

以分組{2,4,6}為例，其相應(yīng)的標(biāo)簽列表分組為{u2,u4,u6}，并假設(shè)m=2,p=(0,1)，則經(jīng)過式（2）統(tǒng)一列表為：u2={u2,u4},u4={u4,u6},u6={u6,u2}。

分析式（2）可知，利用4.2節(jié)的方法很容易實(shí)現(xiàn)分布式m-標(biāo)簽?zāi)涿?，方法步驟如下：

（1）superstep=0，分組節(jié)點(diǎn)發(fā)送消息（nodeid,labellist）給虛擬節(jié)點(diǎn)。

（2）superstep=1，虛擬節(jié)點(diǎn)收到消息，根據(jù)式（2）為分組節(jié)點(diǎn)產(chǎn)生統(tǒng)一標(biāo)簽列表，并將匿名結(jié)果返回給分組節(jié)點(diǎn)。

（3）superstep=2，分組節(jié)點(diǎn)收到消息后，將原有標(biāo)簽列表修改為范化標(biāo)簽列表。

算法5Generate lable list

Input：messages.

1.longstep=getSuperstep()；

2.ifstep==0 then

3.for each vertexudo

4.if isLeft()then

5.sendMessToNeighbors((u.nodeid，u.labellist));//節(jié)點(diǎn)向虛擬節(jié)點(diǎn)發(fā)送(nodeid,labellist)

6.ifstep==1 then

7.if notisLeft()then

8.longlist=getValue(messages);//虛擬節(jié)點(diǎn)取出消息

9.for vertextuin list do

10.new=(u.nodeid，u.genlabellist);//標(biāo)簽?zāi)涿?/p>

11.sendMessToNeighbors(new);//虛擬節(jié)點(diǎn)向用戶節(jié)點(diǎn)返回新的標(biāo)簽

12.ifstep==2 then

13.if isLeft()then

14.longAnolabel=getValue(message);

15.setValue(Anolabel);//節(jié)點(diǎn)u修改自身標(biāo)簽

以圖1為例，并假設(shè)m=2，p={0,1}，為了便于表述，節(jié)點(diǎn)i的標(biāo)簽用ui來表示，則分組{1,7}、{5,3}、{2,4,6}對應(yīng)的標(biāo)簽分組為 {u1,u7}、{u5,u3}、{u2,u4,u6}。當(dāng)superstep=0時，分組節(jié)點(diǎn)向虛擬節(jié)點(diǎn)發(fā)送消息（nodeid,labelist），如圖8（a）；superstep=1時，虛擬節(jié)點(diǎn)利用式（2）為分組節(jié)點(diǎn)產(chǎn)生統(tǒng)一標(biāo)簽列表，并返回給分組節(jié)點(diǎn)，如圖8（b）；當(dāng)superstep=2時，分組節(jié)點(diǎn)收到消息后，將自身的標(biāo)簽替換成統(tǒng)一標(biāo)簽列表，如圖8（c）所示。

Fig.8 Label anonymity圖8 標(biāo)簽?zāi)涿?/p>

5 擴(kuò)展的PLRD-(k,m)方法

社會網(wǎng)絡(luò)中，用戶對隱私保護(hù)強(qiáng)度具有不同的需求，某些用戶甚至不希望隱藏自己的身份，如公眾名人[23]?；谕粯?biāo)準(zhǔn)對用戶進(jìn)行匿名保護(hù)，不僅會增加匿名成本，還將降低匿名數(shù)據(jù)的可用性。為此，對PLRD-(k,m)方法進(jìn)行擴(kuò)展，提出個性化匿名方法PLRDPA（protecting link relationships distributed personalized anonymity)，為用戶提供lv0～lv2不同的隱私保護(hù)級別。

lv0級：隱私保護(hù)級別為0，即對用戶的信息不做任何匿名處理。

lv1級：隱私保護(hù)級別為1，能夠抵抗攻擊者通過度信息識別用戶身份和鏈接關(guān)系。

lv2級：隱私保護(hù)級別為2，攻擊者即使擁有節(jié)點(diǎn)的度和標(biāo)簽，也無法識別出用戶身份和鏈接關(guān)系。

若通過FUG算法進(jìn)行分組，不同隱私保護(hù)級別的節(jié)點(diǎn)可能被分在同一組。為此，提出個性化安全分組條件PSGC（personalized safety grouping condition）。設(shè)C是包含k個節(jié)點(diǎn)的分組，若分組C滿足PSGC條件，則：

（1）?u∈C，?u∈C?u.lv=v.lv

（2）?u∈C，?u∈C?dist(u,v)≥2

條件1表明同一分組的節(jié)點(diǎn)具有相同的隱私保護(hù)等級；條件2表明同一分組的節(jié)點(diǎn)彼此間的最短路徑長度dist(u,v)≥2。因此對算法2做出適當(dāng)修改以滿足PSGC條件，“調(diào)解人”判斷的條件修改為：

（1）u.groupid=v.min

（2）v.groupid=u.min

（3）u.lv=v.lv

算法3計算M值時，隱私級別為lv0的分組將M值置為0。經(jīng)過算法2和算法3，對隱私保護(hù)級別為lv1的分組利用算法4進(jìn)行k-degree匿名；隱私級別為lv2的分組，只需要在lv1的基礎(chǔ)上執(zhí)行算法5即可。

6 PLRD-(k,m)方法的安全性分析

PLRD-(k,m)方法的目標(biāo)是抵抗節(jié)點(diǎn)重識別的同時，抵抗標(biāo)簽鏈接泄露，對算法安全性的分析從這兩方面著手。

定理4已知圖G*是社會網(wǎng)絡(luò)圖G=(V,E,L,δ)，由PLRD-(k,m)生成的匿名圖，P是攻擊者根據(jù)節(jié)點(diǎn)的度或標(biāo)簽從G*中識別出目標(biāo)節(jié)點(diǎn)的概率，則概率P滿足：1/k≤P≤1/m。

證明（1）若攻擊者僅掌握了節(jié)點(diǎn)的度，由于G*是k-degree匿名圖，對任意節(jié)點(diǎn)v存在(k-1)個其他節(jié)點(diǎn)與v的度相同，則節(jié)點(diǎn)v被識別出的概率為1/k。（2）若攻擊者僅掌握了節(jié)點(diǎn)v的標(biāo)簽，由算法5，在匿名圖G*中存在(m-1)個其他節(jié)點(diǎn)包含v的標(biāo)簽，故被識別的概率為1/m。（3）若攻擊者同時掌握了節(jié)點(diǎn)v的度信息和標(biāo)簽信息，由概率組合知識可知，節(jié)點(diǎn)v被識別的概率為1/m。

定理5已知圖G*是社會網(wǎng)絡(luò)圖G=(V,E,L,δ)，由PLRD-(k,m)生成的匿名圖，則圖G*不存在標(biāo)簽鏈接泄露。

PLRD-(k,m)方法包括FUG、k-degree匿名以及m-標(biāo)簽?zāi)涿?，分析可知，k-degree匿名和m-標(biāo)簽?zāi)涿粫?dǎo)致標(biāo)簽鏈接泄露。因此，只需證明FUG算法不會將鏈接引入分組。

證明每次迭代，F(xiàn)UG算法都要構(gòu)建新圖，用Gi表示第i次構(gòu)建的圖，Si表示圖Gi中的節(jié)點(diǎn)，由算法1和算法2可知，節(jié)點(diǎn)Si是由圖Gi-1中互為2-hop鄰居的節(jié)點(diǎn)u、v形成的超級節(jié)點(diǎn)，故節(jié)點(diǎn)Si在Gi中的鏈接關(guān)系繼承自節(jié)點(diǎn)u、v，即u、v在圖Gi-1中的1-hop鄰居節(jié)點(diǎn)，在Gi中轉(zhuǎn)變?yōu)楣?jié)點(diǎn)Si的1-hop鄰居節(jié)點(diǎn)。因此，F(xiàn)UG算法不會將鏈接引入分組。

7 實(shí)驗(yàn)分析

實(shí)驗(yàn)對PLRD-(k,m)隱私保護(hù)方法進(jìn)行性能分析和評價，采用真實(shí)社會網(wǎng)絡(luò)com-Youtube圖數(shù)據(jù)集。com-Youtube圖數(shù)據(jù)集包含1 134 890個節(jié)點(diǎn)和2 897 624條邊。由于PLRD-(k,m)方法涉及到節(jié)點(diǎn)標(biāo)簽而com-Youtube數(shù)據(jù)集不包含標(biāo)簽信息，因此實(shí)驗(yàn)中人工生成節(jié)點(diǎn)標(biāo)簽信息。節(jié)點(diǎn)的標(biāo)簽包括3個屬性：國籍（80個國家）、性別（男或女）、年齡（15～75）。所有的值滿足同一分布。為了進(jìn)行對比，實(shí)驗(yàn)同時在單工作站環(huán)境實(shí)現(xiàn)了PLRD-(k,m)和PLRDPA方法，兩種環(huán)境如下：

單工作站環(huán)境：Intel Core i7-2720QM，CPU 2.2 GHz，16 GB RAM；操作系統(tǒng)，Win 7 旗艦版；編程語言，Python。

集群環(huán)境：12臺計算節(jié)點(diǎn)搭建的集群，Hadoop 2.7.2，Spark1.6.3；CPU 1.8 GHz，16 GB RAM，編程語言，Scala。

其中，PLRD-(k,m)和PLRDPA算法所對應(yīng)的單工作站版本分別記作PLR-(k,m)和PLRPA。在實(shí)現(xiàn)PLRPA和PLRDPA時，實(shí)驗(yàn)從數(shù)據(jù)集中虛擬出10%的節(jié)點(diǎn)為lv0級，15%的節(jié)點(diǎn)為lv2級，剩余節(jié)點(diǎn)則將隱私級別設(shè)置為lv1級。

7.1 算法性能分析

7.1.1 運(yùn)行時間

圖9展示了算法隨閾值m變化的運(yùn)行時間對比結(jié)果。從圖9可以看出，隨著m值的增大運(yùn)行時間隨之增大，原因是m值越大，序列p={p0,p1,…,pm-1} 的范圍越廣，m-標(biāo)簽?zāi)涿牡臅r間越多。同時，從實(shí)驗(yàn)結(jié)果也可以看出，PLRD-(k,m)和PLRDPA算法的匿名開銷要遠(yuǎn)小于PLR-(k,m)和PLRPA，所提出的算法在處理大規(guī)模數(shù)據(jù)上更具有優(yōu)勢。

Fig.9 Comparison of run time圖9 運(yùn)行時間對比

7.1.2 加速比和規(guī)?？蓴U(kuò)展性

相對加速比是指同一并行算法在單個計算節(jié)點(diǎn)上運(yùn)行時間與在多個相同計算節(jié)點(diǎn)構(gòu)成的處理系統(tǒng)上運(yùn)行時間之比，其計算公式如下：

計算節(jié)點(diǎn)的數(shù)目從3逐步增加到12，并將數(shù)目為3時的運(yùn)行時間作為T(1)，結(jié)果如圖10所示。可以看出，兩種算法均具有良好的加速比，但不是理想的線性加速比，因?yàn)殡S著計算節(jié)點(diǎn)數(shù)目的遞增，彼此間的通信量會隨之增多，產(chǎn)生更多的額外開銷。

實(shí)驗(yàn)通過固定計算節(jié)點(diǎn)數(shù)目，擴(kuò)大數(shù)據(jù)規(guī)模并求處理時間比的方法評測算法的擴(kuò)展性，可擴(kuò)展性計算公式如下：

Fig.10 Speedup ratio圖10 加速比

式中，DB是基礎(chǔ)數(shù)據(jù)集，m×DB是m比例于DB的數(shù)據(jù)集，T(*)是處理數(shù)據(jù)集消耗的時間。實(shí)驗(yàn)將com-Youtube圖數(shù)據(jù)集等分成5份，然后按1∶2∶3∶4∶5重新聚合成split1～split5，并將數(shù)據(jù)集split1作為基礎(chǔ)數(shù)據(jù)集DB，然后在集群上處理5個數(shù)據(jù)集，實(shí)驗(yàn)對比結(jié)果如圖11所示。根據(jù)式（4），理想狀態(tài)下，Scalability的值應(yīng)不大于比例m，但圖12表明，處理split5時，Scalability的值卻大于5，原因是受限于CPU的處理能力以及I/O消耗。

Fig.11 Scalability圖11 可擴(kuò)展性

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

PLRD-(k,m)方法修改了圖的結(jié)構(gòu)和節(jié)點(diǎn)屬性值，因此，實(shí)驗(yàn)通過計算圖結(jié)構(gòu)信息的損失和查詢的準(zhǔn)確性來評價算法在數(shù)據(jù)可用性上的表現(xiàn)。

7.2.1 圖結(jié)構(gòu)信息損失

實(shí)驗(yàn)通過平均最短路徑長度和聚集系數(shù)的變化率來評測匿名圖G*的信息損失。節(jié)點(diǎn)u的聚集系數(shù)是指其鄰居節(jié)點(diǎn)中連接關(guān)系所占的比例。圖結(jié)構(gòu)信息變化率定義為|G-G*|/|G|，其中G和G*分別表示在原始圖和匿名圖中的測量值，Error值越小，數(shù)據(jù)的可用性越好。圖12和圖13分別顯示了匿名圖在平均最短路徑長度、聚集系數(shù)的變化情況。從實(shí)驗(yàn)結(jié)果可以看出，隨著分組中節(jié)點(diǎn)數(shù)目的增加，匿名后圖結(jié)構(gòu)信息的損失率也相對增加。

Fig.12 Change ratio of average shortest path圖12 平均最短路徑變化率

Fig.13 Change ratio of clustering coefficient圖13 聚集系數(shù)變化率

7.2.2 查詢準(zhǔn)確性

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

實(shí)驗(yàn)通過單跳查詢評測PLRD-(k,m)方法在查詢準(zhǔn)確性上的表現(xiàn)，并對比PLRDPA方法。實(shí)驗(yàn)提出的查詢操作為：“在不同年齡段，A國用戶和B國用戶間存在多少朋友關(guān)系”。圖14展示了不同閾值對算法PLRD-(k,m)和PLRDPA查詢結(jié)果的影響。實(shí)驗(yàn)結(jié)果表明，在閾值參數(shù)相同的情況下，相比于PLRD-(k,m)方法，PLRDPA方法的查詢誤差更低，說明根據(jù)用戶不同需求，提供個性化匿名保護(hù)能夠更好地保護(hù)數(shù)據(jù)的可用性。

Fig.14 Relative error of query圖14 查詢誤差率

圖15和圖16分別展示了參數(shù)k對單跳查詢、雙跳查詢的準(zhǔn)確性的影響。實(shí)驗(yàn)結(jié)果表明，隨著分組中節(jié)點(diǎn)數(shù)目的增加，查詢誤差率隨之增大，因?yàn)榉纸M中節(jié)點(diǎn)數(shù)目越多，節(jié)點(diǎn)的候選標(biāo)簽數(shù)越多，因此導(dǎo)致查詢結(jié)果的相對誤差變大。同時表明，個性化匿名的查詢誤差率明顯更低，能夠更好地保護(hù)查詢準(zhǔn)確性。

Fig.15 Relative error of single-hop query圖15 單跳查詢誤差率

8 結(jié)束語

Fig.16 Relative error of dual-hop query圖16 雙跳查詢誤差率

目前的隱私保護(hù)技術(shù)僅針對某一種背景知識，并且隨著社會網(wǎng)絡(luò)規(guī)模的逐年遞增已不能滿足實(shí)際需求。為此，提出一種分布式匿名方法PLRD-(k,m)，該方法基于GraphX“節(jié)點(diǎn)為中心”的特點(diǎn)，將互為N-hop鄰居的節(jié)點(diǎn)分為一組，并對分組進(jìn)行k-degree匿名和m-標(biāo)簽?zāi)涿诘挚怪刈R別攻擊的同時保護(hù)了鏈接關(guān)系。此外，為了滿足個性化需求，擴(kuò)展了PLRD-(k,m)方法，提出一種個性化匿名方案PLRDPA，允許用戶設(shè)置不同的隱私級別并提供不同的保護(hù)?；谡鎸?shí)社會網(wǎng)絡(luò)的實(shí)驗(yàn)數(shù)據(jù)表明，所提出的算法能夠在提供隱私保護(hù)的同時，提高處理大規(guī)模數(shù)據(jù)的效率。

社會網(wǎng)絡(luò)中，受限于身份的不同，用戶在輿論傳播過程中具有不同的影響力。匿名社會網(wǎng)絡(luò)時，往往需要對圖結(jié)構(gòu)進(jìn)行一定程度的修改，很可能導(dǎo)致匿名前后用戶的影響力發(fā)生重大變化。因此接下來將考慮在匿名社會網(wǎng)絡(luò)圖的過程中保護(hù)節(jié)點(diǎn)的影響力。