張曉琳，于芳名，何曉玉，袁昊晨

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

1 引言

針對(duì)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)（Dynamic Social Network，DSN）隱私保護(hù)問題，提出了多種隱私保護(hù)方法。陳偉鶴等[1]提出基于動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)的敏感邊的隱私保護(hù)。谷勇浩等[2]提出基于聚類的動(dòng)態(tài)社交網(wǎng)絡(luò)隱私保護(hù)方法。Zhang等[3]提出基于k-鄰居同構(gòu)的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)隱私保護(hù)方法。對(duì)于動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)的研究有助于揭示網(wǎng)絡(luò)性質(zhì)的起源，并能夠?qū)ζ浒l(fā)展進(jìn)行預(yù)測(cè)。預(yù)測(cè)鏈接在DSN中的基本思想是：通過當(dāng)前社會(huì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)預(yù)測(cè)未來社會(huì)網(wǎng)絡(luò)中真實(shí)存在的邊，如果將預(yù)測(cè)邊作為偽邊匿名當(dāng)前圖數(shù)據(jù)，則在匿名下一時(shí)刻的社會(huì)網(wǎng)絡(luò)圖數(shù)據(jù)時(shí)將會(huì)減小匿名代價(jià)。Bhagat等[4]比較多種預(yù)測(cè)鏈接方法對(duì)于隱私保護(hù)強(qiáng)度的影響，有效保證結(jié)點(diǎn)和邊的隱私信息。Liu等[5]提出防止鏈接推理攻擊的隱私保護(hù)方法，保護(hù)社交網(wǎng)絡(luò)中邊的隱私信息。王路寧[6]提出的隱私保護(hù)方法通過加入預(yù)測(cè)鏈接方法，較大程度地提升圖數(shù)據(jù)的可用性。但以上算法運(yùn)行在單機(jī)環(huán)境下，效率不高，實(shí)現(xiàn)社會(huì)網(wǎng)絡(luò)隱私的并行化已成為未來趨勢(shì)[7]。Zakerzadeh等[8]基于Hadoop框架加速處理圖數(shù)據(jù)匿名的過程。Mehmood等[9]全面概述大數(shù)據(jù)中的隱私保護(hù)機(jī)制，利用分布式系統(tǒng)提高數(shù)據(jù)處理效率。但是由于傳統(tǒng)MapReduce模型在多次迭代處理時(shí)的數(shù)據(jù)反復(fù)遷移和作業(yè)連續(xù)調(diào)度等問題，數(shù)據(jù)處理效率較低。BSP（Bulk Synchronous Parallel）模型是云計(jì)算環(huán)境下處理大規(guī)模圖數(shù)據(jù)的典型計(jì)算模型，適合大規(guī)模圖計(jì)算過程的并行處理[10]。Google的Pregel系統(tǒng)[11]是基于BSP模型的最成熟的圖處理系統(tǒng)，Pregel系統(tǒng)帶動(dòng)了一系列Pregel-like系統(tǒng)[12]發(fā)展，如Apache的Hama、Yahoo的Giraph和Spark的GraphX[13-14]等。由于單機(jī)工作站環(huán)境下，動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)隱私保護(hù)方法處理大規(guī)模圖數(shù)據(jù)存在很大的局限性，同時(shí)為了提高數(shù)據(jù)可用性，本文提出了D-DSNBLP（Distributed-Dynamic Social Network Based on Link Prediction）。該方法利用DP動(dòng)態(tài)規(guī)劃算法[15]將結(jié)點(diǎn)分成獨(dú)立的組，每個(gè)組k個(gè)結(jié)點(diǎn)；其次利用預(yù)測(cè)鏈接并行構(gòu)建候選結(jié)點(diǎn)集合，使得每個(gè)組滿足k-度匿名；最后構(gòu)建互斥邊集合添加邊，完成圖的匿名操作。為便于研究，只考慮不帶標(biāo)簽的無向圖。

2 相關(guān)知識(shí)

