保護社區結構的社會網絡匿名技術

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

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

0 引 言

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

1 相關工作

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

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

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

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

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

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

(3)通過在真實數據集上的實驗測試與分析，驗證了SNDA-PCS算法的有效性以及社會網絡發布圖在社區結構方面的高可用性。

2 預備知識及問題定義

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

2.1 社會網絡社區劃分

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

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

(2)聚集：優化分裂結果，根據吸引力合并分組，合并終止條件為社會網絡所有分組均滿足社區標準。

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

圖1 基于DA算法的社區劃分

2.2 保護社區結構的社會網絡k-度匿名模型

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

定義1 保護社區結構的k-度匿名隱私目標：已知社會網絡無向圖G(V,E)， 正整數k，使社會網絡發布圖G*(V*,E*) 滿足以下隱私目標：

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

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

(3)匿名過程中，在保證效用的同時保護社會網絡社區結構。

圖2 同社區虛擬頂點刪除-添加結果G# (社會網絡發布圖G*)

定義2 保護社區結構的社會網絡k-度匿名模型：給定社會網絡無向圖G(V,E) 以及一個參數k，若社會網絡發布圖G*(V*,E*) 滿足以下3個條件，稱G*(V*,E*) 符合保護社區結構的社會網絡k-度匿名模型。

(1)使用DA算法劃分社區，確定原始社會網絡圖中頂點所屬社區；

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

(3)根據匿名度序列分布并行構造匿名圖，圖重構基于分布式圖處理系統spark graphX實現，減少信息損失，保證發布圖社區結構可用性。

3 保護社區結構的社會網絡度匿名算法(SNDA-PCS)

保護社區結構的社會網絡度匿名算法(SNDA-PCS)，其基本過程包括兩個步驟：頂點分組匿名；圖重構。

3.1 頂點分組匿名

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

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

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

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

(1)

(2)

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

(3)

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

(4)

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

圖4 社會網絡匿名圖G′

3.2 圖重構

為了減少信息損失，基于頂點所屬社區設計虛擬頂點刪除-添加條件及規則，圖重構過程基于分布式圖處理系統GraphX實現，具體步驟為：同社區虛擬頂點刪除-添加；不同社區虛擬頂點刪除添加。

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

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

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

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

(3)Nu.com=Nv.com。

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

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

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

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

算法1：同社區選擇最佳虛擬頂點算法(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為社會網絡同社區虛擬頂點刪除-添加算法SCRA。SCRA算法將初始匿名圖作為輸入，第(2)行～第(4)行尋找虛擬頂點的虛擬鄰居列表信息DNT，第(5)行～第(9)行獲得虛擬頂點的候選集合。第(10)行～第(16)行獲得待刪除-添加的虛擬頂點對集合，第(18)行～第(24)行表示所有超步完成后執行虛擬頂點刪除-添加操作。

算法2：同社區虛擬頂點刪除-添加算法(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所示的社會網絡初始匿名圖G′，執行算法2，當superstep=1及superstep=2時，所有type=0的頂點候選集合均為空。當superstep=3時，虛擬頂點收到3跳虛擬鄰居列表信息，見表1，從而得到虛擬頂點候選集合見表2。

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

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

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

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

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

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

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

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

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

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

算法3：不同社區選擇最佳虛擬頂點算法(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

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

算法4：不同社區虛擬頂點刪除-添加算法(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*;

保護社區結構的社會網絡度匿名算法(SNDA-PCS)如下所示。

算法5：保護社區結構的社會網絡度匿名算法(SNDA-PCS)

輸入：G

輸出：G*

(2) 根據匿名度序列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，因此不需要執行DCRA算法，即社會網絡匿名圖G#滿足保護社區結構的社會網絡k-度匿名模型(G*=G#)。

4 性能分析與評價

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

4.1 實驗設置

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

實驗環境：CPU 1.80 GHz, RAM 16 GB, Hadoop 2.7.2, Spark 2.4.3以及15個計算節點；程序設計語言：Scala 2.13.0。

4.2 處理時間

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

圖5 運行時間

4.3 信息損失分析

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

(5)

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

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

圖6 平均路徑長度

4.4 社區結構可用性分析

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

(6)

(7)

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

圖7 杰卡德相似性

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

(8)

其中，ltv(v) 及lpv(v) 分別表示頂點v在原始圖和發布圖中所屬社區的社區標簽，若頂點v在匿名前后所屬社區相同，ρltv(v)=lpv(v)值為1，反之，值為0。精度指標值越高，社會網絡發布圖社區結構可用性越高。

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

圖8 精度指標

5 結束語

本文研究了社會網絡無向圖的社區結構與隱私保護問題，提出一種保護社區結構的社會網絡k-度匿名模型，在此基礎上設計一種保護社區結構的分布式社會網絡k-度匿名算法SNDA-PCS，從而有效解決攻擊者以頂點度為背景知識的頂點身份再識別問題。基于真實社會網絡數據集上的實驗與分析，驗證SNDA-PCS算法能夠在匿名過程中保證原始社會網絡社區結構可用性，如杰卡德相似系數、精度指標等。