李 娜，張曉琳+，王永平，高 鷺，劉立新,2

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

0 引 言

在不損害用戶隱私的情況下，隱私保護數(shù)據(jù)發(fā)布能夠提供一套工具，解決方案及框架去與研究者或數(shù)據(jù)分析者分享有價值的信息[1]。在匿名過程中，社會網(wǎng)絡(luò)隱私保護方法主要分為頂點k-匿名、子圖k-匿名、數(shù)據(jù)擾亂和推演控制等。對于海量的社會網(wǎng)絡(luò)圖數(shù)據(jù)，深入研究并行化匿名技術(shù)是提高數(shù)據(jù)處理效率的有效途徑。復雜社會網(wǎng)絡(luò)除了具有小世界特性及無標度特性之外，還具有一定的社區(qū)結(jié)構(gòu)。復雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)對分析復雜網(wǎng)絡(luò)頂點的傳播性質(zhì)、網(wǎng)絡(luò)的層級結(jié)構(gòu)以及社區(qū)的形成，挖掘其內(nèi)部的網(wǎng)絡(luò)特征具有重要意義[2]。而現(xiàn)有的大部分社會網(wǎng)絡(luò)匿名模型在滿足隱私要求的同時忽略對社區(qū)結(jié)構(gòu)的保護，降低了發(fā)布圖在社區(qū)結(jié)構(gòu)方面的數(shù)據(jù)利用率。針對以上問題，提出一種保護社區(qū)結(jié)構(gòu)的社會網(wǎng)絡(luò)分布式匿名算法，該算法能夠有效保護社會網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。

1 相關(guān)工作

隨著社會網(wǎng)絡(luò)的磅礴發(fā)展，愈來愈多的人們投入到這場新的社交盛宴。人們在享受社交網(wǎng)絡(luò)帶來諸多便利的同時，用戶隱私信息的泄露成為亟待解決的問題。關(guān)于社交網(wǎng)絡(luò)中要保留的隱私信息，目前已經(jīng)確定了3種主要的隱私威脅[3]：身份披露[3-8,16]、屬性披露[9]以及鏈接披露[10-12]。

為了抵御身份披露，研究者相繼提出了多種匿名方法，其主要途徑基于圖修改技術(shù)。社會網(wǎng)絡(luò)頂點身份披露包括很多子類別，如頂點存在性、頂點屬性以及圖度量[3]。文獻[4]針對社會網(wǎng)絡(luò)數(shù)據(jù)匿名過程中g(shù)raphlet結(jié)構(gòu)信息的過度丟失問題，提出了一種基于graphlet結(jié)構(gòu)感知的分層k匿名技術(shù)。文獻[5]考慮保護加權(quán)社會網(wǎng)絡(luò)中頂點免受基于權(quán)重的攻擊，并提出一種基于加權(quán)社會網(wǎng)絡(luò)的k加權(quán)泛化匿名方法KWGA，該方法將k-匿名與泛化方法相結(jié)合，保證了社交網(wǎng)絡(luò)數(shù)據(jù)發(fā)布時的安全性。文獻[6]提出了一種大型網(wǎng)絡(luò)k度匿名算法，該算法使用單變量微聚集技術(shù)獲得匿名度序列，并同時考慮邊緣相關(guān)性，通過隨機邊選擇和領(lǐng)域中心性邊選擇兩種構(gòu)圖方式來達到期望的k-度匿名值，使得匿名圖中保留了原始網(wǎng)絡(luò)中最重要的邊，提高數(shù)據(jù)效用。為了減少匿名過程中的信息損失及社會網(wǎng)絡(luò)發(fā)布圖結(jié)構(gòu)特征改變量，文獻[7]提出了一種新穎的k-度匿名模型，該模型不僅能夠?qū)崿F(xiàn)基于圖的k-度匿名化的隱私保護，還能提高抵御度屬性攻擊的能力。文獻[8]提出了一種省時間的k-度匿名方法TSRAM，該方法在頂點分組過程中使用一次性掃描算法以實現(xiàn)不同的k值需求。文獻[16]提出了一種改進的k度匿名模型，該方法在劃分社區(qū)的基礎(chǔ)上通過邊緣插入操作構(gòu)造匿名圖，使得發(fā)布圖中同組頂點基于度值不可區(qū)分。現(xiàn)有的社會網(wǎng)絡(luò)隱私保護算法在滿足匿名要求的同時能夠有效減少匿名代價，但是這些方法在對原始社會網(wǎng)絡(luò)進行圖修改過程中不能很好地保護原始社會網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，導致社會網(wǎng)絡(luò)發(fā)布圖社區(qū)結(jié)構(gòu)可用性不高。