給定動(dòng)態(tài)社會(huì)網(wǎng)絡(luò) Gt和 Gt+1，如圖1（a）和圖1（c）。攻擊者知道結(jié)點(diǎn)v15的度由d15=1變?yōu)閐15=2，則通過結(jié)點(diǎn)度的變化，能夠唯一識(shí)別結(jié)點(diǎn)v15（度攻擊）。傳統(tǒng)的動(dòng)態(tài)度匿名方法通過考慮當(dāng)前圖的拓?fù)浣Y(jié)構(gòu)，然后修改圖中結(jié)點(diǎn)之間的邊，使得每個(gè)圖都達(dá)到k-度匿名，但這種方式選擇的偽邊忽略了動(dòng)態(tài)圖之間的聯(lián)系。為了解決此類問題，提出預(yù)測(cè)鏈接的方式選擇偽邊，即通過當(dāng)前圖的拓?fù)浣Y(jié)構(gòu)預(yù)測(cè)下一個(gè)圖的連接關(guān)系，將此連接關(guān)系作為修改圖中結(jié)點(diǎn)之間的偽邊。

定義1（動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)圖）動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)圖G=(Vt,Et)。Vt={v1,v2,…,vn}代表t時(shí)刻社會(huì)網(wǎng)絡(luò)圖的結(jié)點(diǎn)，Et?Vt×Vt代表t時(shí)刻社會(huì)網(wǎng)絡(luò)圖的邊。Γ={G1,G2,…,Gt}表示在T=1,2,…,t時(shí)刻的社會(huì)網(wǎng)絡(luò)圖集合，表示在t時(shí)刻的社會(huì)網(wǎng)絡(luò)匿名圖集合。

定義2（k-度匿名序列）動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)圖G=(Vt,Et)中的結(jié)點(diǎn)v∈V按照度降序所構(gòu)成的序列稱為非遞增度序列DS′。若DS′中任意一個(gè)結(jié)點(diǎn)的度都有k-1個(gè)結(jié)點(diǎn)和它有相同的度，則稱這個(gè)度序列為匿名度序列，標(biāo)記為DS*。滿足匿名度序列的圖稱為k-度匿名社會(huì)網(wǎng)絡(luò)圖，表示為G*，令dv表示結(jié)點(diǎn)v的度。

Nr(v)表示結(jié)點(diǎn)v在第r步到達(dá)的所有結(jié)點(diǎn)集合，簡(jiǎn)稱r鄰居，文中也表示為r-鄰居。例如圖1（a）中，即v15的兩鄰居是v11、v13。

定義5（預(yù)測(cè)鏈接）給定圖Gi和Gj,存在e1=e(v1,v2)?Gi,e1=e(v1,v2)∈Gj，且 i＜j。在 i時(shí)刻，利用圖Gi的某些特性預(yù)測(cè)出e1的過程，稱為預(yù)測(cè)鏈接。

在社會(huì)網(wǎng)絡(luò)圖中，共同鄰居信息是預(yù)測(cè)鏈接的衡量指標(biāo)之一，但是單獨(dú)以共同鄰居作為預(yù)測(cè)鏈接的指標(biāo)，忽略了共同鄰居之間的關(guān)系，因此使用路徑信息進(jìn)一步獲得結(jié)點(diǎn)之間的鏈接強(qiáng)度。即將共同鄰居數(shù)量和路徑信息同時(shí)作為達(dá)到匿名圖的度量標(biāo)準(zhǔn)UMC（Utility Metric Criteration）：

UMC值越大說明兩個(gè)結(jié)點(diǎn)鏈接關(guān)系越強(qiáng)，在下一時(shí)刻存在鏈接的可能性也越大。

如果發(fā)布的圖G*的度序列滿足k-度匿名序列，則可以防止度攻擊。

