應用預測鏈接的分布式社會網(wǎng)絡隱私保護方法

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

內蒙古科技大學 信息工程學院，內蒙古 包頭 014010

1 引言

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

2 相關知識

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

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

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

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

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

在社會網(wǎng)絡圖中，共同鄰居信息是預測鏈接的衡量指標之一，但是單獨以共同鄰居作為預測鏈接的指標，忽略了共同鄰居之間的關系，因此使用路徑信息進一步獲得結點之間的鏈接強度。即將共同鄰居數(shù)量和路徑信息同時作為達到匿名圖的度量標準UMC（Utility Metric Criteration）：

UMC值越大說明兩個結點鏈接關系越強，在下一時刻存在鏈接的可能性也越大。

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

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

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

3 D-DSNBLP隱私保護方法

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

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

算法1 D-DSNBLP隱私保護方法

輸入：社會網(wǎng)絡圖Γ={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度匿名計算所有結點在一個組時的匿名代價，同時給定組編號和結點的Attr

13. if結點個數(shù)小于2k

14.返回costall

15.else

16. for i←k to結點個數(shù)-k

17. costi=計算以i為分界點的代價（此處迭代調用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 社會網(wǎng)絡圖

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

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

表1 度序列及結點屬性

3.1 并行構建候選結點集合

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

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

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

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

算法2構建候選結點集合

輸入：帶結點屬性Attr(v)的原始圖G。

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

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

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

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

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

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

圖2 結點接收、發(fā)送信息

3.2 互斥邊集合

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

算法3構建互斥邊集合

輸入：所有結點的候選邊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)},此時兩條邊均滿足條件，則EdgeSet{(v16,v5),(v12,v15)}。此時S中的Attr均為0，直接刪除即可，S為空，則t+1時刻匿名圖如圖3所示。

圖3 t+1時刻社會網(wǎng)絡匿名圖

4 實驗結果與分析

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

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

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

4.1 處理時間分析

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

圖4 處理效率分析圖

圖5 D-DSNBLP方法中worker對運行效率的影響

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

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

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

圖6 圖修改量隨著t時刻的變化

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

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

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

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

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

圖9 a值對UMC值的影響

5 結束語

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