社區(qū)結(jié)構(gòu)作為社會網(wǎng)絡(luò)圖中普遍具有的拓撲特征，它能夠幫助研究者們更好理解社會網(wǎng)絡(luò)結(jié)構(gòu)與社會網(wǎng)絡(luò)功能之間的關(guān)系。文獻[13]利用原始集的上近似概念提出一種社會網(wǎng)絡(luò)圖隱私保護方案，在匿名過程中能夠有效保護圖形社區(qū)結(jié)構(gòu)。文獻[14]提出一種隨機擾動方法，采用貪婪聚類方法對頂點進行分組，將原始社會網(wǎng)絡(luò)圖轉(zhuǎn)化為k分組圖，在k分組圖上執(zhí)行圖形重構(gòu)操作，使得已發(fā)布的社會網(wǎng)絡(luò)圖在達到k匿名的隱私要求的同時保護原始社會網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。文獻[15]提出了一種概率匿名方法來保護數(shù)據(jù)隱私，在擾動過程中考慮了數(shù)據(jù)的社區(qū)結(jié)構(gòu)信息，該方法將k-匿名與隨機擾動相結(jié)合，能夠達到最小化對社區(qū)結(jié)構(gòu)影響的目的。

大部分隱私保護模型在社區(qū)結(jié)構(gòu)保護方面還存在著很大的局限，這對研究人員分析社區(qū)結(jié)構(gòu)性質(zhì)造成了很大影響，極大地降低了數(shù)據(jù)在社區(qū)結(jié)構(gòu)方面的可用性。因此，本文研究社會網(wǎng)絡(luò)頂點身份再識別問題，設(shè)計了一種保護社區(qū)結(jié)構(gòu)的社會網(wǎng)絡(luò)度匿名(SNDA-PCS)算法，本文主要貢獻如下：

(1)針對社會網(wǎng)絡(luò)無向圖，提出一種保護社區(qū)結(jié)構(gòu)的社會網(wǎng)絡(luò)k-度匿名模型，從而有效地防止攻擊者以頂點度為背景知識的隱私攻擊；

(2)提出一種保護社區(qū)結(jié)構(gòu)的分布式社會網(wǎng)絡(luò)k-度匿名算法。通過壓縮二叉樹得到匿名度序列，添加虛擬頂點構(gòu)造匿名圖，為了減少信息損失，基于頂點所屬社區(qū)提出并行圖重構(gòu)算法來減少虛擬頂點數(shù)量，社會網(wǎng)絡(luò)滿足匿名的同時保證社區(qū)結(jié)構(gòu)可用性；

(3)通過在真實數(shù)據(jù)集上的實驗測試與分析，驗證了SNDA-PCS算法的有效性以及社會網(wǎng)絡(luò)發(fā)布圖在社區(qū)結(jié)構(gòu)方面的高可用性。

2 預備知識及問題定義

社會網(wǎng)絡(luò)無向圖表示為G(V,E)， 其中V={v1,v2,…,vn} 是頂點集合，代表社會網(wǎng)絡(luò)中的用戶；E是邊集合代表用戶之間的聯(lián)系，即e(vi,vj)=eij，vi,vj∈V。 多元組dG=(d1,d2,…di…,dn) 表示社會網(wǎng)絡(luò)無向圖G(V,E) 的頂點度序列,其中di表示頂點vi的度且di≤di+1。

2.1 社會網(wǎng)絡(luò)社區(qū)劃分

社區(qū)發(fā)現(xiàn)算法的優(yōu)劣對理解網(wǎng)絡(luò)的組織與功能產(chǎn)生直接影響。針對社會網(wǎng)絡(luò)無向圖，文獻[17]提出一種兩階段策略的社區(qū)劃分算法(DA)，使用基于普通鄰居度值計算的AA相似性指數(shù)捕獲社會網(wǎng)絡(luò)全局信息和局部信息，即對于社會網(wǎng)絡(luò)中任意兩個頂點vi與vj的公共鄰居度值越低，其越容易在同一個社區(qū)，保證了社區(qū)劃分結(jié)果最優(yōu)。步驟如下：