定義6((k,dtarget)-度匿名）由DS′劃分成若干個(gè)獨(dú)立的組C1,C2,…,Ci,…,Cm，每個(gè)組至少有k個(gè)結(jié)點(diǎn)。v,u∈Ci,?dv≥du,1＜i＜m ，則 dmax(Ci)=dv。在 t時(shí)刻，為了使組中的結(jié)點(diǎn)有同樣的度，結(jié)點(diǎn)需要添加Attr個(gè)偽邊或者結(jié)點(diǎn)屬性值，即 Attr(vi)=dmax(Cj)-dvi。vi∈Cj,i=1,2,…,|Cj|,j=1,2,…,m 。

定義7（組間匿名）給定兩個(gè)組Cm、Cn,Cost(Cm,Cn)=dmax=dv。結(jié)點(diǎn)v與組C的匿名代價(jià)可以看作是只有一個(gè)結(jié)點(diǎn)的組和C的代價(jià)。

3 D-DSNBLP隱私保護(hù)方法

D-DSNBLP隱私保護(hù)方法的主要思想：首先將社會(huì)網(wǎng)絡(luò)中的結(jié)點(diǎn)通過動(dòng)態(tài)劃分組得到每個(gè)結(jié)點(diǎn)的Attr(vi),Attr(vi)≠0的結(jié)點(diǎn)及對(duì)應(yīng)的Attr(vi)存放在序列S中；其次S中的結(jié)點(diǎn)并行選擇候選結(jié)點(diǎn)集合Cand Set(vi)；最后構(gòu)建互斥邊集合，根據(jù)互斥邊集合更新序列S。

在對(duì)社會(huì)網(wǎng)絡(luò)圖采用D-DSNBLP方法之前，需要格式化數(shù)據(jù)，使數(shù)據(jù)的格式滿足實(shí)驗(yàn)需求。

算法1 D-DSNBLP隱私保護(hù)方法

輸入：社會(huì)網(wǎng)絡(luò)圖Γ={G1,G2,…,Gt}，匿名參數(shù)k。

1.for every graph

2. Stemp←Attr(vi)≠0;DS′=degree(vi)//初始化集合

3. if（the first graph）

4.splitGroup(DS′,k)

5. anonmization(group,S)

6.else

7. Foreach g in group

8. If g.size＜k then g union other group by cost and get Attr(vi)

9. If exist new node union other group by cost and get Attr(vi)

10. anonmization(group,S)

11.def splitGroup(array(ID,degree),k){

12. costall=根據(jù)k-target度匿名計(jì)算所有結(jié)點(diǎn)在一個(gè)組時(shí)的匿名代價(jià)，同時(shí)給定組編號(hào)和結(jié)點(diǎn)的Attr

13. if結(jié)點(diǎn)個(gè)數(shù)小于2k

14.返回costall

15.else

16. for i←k to結(jié)點(diǎn)個(gè)數(shù)-k

17. costi=計(jì)算以i為分界點(diǎn)的代價(jià)（此處迭代調(diào)用splitPoint）

18. if costi＞costall：return costi else costall

19. }

20.def anonmization(group,S)

21.allEdge=null

23.r=2//表示 N2(v)

24.everyNodeCandSet=call 算法2（r）

25.everyNodeCandEdge+=call 算法3（everyNodeCand-Set）.EdgeSet

26.S=update by everyNodeCandEdge

27.allEdge+=everyNodeCandEdge

28.r=r+1

29.G*=G.Add(allEdge)

圖1 社會(huì)網(wǎng)絡(luò)圖

動(dòng)態(tài)圖的第一個(gè)圖需要分組，后續(xù)的圖需要按照第一個(gè)圖的分組進(jìn)行匿名，即僅需要一次分組。算法第3～5行根據(jù)DP動(dòng)態(tài)算法劃分組，求得每個(gè)結(jié)點(diǎn)達(dá)到匿名需要添加的邊數(shù)并追加到集合S，然后匿名；第6～10行表示新加入的結(jié)點(diǎn)根據(jù)組間匿名代價(jià)加入Cost最小的組求得Attr(v)；若某組結(jié)點(diǎn)不滿k個(gè)，則根據(jù)組間匿名代價(jià)合并，求得 Attr(v)；第11～19行說明了分組算法[15]。第20～29行表示因?yàn)榛ゲ粸?鄰居的結(jié)點(diǎn)才能添加邊，所以r≥2，由“小世界理論”和“六度分割原理”定義r小于等于6。r=2，當(dāng)N2(v)中結(jié)點(diǎn)不能夠滿足Attr(v)個(gè)結(jié)點(diǎn)時(shí)，將N2(v)的范圍變?yōu)镹3(v)，以此類推，直到r=6時(shí)停止。如果r=6時(shí)仍然無法找到候選結(jié)點(diǎn)，則在圖G中隨機(jī)尋找結(jié)點(diǎn)作為候選結(jié)點(diǎn)，使得候選結(jié)點(diǎn)總數(shù)能夠達(dá)到Attr(v)個(gè)。第24～25行表示尋找候選結(jié)點(diǎn)結(jié)合，計(jì)算并篩選候選邊CandEdge；調(diào)用算法3得到互斥邊集合并存儲(chǔ)，第26行根據(jù)互斥邊集合更新S。第29行向圖G中添加所有互斥邊，匿名結(jié)束。

例1圖1（a）為t時(shí)刻原始圖，以k=5為例，度序列如表1，通過DP動(dòng)態(tài)算法分組為C1={v7,v11,v13,v4,v2},C2={v3,v14,v6,v8,v10},C3={v9,v1,v15,v16,v5}。假設(shè)加入偽邊(v2,v4),(v10,v8),(v13,v15)得到匿名圖1（b），那么t+1時(shí)刻，如圖1（c），由于三條偽邊真實(shí)存在，則由于C1、C2分組內(nèi)結(jié)點(diǎn)沒有發(fā)生變化，故不需要匿名，匿名代價(jià)為0。C3組內(nèi)dv1=dv9=3，則利用(k,dtarget)匿名得到Attr(v15)=Attr(v12)=Attr(v16)=Attr(v5)=1。結(jié)點(diǎn)得到Attr(vi)后，選擇候選結(jié)點(diǎn)集合Cand Set(v),S={(v15,1),(v12,1),(v16,1),(v5,1)}。

表1 度序列及結(jié)點(diǎn)屬性

3.1 并行構(gòu)建候選結(jié)點(diǎn)集合

Pregel是一個(gè)消息迭代更新模型，能夠高效地分布式處理大規(guī)模社會(huì)網(wǎng)絡(luò)圖。一個(gè)Pregel任務(wù)可分為多個(gè)超步（supersteps）。每個(gè)superstep分為vprog、sendMsg、mergeMsg三個(gè)階段。vprog階段結(jié)點(diǎn)在本地處理接收到的消息；sendMsg階段結(jié)點(diǎn)將更新后的消息發(fā)送給1-鄰居；mergeMsg階段結(jié)點(diǎn)合并接收到的消息。當(dāng)全部結(jié)點(diǎn)沒有消息更新時(shí)或者達(dá)到最大的迭代次數(shù)時(shí)，Pregel操作停止迭代并返回結(jié)果。每個(gè)超級(jí)步并行發(fā)送消息。若結(jié)點(diǎn)更新消息則將結(jié)點(diǎn)狀態(tài)置為Active，否則置為InActive狀態(tài)。

結(jié)點(diǎn)v的候選結(jié)點(diǎn)集合Cand Set(v)是將UMC(v,u)值最大的Attr(v)個(gè)結(jié)點(diǎn)u∈Nr(v)加入v的候選結(jié)點(diǎn)集合Cand Set(v)。因?yàn)閡和v之間所有的路徑信息Path包含了源結(jié)點(diǎn)u和目標(biāo)結(jié)點(diǎn)v的1-鄰居，所以UMC的計(jì)算只需尋找該結(jié)點(diǎn)Pathr+1再比較得出候選結(jié)點(diǎn)集合Cand Set(v)。以下為并行尋找Pathr+1的過程（以r=2為例）：