(1)分裂：基于AA指數(shù)尋找社會網(wǎng)絡(luò)頂點最相似鄰居，將社會網(wǎng)絡(luò)劃分為若干個最相似鄰居群；

(2)聚集：優(yōu)化分裂結(jié)果，根據(jù)吸引力合并分組，合并終止條件為社會網(wǎng)絡(luò)所有分組均滿足社區(qū)標準。

如圖1(a)為社會網(wǎng)絡(luò)無向圖G(V,E)，12個社會網(wǎng)絡(luò)頂點的分裂結(jié)果為兩個最相似鄰居群：Group1={v1,v3,v4,v5,v11}，Group2={v2,v6,v7,v8,v9,v10,v12}。 由于Group1和Group2均滿足社區(qū)標準，即社區(qū)劃分結(jié)果為：C1=Group1，C2=Group2， 如圖1(b)所示。

圖1 基于DA算法的社區(qū)劃分

2.2 保護社區(qū)結(jié)構(gòu)的社會網(wǎng)絡(luò)k-度匿名模型

社會網(wǎng)絡(luò)無向圖中，攻擊者可以通過頂點度知識成功識別目標頂點，傳統(tǒng)的k-度匿名模型確保發(fā)布圖中的任意一個頂點vi∈V，均存在至少k-1個其它頂點與頂點vi度值相等。隱私保護的目的是將原始社會網(wǎng)絡(luò)圖通過最小的圖修改操作轉(zhuǎn)化為滿足k-度匿名的發(fā)布圖。但是，傳統(tǒng)的圖修改過程破壞了社會網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)，因此針對社會網(wǎng)絡(luò)無向圖，抵御攻擊者將度作為背景知識的頂點身份再識別攻擊，提出保護社區(qū)結(jié)構(gòu)的社會網(wǎng)絡(luò)k-度匿名模型。

定義1 保護社區(qū)結(jié)構(gòu)的k-度匿名隱私目標：已知社會網(wǎng)絡(luò)無向圖G(V,E)， 正整數(shù)k，使社會網(wǎng)絡(luò)發(fā)布圖G*(V*,E*) 滿足以下隱私目標：

(1)攻擊者基于頂點度成功識別目標頂點的概率不超過1/k；

(2)匿名過程中，原始頂點與原始邊不發(fā)生變化；

(3)匿名過程中，在保證效用的同時保護社會網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。

圖2 同社區(qū)虛擬頂點刪除-添加結(jié)果G# (社會網(wǎng)絡(luò)發(fā)布圖G*)

定義2 保護社區(qū)結(jié)構(gòu)的社會網(wǎng)絡(luò)k-度匿名模型：給定社會網(wǎng)絡(luò)無向圖G(V,E) 以及一個參數(shù)k，若社會網(wǎng)絡(luò)發(fā)布圖G*(V*,E*) 滿足以下3個條件，稱G*(V*,E*) 符合保護社區(qū)結(jié)構(gòu)的社會網(wǎng)絡(luò)k-度匿名模型。

(1)使用DA算法劃分社區(qū)，確定原始社會網(wǎng)絡(luò)圖中頂點所屬社區(qū)；

(2)根據(jù)頂點度序列構(gòu)造壓縮二叉樹，獲得頂點分組結(jié)果及匿名度序列；

(3)根據(jù)匿名度序列分布并行構(gòu)造匿名圖，圖重構(gòu)基于分布式圖處理系統(tǒng)spark graphX實現(xiàn)，減少信息損失，保證發(fā)布圖社區(qū)結(jié)構(gòu)可用性。

3 保護社區(qū)結(jié)構(gòu)的社會網(wǎng)絡(luò)度匿名算法(SNDA-PCS)

保護社區(qū)結(jié)構(gòu)的社會網(wǎng)絡(luò)度匿名算法(SNDA-PCS)，其基本過程包括兩個步驟：頂點分組匿名；圖重構(gòu)。

3.1 頂點分組匿名