（1）superstep=0時(shí)，每個(gè)結(jié)點(diǎn)狀態(tài)設(shè)置為Active狀態(tài)，處于Active狀態(tài)的結(jié)點(diǎn)將自己的信息Info發(fā)送給鄰居結(jié)點(diǎn)。

（2）當(dāng)superstep≠0時(shí)，接收到消息的結(jié)點(diǎn)判斷消息隊(duì)列中的每條消息的生命值是否為0，是則停止發(fā)送此條消息給鄰居，結(jié)點(diǎn)置為InActive狀態(tài)，否則將當(dāng)前結(jié)點(diǎn)的Vertex ID加入路徑，生命值減1，繼續(xù)傳遞消息，重復(fù)執(zhí)行（2），直到生命值為0或者沒有結(jié)點(diǎn)更新消息時(shí)停止迭代。Info信息為(VertexID,lifeValue,Path(VertexID))。Path是用來存儲(chǔ)長(zhǎng)度在r+1以內(nèi)的每一條路徑的數(shù)據(jù)結(jié)構(gòu)，Path初始值為結(jié)點(diǎn)本身的VertexID值，初始lifeValue=3（因?yàn)椴檎?步內(nèi)的所有路徑信息）。

算法2構(gòu)建候選結(jié)點(diǎn)集合

輸入：帶結(jié)點(diǎn)屬性Attr(v)的原始圖G。

輸出：每個(gè)結(jié)點(diǎn)v及其對(duì)應(yīng)的Cand Set(v)。

1.Gn2Pc3=Pregel（）

2.{

Initial graph G，Max iterator MaxValue

Call updateMsg（）

Call sendMsgToNeibor（）

Call mergeMsg（）

}

3.updateMsg{

4. if（superstep=0）then

5. send its Info to Neiborhood

6.if（superstep!=0）then

7. if（Info.lifeValue!=0）then

8. add current VertexId to Path

9. lifeValue-1

10. send its Info to Neiborhood

11.}

12.sendMsgToNeibor{

13. send Info to Neiborhood which not contains source VertexId

14.}

15.mergeMsg{

16.mergeallInfo

17.}

18.computeUMCforeveryNodebyGn2Pc3

算法2第1～2行是Pregel算法的調(diào)用。調(diào)用過程初始化運(yùn)行時(shí)的圖、最大迭代次數(shù)和消息傳遞方向，調(diào)用消息更新模型、消息發(fā)送模型和消息合并模型。第3～17行是第1行調(diào)用的三個(gè)方法。第3～11行的方法updateMsg是結(jié)點(diǎn)處理接收到的消息的方法，若superstep=0，表示結(jié)點(diǎn)目前只擁有初始值，直接發(fā)送信息即可；如果superstep不等于0，表示結(jié)點(diǎn)收到了消息，需要將自己的VertexID加入到每個(gè)路徑中，lifeValue減1，繼續(xù)發(fā)送信息，直到所有結(jié)點(diǎn)信息的生命值為0。第12～14行sendMsgToNeibor的方法是將多次包含源結(jié)點(diǎn)信息去除，再發(fā)送給鄰居，避免環(huán)路發(fā)送信息。第15～17行是每個(gè)結(jié)點(diǎn)合并收到的所有信息，處理后發(fā)送信息給updateMsg方法更新結(jié)點(diǎn)信息。第18行，圖Gn2Pc3中每個(gè)結(jié)點(diǎn)均攜帶路徑信息，根據(jù)路徑信息和鄰居信息計(jì)算兩個(gè)結(jié)點(diǎn)UMC值，進(jìn)而選擇候選結(jié)點(diǎn)集合。

以圖1（a）中結(jié)點(diǎn)v16獲得的路徑Path(v1,v2,v3,v16)為例進(jìn)行分析。