頂點分組匿名是以匿名代價最小為目標對社會網(wǎng)絡(luò)無向圖頂點度進行分組并匿名，其次根據(jù)度匿名序列構(gòu)造匿名圖。由于匿名過程中刪除邊比添加邊更嚴重破壞了圖的結(jié)構(gòu)信息[18]，因此，SNDA-PCS算法通過添加虛擬頂點構(gòu)造匿名圖。為了實現(xiàn)以上目標，本文對文獻[8]提出的頂點分組匿名算法進行改進，具體步驟如下：

(1)生成聚合向量：給定社會網(wǎng)絡(luò)無向圖G(V,E)， 根據(jù)頂點度序列dG=(d1,d2,…di…,dn) 生成聚合向量AV(G)={(D,C)|D∈dG，C=|D|}, 其中D表示無向圖中任意一個頂點的度di，C表示頂點度序列dG中值為di的頂點計數(shù)；

(2)構(gòu)造壓縮二叉樹：聚合向量AV(G) 構(gòu)成二叉樹的葉子節(jié)點，自左向右選擇計數(shù)最低的葉子節(jié)點，基于節(jié)點相似性合并葉子節(jié)點，生成父親節(jié)點的聚合向量計算過程如式(1)所示，自底向上通過多次迭代直到壓縮二叉樹構(gòu)造完成

(D(vi),C(vi))∪(D(vj),C(vj))→ (max(D(vi),D(vj)),C(vi)+C(vj))

(1)

(2)

相似性計算過程中，二叉樹節(jié)點間電勢場計算如式(2)所示。其中rij表示節(jié)點i與節(jié)點j間的歐幾里得距離

(3)

其次，由式(3)計算節(jié)點i的總電勢，節(jié)點選擇最相似鄰居節(jié)點合并，相似性[8]計算如式(4)所示

(4)

(3)劃切線：切線從樹根向下遍歷，停止條件為該節(jié)點至少存在一個子節(jié)點對應(yīng)聚合向量的計數(shù)小于匿名強度k，切線上每一個節(jié)點對應(yīng)的葉子節(jié)點為一個分組，表示當前節(jié)點的聚合向量反映該分組的匿名度值。以此類推，獲得無向圖G(V,E) 頂點分組匿名結(jié)果。

圖4 社會網(wǎng)絡(luò)匿名圖G′

3.2 圖重構(gòu)

為了減少信息損失，基于頂點所屬社區(qū)設(shè)計虛擬頂點刪除-添加條件及規(guī)則，圖重構(gòu)過程基于分布式圖處理系統(tǒng)GraphX實現(xiàn)，具體步驟為：同社區(qū)虛擬頂點刪除-添加；不同社區(qū)虛擬頂點刪除添加。

為了選擇最優(yōu)鄰居虛擬頂點進行刪除-添加，需要得到n跳虛擬鄰居列表信息(dummy neighbor table，DNT)，頂點數(shù)據(jù)結(jié)構(gòu)由五元組 (NID,deg(Nu),com,type,tag) 表示，每一個五元組都是一個虛擬鄰居列表單元(dummy neighbor table entry，DNTE)，在DNTE中：NID表示頂點編號， deg(Nu) 表示頂點Nu的度，com表示頂點Nu所屬社區(qū)，type表示頂點Nu所屬類型，即type=0代表頂點Nu屬于虛擬頂點，type=1表示頂點Nu屬于原始頂點，tag表示頂點Nu的度deg(Nu) 是否存在于已匿名度值集合DSet中，若存在，tag=1，否則，tag=0。

定義3 同社區(qū)虛擬頂點刪除-添加條件RACSC：若虛擬頂點Nu與虛擬頂點Nv可進行同社區(qū)虛擬頂點刪除-添加，則Nu及Nv需同時滿足以下3個條件：

(1)deg(Nu)+deg(Nv)≤SC_degmax， 其中SC_degmax表示Nu所在社區(qū)中頂點最大匿名度值；

(2)對type=1的頂點Nw， 若邊e(Nu,Nw) 與邊e(Nv,Nw) 不同時存在；

(3)Nu.com=Nv.com。