（1）superstep=0時(shí)，如圖2（a），結(jié)點(diǎn) v1初始化消息Info((v1,3,Path(v1))并發(fā)送給鄰居。

（2）superstep=1時(shí)，如圖2（b），結(jié)點(diǎn) v2接收消息后合并，加入自己的VertexID且生命值減1，處理后得消息Info(v1,2,Path(v1,v2))，最后自身置為Active狀態(tài)并發(fā)送消息。

（3）superstep=2時(shí)，如圖2（c），結(jié)點(diǎn) v3接收消息后合并，加入自己的VertexID且生命值減1，處理后得信息Info(v1,1,Path(v1,v2,v3))，自身置為Active狀態(tài)并發(fā)送消息。

（4）superstep=3時(shí)，結(jié)點(diǎn)v16接收到消息、合并，生命值減1為0，因此自身置為InActive狀態(tài)，Info(v1,0,Path(v1,v2,v3,v16))，停止迭代。

圖2 結(jié)點(diǎn)接收、發(fā)送信息

3.2 互斥邊集合

候選邊集合Cand Edge按照UMC降序排列，依次加入集合EdgeSet,EdgeSet是所有可以同時(shí)添加的邊集合。在EdgeSet集合中的邊需要滿足以下條件：結(jié)點(diǎn)v的ID在集合EdgeSet中出現(xiàn)的次數(shù)小于等于Attr(v)。構(gòu)造互斥邊集合后，并行添加邊時(shí)就不會(huì)出現(xiàn)邊添加異常。

算法3構(gòu)建互斥邊集合

輸入：所有結(jié)點(diǎn)的候選邊Cand Edge（按照UMC值降序排列）。

輸出：可添加的邊集合EdgeSet。

1.EdgeSet←Φ

2.Foreach edge e in CandEdge

3.If count（e.dstid）＜Attr（e.dstid）and count（e.srcid）＜Attr（e.srcid） then EdgeSet← e

例1中，候選邊Cand Edge={(v16,v5),(v12,v15)},此時(shí)兩條邊均滿足條件，則EdgeSet{(v16,v5),(v12,v15)}。此時(shí)S中的Attr均為0，直接刪除即可，S為空，則t+1時(shí)刻匿名圖如圖3所示。

圖3 t+1時(shí)刻社會(huì)網(wǎng)絡(luò)匿名圖

4 實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)使用Pregel-like系統(tǒng)模型Spark-1.3.1，使用12臺(tái)Dell服務(wù)器構(gòu)建成Spark集群，硬件配置為CPU 1.8 GHz，RAM 16 GB。使用Hadoop 2.5.2作為存儲(chǔ)系統(tǒng)，JDK1.7.0_65。實(shí)驗(yàn)使用的數(shù)據(jù)是真實(shí)的DBLP論文數(shù)據(jù)（http：//dblp.dagstuhl.de/xml），2015年3月至7月的數(shù)據(jù)如表2所示。使用此數(shù)據(jù)集的原因一方面是因?yàn)閿?shù)據(jù)量足夠大，另一方面是因?yàn)槠鋵儆谡鎸?shí)的DSN，并且可隨意拆分成多個(gè)規(guī)模不同的數(shù)據(jù)集。為滿足實(shí)驗(yàn)需求，對(duì)原始數(shù)據(jù)集做了以下操作：將數(shù)據(jù)集A隨機(jī)等分為4份，然后按比例1∶2∶3∶4重新將數(shù)據(jù)整合，整合后的4個(gè)數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)。處理后的數(shù)據(jù)集屬性如表3所示。本文選擇簡(jiǎn)單且易于實(shí)現(xiàn)的AMBOGP[1]方法作為基準(zhǔn)方法，用于測(cè)試匿名算法在動(dòng)態(tài)匿名時(shí)圖的整體改變量以及圖結(jié)構(gòu)的保持程度。

表2 數(shù)據(jù)集

表3 數(shù)據(jù)切片

4.1 處理時(shí)間分析