定義4 同社區(qū)虛擬頂點刪除-添加規(guī)則RARSC：任意頂點Nu滿足type=0，在Nu的虛擬鄰居列表DNT中，滿足RACSC的頂點Nv構(gòu)成頂點Nu的候選集合Nu.CandiSet_sc。 同社區(qū)虛擬頂點刪除-添加規(guī)則如下：

(1)若集合Nu.CandiSet_sc中元素唯一，直接將其與Nu進行刪除-添加；

(2)若集合Nu.CandiSet_sc中元素個數(shù)大于1，則優(yōu)先考慮deg(Nu)+deg(Nv) 值小的虛擬頂點Nv進行刪除-添加。

在同社區(qū)虛擬頂點刪除-添加過程中，任意虛擬頂點Nu從集合Nu.CandiSet_sc中選擇最佳虛擬頂點算法(same community select，SCS)如算法1所示。

算法1：同社區(qū)選擇最佳虛擬頂點算法(SCS)

輸入：Nu.CandiSet_sc

輸出：Nv

(1)if(Nu.CandiSet_sc.size>1)then

(2)for(eachNvinNu.CandiSet_sc)do

(3) deg(Nr)=deg(Nu)+deg(Nv);

(4)endfor

(5) M=the number of dummy nodes with degree equal to min(deg(Nr));

(6)if(M=1)then

(7) returnNv;

(8)else

(9) randomly selectNv;

(10) returnNv;

(11)endif

(12)else

(13) returnNv;

(14)endif

算法2為社會網(wǎng)絡(luò)同社區(qū)虛擬頂點刪除-添加算法SCRA。SCRA算法將初始匿名圖作為輸入，第(2)行～第(4)行尋找虛擬頂點的虛擬鄰居列表信息DNT，第(5)行～第(9)行獲得虛擬頂點的候選集合。第(10)行～第(16)行獲得待刪除-添加的虛擬頂點對集合，第(18)行～第(24)行表示所有超步完成后執(zhí)行虛擬頂點刪除-添加操作。

算法2：同社區(qū)虛擬頂點刪除-添加算法(SCRA)

輸入：初始匿名圖G′

輸出：G#

(1)forSuperStep=1 to 6do

(2) sendMessToNeighbors;

(3)for(each dummy nodeNuinG′)do

(4) updateNu. DNT;

(5)for(eachNvinNu.DNT)do

(6)if(Nvsatisfy RACSC)then

(7)Nu.CandiSet_sc←Nv;

(8)endif

(9)endfor

(10) updateNu.CandiSet_sc;

(11) if (Nu.CandiSet_sc≥1) then

(12)Nv=SCS(Nu.CandiSet_sc);

(13)CandiSet_sc←(Nu,Nv);

(14)endif

(15)endfor

(16) VoteToHalt (Nu,Nv);

(17)endfor

(18)for(each (Nu,Nv) in CandiSet_sc)do

(19)G′.EdgeRDD.Remove;

(20)G′.EdgeRDD.Remove;

(21)G′.EdgeRDD.Add;

(22)G′.EdgeRDD.Add;

(23)NDRDD.Add(Nu,Nv);

(24)endfor

(25) returnG#;

如圖4所示的社會網(wǎng)絡(luò)初始匿名圖G′，執(zhí)行算法2，當superstep=1及superstep=2時，所有type=0的頂點候選集合均為空。當superstep=3時，虛擬頂點收到3跳虛擬鄰居列表信息，見表1，從而得到虛擬頂點候選集合見表2。

表1 3跳虛擬鄰居列表信息(DNT)

表2 Superstep=3時虛擬頂點候選集合更新列表

在同社區(qū)虛擬頂點刪除-添加過程的超級步中，每個虛擬頂點最多被合并一次。由SCS算法可知，虛擬頂點N1選擇N2進行刪除-添加，更新虛擬頂點候選集合如表2第三列所示，以此類推，待刪除-添加的虛擬頂點對為 (N1,N2) 和 (N3,N4)。 虛擬頂點N1，N2，N3和N4的狀態(tài)置為Inactive，不參與superstep=3之后的超級步。當superstep=4時，待刪除-添加的虛擬頂點對為 (N5,N7)， 此時虛擬頂點N5，N7狀態(tài)置為Inactive。所有超步完成后執(zhí)行虛擬頂點刪除-添加操作，算法迭代兩次后完成同社區(qū)虛擬頂點刪除-添加過程，得到匿名圖G#如圖2所示。

定義5 不同社區(qū)虛擬頂點刪除-添加條件RACDC：若虛擬頂點Nu與虛擬頂點Nv可進行不同社區(qū)虛擬頂點刪除-添加，Nu及Nv需同時滿足以下3個條件：

(1)deg(Nu)+deg(Nv)≤degmax且deg(Nu)+deg(Nv)∈DSet， 其中degmax代表社會網(wǎng)絡(luò)圖中最大匿名度值；

(2)對type=1的頂點Nw， 若邊e(Nu,Nw) 與邊e(Nv,Nw) 不同時存在；

定義6 不同社區(qū)虛擬頂點刪除-添加規(guī)則RARDC：任意虛擬頂點Nu滿足tag=0，得到Nu的虛擬鄰居列表DNT，若DNT中的頂點Nv滿足RACDC，則將其放置在Nu的候選集合Nu.CandiSet_dc中，不同社區(qū)虛擬頂點刪除-添加規(guī)則如下：

(1)若集合Nu.CandiSet_dc中元素唯一，直接將其與Nu進行刪除-添加；

(2)若集合Nu.CandiSet_dc中元素個數(shù)大于1，優(yōu)先選擇tag=0的虛擬頂點，其次選擇deg(Nu)+deg(Nv) 值小的虛擬頂點Nv進行刪除-添加。

在不同社區(qū)虛擬頂點刪除-添加過程中，虛擬頂點選擇最佳頂點算法DCS如算法3所示。

算法3：不同社區(qū)選擇最佳虛擬頂點算法(DCS)

輸入：Nu.CandiSet_dc

輸出：Nv

(1)if(Nu.CandiSet_dc.size>1)then

(2)for(eachNvinNu.CandiSet_dc)do

(3)if(Nu.tag=0&&Nv.tag=0)then

(4)List1u←Nv;

(5)else(Nu.tag=0&&Nv.tag=1)then

(6)List2u←Nv;

(7)endif

(8)endfor

(9)if(List1u.size!=0) do

(10)List=List1u;

(11)else

(12)List=List2u;

(13)endif

(14)for(eachNvn List)do

(15)deg(Nr)=deg(Nu)+deg(Nv);

(16)endfor

(17) M=the number of dummy nodes with degree equal to min(deg(Nr));

(18)if(M=1)then

(19) returnNv;

(20)else(M>1)then

(21) randomly selectNv;

(22) returnNv;

(23)endif

(24)else

(25) returnNv;

(26)endif

同社區(qū)虛擬頂點刪除-添加操作執(zhí)行后，在社會網(wǎng)絡(luò)匿名圖G#中，若存在tag=0的虛擬頂點，執(zhí)行算法4，即不同社區(qū)之間虛擬頂點刪除-添加操作。在DCRA算法中，第(2)行～第(9)行獲得tag=0的虛擬頂點的候選集合，第(10)行～第(14)行尋找待刪除-添加虛擬頂點對，第(18)行～第(24)行完成虛擬頂點刪除-添加過程，DCRA算法輸出社會網(wǎng)絡(luò)發(fā)布圖G*。

算法4：不同社區(qū)虛擬頂點刪除-添加算法(DCRA)

輸入：G#

輸出：G*

(1)for(SuperStep=1 to 6)do

(2) sendMessToNeighbors;