D-DSNBLP隱私保護(hù)方法通過修改結(jié)點(diǎn)的鏈接操作達(dá)到k-度匿名，保證圖結(jié)構(gòu)信息的同時(shí)，提高處理大規(guī)模社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集的效率。對(duì)表2的四種數(shù)據(jù)集執(zhí)行D-DSNBLP方法。由圖4可知在處理小數(shù)據(jù)集（Split_1，Split_2）時(shí)，D-DSNBLP方法在兩個(gè)數(shù)據(jù)集上的執(zhí)行時(shí)間相近，隨著數(shù)據(jù)量的增加（Split_3，Split_4），D-DSNBLP方法執(zhí)行時(shí)間相差無幾，說明Pregel-like模型更適合大數(shù)據(jù)的迭代并行操作。從并行處理的角度，資源越多，處理速度越快，由于worker是集群資源的貢獻(xiàn)結(jié)點(diǎn)，由圖5可知，Spark集群在處理任務(wù)時(shí)，將任務(wù)分發(fā)到不同的worker上，運(yùn)行時(shí)間隨著worker的增大而減小。當(dāng)worker數(shù)量增加時(shí)，并行處理的速度也會(huì)有所提升。無限地提升worker的數(shù)量并不一定能夠加快算法執(zhí)行速度，原因可能是由于worker的數(shù)量增多導(dǎo)致worker之間的通信量過大，此時(shí)計(jì)算性能的提升被網(wǎng)絡(luò)開銷的代價(jià)所抵消。

圖4 處理效率分析圖

圖5 D-DSNBLP方法中worker對(duì)運(yùn)行效率的影響

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

D-DSNBLP隱私保護(hù)方法是基于預(yù)測(cè)鏈接和添加偽邊進(jìn)行k-度匿名方法，很好地保護(hù)了動(dòng)態(tài)圖的結(jié)構(gòu)。通過測(cè)試添加偽邊前后動(dòng)態(tài)圖結(jié)構(gòu)變化情況來分析數(shù)據(jù)可用性，主要衡量邊的變化和平均聚集系數(shù)，并說明圖結(jié)構(gòu)的變化程度。

圖數(shù)據(jù)可用性與圖結(jié)構(gòu)的變化程度呈反相關(guān)的趨勢(shì)，圖結(jié)構(gòu)變化越大，則圖數(shù)據(jù)的可用性越低，反之則越高。圖結(jié)構(gòu)的變化C是指匿名圖G*中邊的數(shù)量相對(duì)于原始圖的改變量，C=|E(G*)-E(G)|。如圖6所示，將傳統(tǒng)方法修改的邊的數(shù)量與D-DSNBLP方法修改的邊的數(shù)量進(jìn)行比較，假定k=5，隨著t時(shí)刻動(dòng)態(tài)圖的發(fā)布，原始算法對(duì)于圖的修改量增加迅速，而D-DSNBLP因?yàn)樵谔砑舆叺臅r(shí)候選擇下一個(gè)發(fā)布圖中可能存在的鏈接關(guān)系，所以圖的修改量增加較為緩慢，圖數(shù)據(jù)的可用性提高。對(duì)于數(shù)據(jù)集A，由圖7可知，AMBOGP對(duì)于圖的修改量隨著k值的增加不斷增大，而D-DSNBLP對(duì)于圖的修改量相對(duì)較小。這是由于動(dòng)態(tài)劃分組可以最小化圖的修改量，使得D-DSNBLP方法更好地保證圖數(shù)據(jù)的可用性。

圖6 圖修改量隨著t時(shí)刻的變化

圖7 圖修改量隨著k值的變化

針對(duì)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)的不斷變化，評(píng)估其匿名圖與原始圖的拓?fù)浣Y(jié)構(gòu)的改變，若改變較小，說明其結(jié)構(gòu)保持較好，數(shù)據(jù)可用性較高。圖的拓?fù)浣Y(jié)構(gòu)有平均聚集系數(shù)、平均最短路徑、接近中心性等，限于篇幅，分析平均聚集系數(shù)在動(dòng)態(tài)圖匿名前后的改變。平均聚集系數(shù)用來度量圖結(jié)構(gòu)的聚集程度。D-DSNBLP方法中邊的修改會(huì)導(dǎo)致圖的聚集系數(shù)的改變。圖8分析在不同時(shí)刻預(yù)測(cè)邊對(duì)平均聚集系數(shù)（Average Clustering Coefficient，ACC）的影響。預(yù)測(cè)鏈接技術(shù)通過減少未來圖中邊的修改量來提高圖數(shù)據(jù)的可用性。隨著動(dòng)態(tài)圖的發(fā)布，原始算法添加的邊的數(shù)量呈上升趨勢(shì)，這是由于邊的添加使得圖中三角形的個(gè)數(shù)增多，從而平均聚集系數(shù)增大。與原始算法相比，D-DSNBLP隱私保護(hù)方法對(duì)原始圖的聚集系數(shù)保持較好，數(shù)據(jù)可用性較高。