(3)if(dummy nodeNu.tag=0 inG#)then

(4) updateNu. DNT;

(5)for(eachNvinNu. DNT)do

(6)if(Nvsatisfy RACDC)then

(7)Nu.CandiSet_dc←Nv;

(8)endif

(9)endfor

(10) updateNu.CandiSet_dc;

(11)if(Nu.CandiSet_dc≥1)then

(12)Nv=DCS(Nu.CandiSet_dc);

(13)CandiSet_dc←(Nu,Nv);

(14)endif

(15)endif

(16) VoteToHalt (Nu,Nv);

(17)endfor

(18)for(each (Nu,Nv) in CandiSet_dc)do

(19)G#.EdgeRDD.Remove;

(20)G#.EdgeRDD.Remove;

(21)G#.EdgeRDD.Add;

(22)G#.EdgeRDD.Add;

(23)NDRDD.Add(Nu,Nv);

(24)endfor

(25) returnG*;

保護社區(qū)結(jié)構(gòu)的社會網(wǎng)絡(luò)度匿名算法(SNDA-PCS)如下所示。

算法5：保護社區(qū)結(jié)構(gòu)的社會網(wǎng)絡(luò)度匿名算法(SNDA-PCS)

輸入：G

輸出：G*

(2) 根據(jù)匿名度序列d*在原始圖G中添加虛擬頂點生成初始匿名圖G′;

(3) Initial:G′， NDRDD=?，Nu.CandiSet_sc=?，Nu.CandiSet_dc=?, EdgeRDD=G′.EdgeRDD;

(4) update DSet;

(5)while(?Nu,Nv∈G′&&Nu,Nvsatisfy RACSC)do

(6)G#=SCRA(G′);

(7)endwhile

(8)if(?Nu∈G#&&Nu.tag!=1)then

(9)G*=DCRA(G#)；

(10)else

(11)G*=G#；

(12)endif

(13) returnG*；

如圖2所示，匿名度值集合DSet={2,3,6}， 由于所有type=0的頂點tag值均為1，因此不需要執(zhí)行DCRA算法，即社會網(wǎng)絡(luò)匿名圖G#滿足保護社區(qū)結(jié)構(gòu)的社會網(wǎng)絡(luò)k-度匿名模型(G*=G#)。

4 性能分析與評價

本節(jié)從處理時間、信息損失分析及社區(qū)結(jié)構(gòu)可用性分析等3個維度對SNDA-PCS隱私保護算法進行性能分析和評價，將SNDA-PCS算法與文獻[19]提出的經(jīng)典k度匿名(KDA)算法進行對比。

4.1 實驗設(shè)置

實驗采用兩個真實社會網(wǎng)絡(luò)數(shù)據(jù)集對算法進行測試：ca_CondMat和Oregon。ca_CondMat網(wǎng)絡(luò)是Arxiv凝聚態(tài)物質(zhì)科學合作網(wǎng)絡(luò)，若作者i與作者j合著了一篇論文，則該圖包含一條從i到j(luò)的無向邊。該數(shù)據(jù)涵蓋了從1993年1月至2003年4月(共124個月)期間的論文，共包含23 133個頂點及93 497條邊。Oregon數(shù)據(jù)集是來自俄勒岡州路線的自治系統(tǒng)圖，共包含10 981個頂點及30 855條邊。

實驗環(huán)境：CPU 1.80 GHz, RAM 16 GB, Hadoop 2.7.2, Spark 2.4.3以及15個計算節(jié)點；程序設(shè)計語言：Scala 2.13.0。

4.2 處理時間

圖5顯示了在不同數(shù)據(jù)集上，SNDA-PCS算法的執(zhí)行時間隨隱私參數(shù)k值大小的變化情況。從實驗結(jié)果可以看出，隨k值的增加，執(zhí)行時間均呈上升趨勢，SNDA-PCS算法在ca_CondMat數(shù)據(jù)集上的執(zhí)行時間較長。SNDA-PCS算法在圖重構(gòu)過程中先執(zhí)行社區(qū)內(nèi)虛擬頂點刪除-添加操作，再執(zhí)行社區(qū)間虛擬頂點刪除-添加操作，隨著隱私保護程度的增加，社會網(wǎng)絡(luò)初始匿名圖中的虛擬頂點數(shù)量增加，圖重構(gòu)時間增大，因此當匿名強度增加時，SNDA-PCS算法具有相對較高的時間代價。

圖5 運行時間

4.3 信息損失分析

平均路徑長度(average path length，APL)用來描述社會網(wǎng)絡(luò)圖中頂點間最短路徑長度的平均值，公式定義如式(5)所示，其中，n表示圖中的頂點數(shù)，d(vi,vj) 表示頂點vi和vj之間的最短路徑長度。實驗通過平均路徑長度的變化率(rate of change，ROC)衡量發(fā)布圖的信息損失，平均路徑長度變化率越小，匿名后社會網(wǎng)絡(luò)圖結(jié)構(gòu)與原始圖越接近，發(fā)布圖的信息損失越小。平均路徑長度變化率計算公式為 |APL-APL*|/|APL|， APL和APL*分別表示原始圖及發(fā)布圖的平均路徑長度

(5)

圖6(a)顯示了Oregon數(shù)據(jù)集上平均路徑長度隨隱私參數(shù)k的變化情況。為了滿足不同的隱私需求，匿名過程需要進行不同程度的圖修改，即隱私需求越高，圖修改程度越大，因此兩種算法的平均路徑長度變化率均隨k值的增大而增大。但是從整體上看，SNDA-PCS算法的平均路徑長度變化率低于KDA算法，這表明SNDA-PCS算法在匿名過程中能夠有效減少圖結(jié)構(gòu)信息損失。

圖6(b)顯示了不同算法在ca_CondMat數(shù)據(jù)集上平均路徑長度的實驗結(jié)果，平均路徑長度變化率與Oregon數(shù)據(jù)集上的變化趨勢相似，SNDA-PCS算法在匿名過程中更好地保留了原始社會網(wǎng)絡(luò)圖的拓撲結(jié)構(gòu)。

圖6 平均路徑長度

4.4 社區(qū)結(jié)構(gòu)可用性分析

杰卡德相似性(Jaccard similarity)用來衡量兩個集合之間的相似程度，其計算公式如式(6)所示

(6)

(7)

圖7(a)比較了不同算法在ca_CondMat數(shù)據(jù)集上的杰卡德相似性，其值的變化直接反映社會網(wǎng)絡(luò)圖匿名前后社區(qū)結(jié)構(gòu)的改變量，從圖中可以看出，隨匿名強度的增加，隱私保護算法對原始社會網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的破壞越嚴重，發(fā)布圖社區(qū)結(jié)構(gòu)可用性隨之降低。不同k (k∈(0,50]) 值情況下，SNDA-PCS算法對應(yīng)的杰卡德相似性值均高于KDA算法。圖7(b)顯示了不同算法在Oregon數(shù)據(jù)集上杰卡德相似性隨k值的變化情況，SNDA-PCS算法對原始社會網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的保護程度高于0.703，SNDA-PCS算法在社區(qū)結(jié)構(gòu)保護方面效果優(yōu)于KDA算法。

圖7 杰卡德相似性

為了進一步衡量社會網(wǎng)絡(luò)發(fā)布圖社區(qū)結(jié)構(gòu)的可用性，從頂點所屬社區(qū)角度出發(fā)，引入精度指標(precision index)來分析頂點匿名前后所屬社區(qū)的變化。對于給定的具有n個頂點的初始社會網(wǎng)絡(luò)圖G， 精度指標定義如式(8)所示

(8)

其中，ltv(v) 及l(fā)pv(v) 分別表示頂點v在原始圖和發(fā)布圖中所屬社區(qū)的社區(qū)標簽，若頂點v在匿名前后所屬社區(qū)相同，ρltv(v)=lpv(v)值為1，反之，值為0。精度指標值越高，社會網(wǎng)絡(luò)發(fā)布圖社區(qū)結(jié)構(gòu)可用性越高。

圖8顯示了精度指標值在不同數(shù)據(jù)集上隨k值的變化情況。精度指標隨隱私參數(shù)的增大而減小，與KDA算法相比較，SNDA-PCS算法的精度指標值更接近于1，這是因為KDA算法在匿名過程中沒有考慮保護社區(qū)結(jié)構(gòu)。從總體上看，SNDA-PCS算法在保護原始社會網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)方面效果較好。

圖8 精度指標

5 結(jié)束語

本文研究了社會網(wǎng)絡(luò)無向圖的社區(qū)結(jié)構(gòu)與隱私保護問題，提出一種保護社區(qū)結(jié)構(gòu)的社會網(wǎng)絡(luò)k-度匿名模型，在此基礎(chǔ)上設(shè)計一種保護社區(qū)結(jié)構(gòu)的分布式社會網(wǎng)絡(luò)k-度匿名算法SNDA-PCS，從而有效解決攻擊者以頂點度為背景知識的頂點身份再識別問題?；谡鎸嵣鐣W(wǎng)絡(luò)數(shù)據(jù)集上的實驗與分析，驗證SNDA-PCS算法能夠在匿名過程中保證原始社會網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)可用性，如杰卡德相似系數(shù)、精度指標等。