圖8 不同時(shí)刻聚集系數(shù)的變化

由于預(yù)測(cè)精度的高低直接影響圖匿名添加的偽邊質(zhì)量高低，圖9著重分析了預(yù)測(cè)邊在未來圖的匿名過程中，預(yù)測(cè)的精確度對(duì)動(dòng)態(tài)圖匿名的影響。相比t時(shí)刻，t+1時(shí)刻添加的邊為E(Gt+1)-E(Gt)，在t時(shí)刻加入的

即t時(shí)刻匿名圖添加的偽邊與t+1時(shí)刻網(wǎng)絡(luò)中真實(shí)添加的邊的交集除以t+1時(shí)刻真實(shí)添加的邊。當(dāng)預(yù)測(cè)的準(zhǔn)確度提高時(shí)，匿名代價(jià)隨之降低，圖結(jié)構(gòu)受到的影響較小。而選擇添加邊的衡量指標(biāo)由UMC值來決定，因此accurate與UMC值中的a值關(guān)系緊密。在a=0.5時(shí)，預(yù)測(cè)的值達(dá)到最大，這是因?yàn)樵陉P(guān)系網(wǎng)中，結(jié)點(diǎn)間的相似度與共同鄰居個(gè)數(shù)和他們之間的路徑數(shù)量均有很大關(guān)系。在a=0.9,a=1.0時(shí)，預(yù)測(cè)精準(zhǔn)度不高。這說明單獨(dú)以共同鄰居個(gè)數(shù)作為衡量指標(biāo)過于片面。在a=0.3,a=0.4時(shí)，預(yù)測(cè)精度更接近最大值，是因?yàn)槁窂絺€(gè)數(shù)信息比共同鄰居信息更能反映結(jié)點(diǎn)之間關(guān)系的鏈接強(qiáng)度。偽邊是，預(yù)測(cè)精確度為：

圖9 a值對(duì)UMC值的影響

5 結(jié)束語

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，社會(huì)網(wǎng)絡(luò)數(shù)據(jù)呈現(xiàn)出數(shù)據(jù)規(guī)模大，數(shù)據(jù)多樣性等特點(diǎn)，以至于在單機(jī)工作站環(huán)境下處理大規(guī)模圖數(shù)據(jù)時(shí)出現(xiàn)數(shù)據(jù)可用性差和處理效率低的問題。因此，實(shí)現(xiàn)社會(huì)網(wǎng)絡(luò)隱私保護(hù)技術(shù)的并行化計(jì)算已成為未來趨勢(shì)。針對(duì)社會(huì)網(wǎng)絡(luò)中的結(jié)點(diǎn)隱私保護(hù)問題，提出了云環(huán)境下利用預(yù)測(cè)鏈接的社會(huì)網(wǎng)絡(luò)隱私保護(hù)方法D-DSNBLP。該方法通過Pregel-like模型，利用基本的集合操作和消息迭代更新模型，完成了在大規(guī)模社會(huì)網(wǎng)絡(luò)圖數(shù)據(jù)中動(dòng)態(tài)劃分組，構(gòu)建候選結(jié)點(diǎn)集合，構(gòu)建互斥邊集合等操作。實(shí)驗(yàn)結(jié)果表明，D-DSNBLP方法提高了處理大規(guī)模圖數(shù)據(jù)的速度，保證了隱私保護(hù)效果和數(shù)據(jù)發(fā)布的可用性。