基于邊介數(shù)模型的差分隱私保護(hù)方案

黃海平，王凱，湯雄，張東軍

（1. 南京郵電大學(xué)計(jì)算機(jī)學(xué)院，江蘇 南京 210023；2. 江蘇省無(wú)線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210023）

1 引言

快速發(fā)展的社交網(wǎng)絡(luò)應(yīng)用促使大量社交數(shù)據(jù)被廣泛使用，對(duì)用戶隱私構(gòu)成了威脅[1]。因此，社交網(wǎng)絡(luò)的研究者通過(guò)在節(jié)點(diǎn)參數(shù)和圖結(jié)構(gòu)中添加噪聲來(lái)實(shí)現(xiàn)數(shù)據(jù)隱私保護(hù)。然而，即使是引入噪聲的圖數(shù)據(jù)仍然可以實(shí)現(xiàn)去匿名化，尤其是在攻擊者具備相應(yīng)網(wǎng)絡(luò)背景知識(shí)的前提下。隨著社交網(wǎng)絡(luò)在全球范圍內(nèi)的普及，攻擊者將更容易獲得各種類型的背景知識(shí)，隱私泄露的風(fēng)險(xiǎn)也隨之增加。

為了加強(qiáng)隱私保護(hù)的效果，差分隱私技術(shù)[2]被應(yīng)用于社交網(wǎng)絡(luò)中。最早的差分隱私只是對(duì)社交網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行一些簡(jiǎn)單的統(tǒng)計(jì)分析，大多只涉及屬性信息而忽略了結(jié)構(gòu)信息，許多重要的圖屬性都可以通過(guò)子圖計(jì)數(shù)查詢得到。其后，關(guān)系差分隱私框架出現(xiàn)，它保證了社交網(wǎng)絡(luò)中任何一條邊的改變都不會(huì)對(duì)查詢結(jié)果造成太大的影響。然而，盡管關(guān)系差分隱私框架將需要引入的噪聲量從網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量的多項(xiàng)式級(jí)別減少到了多項(xiàng)式對(duì)數(shù)級(jí)別，但相對(duì)于查詢函數(shù)中節(jié)點(diǎn)的數(shù)目，關(guān)系差分隱私需要引入的噪聲量依然是超指數(shù)級(jí)別的，查詢結(jié)果的數(shù)據(jù)可用性依然很難保證。為了在不泄露隱私的情況下安全地發(fā)布真實(shí)的社交網(wǎng)絡(luò)圖數(shù)據(jù)，可應(yīng)用一個(gè)更加強(qiáng)健的匿名技術(shù)框架[3]，其以精妙的方式修改圖結(jié)構(gòu)以提高隱私保護(hù)程度，而保留大部分的原始圖結(jié)構(gòu)。然而，這類方法通常僅能針對(duì)一種特定類型的攻擊方式，而對(duì)一些新型的去匿名化攻擊技術(shù)效果不佳。

鑒于此，本文將尋求一種提供圖數(shù)據(jù)隱私保護(hù)且能保留圖結(jié)構(gòu)的方案，該方案將“重要性”相同的邊劃分成為單獨(dú)的組進(jìn)行加噪處理，在提供了較高強(qiáng)度的隱私保護(hù)性的同時(shí)，保證了社交網(wǎng)絡(luò)圖的數(shù)據(jù)可用性。本文的主要貢獻(xiàn)如下。

1) 結(jié)合dK-匿名結(jié)構(gòu)將排序后的2K序列根據(jù)條件進(jìn)行聚類操作，劃分成一組組子序列，使 2K序列敏感度上限顯著減少，從而大大降低了所需引入的總噪聲量。

2) 提出基于邊介數(shù)模型的差分隱私保護(hù)方案BCPA（betweenness centrality protection algorithm），根據(jù)介數(shù)排序的dK序列將原始圖中“重要性”相同或相近的邊聚類在同一子序列中，分組加噪時(shí)能保證不改變各條邊的“重要性”，在保留了更多結(jié)構(gòu)特征的同時(shí)也具有更好的數(shù)據(jù)可用性。

3) 提出一種基于鄰接度的隱私保護(hù)性衡量算法，可以有效地衡量擾動(dòng)對(duì)原始圖數(shù)據(jù)的影響程度。

2 相關(guān)工作

近年來(lái)，針對(duì)社交網(wǎng)絡(luò)圖結(jié)構(gòu)的差分隱私，研究者們?nèi)〉昧撕芏喑晒?。Hay等[4]提出k-邊差分隱私，即2個(gè)鄰圖最多相差k條邊，以求擾動(dòng)程度與隱私保護(hù)強(qiáng)度之間的平衡，與常用的節(jié)點(diǎn)差分隱私相比，其減小了校準(zhǔn)噪聲的添加，使圖結(jié)構(gòu)分析在k-邊差分隱私時(shí)較為準(zhǔn)確。Mir等[5]試圖用隨機(jī)Kronecker圖[6]生成與原始圖具有相似敏感度的差分隱私拓?fù)鋱D，提供較為準(zhǔn)確的真實(shí)圖像，同時(shí)保護(hù)其中參與個(gè)體的隱私。Day等[7]引入基于邊加法的圖投影方法，提出2種基于聚合和累加直方圖的方法來(lái)發(fā)布滿足差分隱私的擾動(dòng)圖，通過(guò)降低敏感度來(lái)生成逼近真實(shí)度分布的拓?fù)鋱D。

在處理差分隱私發(fā)布圖時(shí)，研究者廣泛運(yùn)用了dK圖隱私模型。Sala等[8]提出一種dK圖隱私模型，設(shè)計(jì)了dK-PA（dK-perturbation algorithm）處理差分隱私的圖發(fā)布，使用dK圖查詢并獲取圖結(jié)構(gòu)的dK序列，對(duì)查詢結(jié)果dK注入差分隱私噪聲獲得擾動(dòng)的dK序列。其后，Sala等[8]又設(shè)計(jì)出DRC（divide randomize and conquer）算法，通過(guò)對(duì)加噪之前的dK序列進(jìn)行聚類分組，以降低算法復(fù)雜度，但是由于全局敏感度較大，所提出的 2K圖隱私模型實(shí)用性比較低。Wang等[9]結(jié)合dK圖模型與隨機(jī)矩陣圖模型，設(shè)計(jì)了針對(duì)圖的1K、2K、3K模型處理算法注入擾動(dòng)參數(shù)，獲取網(wǎng)絡(luò)圖的邊差分隱私。蘭麗輝等[10]針對(duì)權(quán)重社交網(wǎng)絡(luò)，結(jié)合dK圖模型設(shè)計(jì)LWSPA（protection algorithm based on Laplace noise for weighted social network）對(duì)查詢結(jié)果集中的三元組序列進(jìn)行分割，再對(duì)每個(gè)子序列構(gòu)建滿足差分隱私的算法，將查詢結(jié)果集映射為一個(gè)實(shí)數(shù)向量，通過(guò)在向量中注入 Laplace噪聲實(shí)現(xiàn)隱私保護(hù)。然而，這些方法在數(shù)據(jù)可用性方面仍顯不足，除非隱私參數(shù)ε被設(shè)置成不合理的大值。

通過(guò)對(duì)上述相關(guān)工作的研究與分析，本文提出了基于邊介數(shù)模型的差分隱私處理方案。在該方案中，選用dK圖模型來(lái)實(shí)現(xiàn)圖的差分隱私。根據(jù)給定的原始網(wǎng)絡(luò)圖，生成對(duì)應(yīng)的 2K序列；根據(jù)邊中介中心性系數(shù)對(duì)2K序列進(jìn)行重新排序；將排序后的序列聚類為一個(gè)個(gè)子序列，并分組進(jìn)行擾動(dòng)[11]以滿足差分隱私；將擾動(dòng)后的各子序列整合成完整的新2K序列，并還原成圖進(jìn)行發(fā)布。最后，本文將該隱私保護(hù)方案與已有經(jīng)典方案進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明，在較高隱私需求的情況下，其隱私保護(hù)性和大部分?jǐn)?shù)據(jù)可用性都具有一定優(yōu)勢(shì)。

3 模型與算法描述

3.1 差分隱私定義

差分隱私是由Dwork[2]提出的一種隱私保護(hù)模型。該模型可以保證即使攻擊者獲得了所能掌握的最大背景知識(shí)，仍無(wú)法識(shí)別某一條數(shù)據(jù)記錄是否存在于該數(shù)據(jù)集中。同時(shí)，該模型還提出了一種量化分析方法來(lái)表示隱私保護(hù)強(qiáng)度。

定義1若給定 2個(gè)數(shù)據(jù)集D1和D2，有且只有一條記錄不同，表示為，則稱D1和D2為兄弟數(shù)據(jù)表。對(duì)于隨機(jī)算法A，Range(A)用來(lái)表示該算法的輸出結(jié)果集合，即對(duì)于D1與D2的算法輸出結(jié)果S∈Range(A)，若滿足式(1)，則稱算法A滿足ε-差分隱私。

其中，概率Pr表示隱私被披露的風(fēng)險(xiǎn)；ε為調(diào)節(jié)算法A隱私保護(hù)強(qiáng)度的參數(shù)，即隱私預(yù)算參數(shù)，ε越小，數(shù)據(jù)的安全性越高[12]。

定理1非交互輸出擾動(dòng)[13]。設(shè)有函數(shù)集F，其敏感度為S(F)，K為向F中每一個(gè)函數(shù)f的輸出添加獨(dú)立噪聲的算法。若該噪聲為參數(shù)值取的Laplace分布，則算法K滿足ε-差分隱私。其中，對(duì)以兄弟數(shù)據(jù)表為輸入的查詢函數(shù)，敏感度S(F)為其查詢結(jié)果的最大曼哈頓距離。

證明見文獻(xiàn)[13]。

定理2組合性質(zhì)[14]。假設(shè)有n個(gè)隨機(jī)算法，其中Ai滿足εi-差分隱私，且任意2個(gè)算法的操作數(shù)據(jù)集沒(méi)有交集，則{Ai}(1≤i≤n)組合后的算法滿足max(εi)-差分隱私。

證明見文獻(xiàn)[14]。

由定理1可知，敏感度S(F)和差分隱私參數(shù)ε決定了實(shí)現(xiàn)差分隱私需要添加的Laplace噪聲量。

3.2 dK序列及2K敏感度分析

dK序列是一組描述圖屬性的數(shù)據(jù)集合，它可以將不同細(xì)節(jié)級(jí)別的圖結(jié)構(gòu)表示為統(tǒng)計(jì)信息。隨著d值的增加，描述的圖屬性也更加具體。

對(duì)于給定的圖G，0K分布只是圖的平均節(jié)點(diǎn)度；1K分布則是圖的度數(shù)分布；2K分布是圖的聯(lián)合度分布，即具有不同節(jié)點(diǎn)度組合的2節(jié)點(diǎn)子圖的數(shù)目；3K分布表示具有不同節(jié)點(diǎn)度組合的3節(jié)點(diǎn)子圖的數(shù)目，即聚類系數(shù)分布。在極限情況下，nK分布（其中n是圖中的節(jié)點(diǎn)數(shù)）可以捕獲完整的圖結(jié)構(gòu)。圖1給出一個(gè)詳細(xì)的示例，其中列出了所給圖的2K序列和3K序列。

圖1 dK序列示例

dK模型是一個(gè)圖構(gòu)造模型，它利用dK序列捕獲的結(jié)構(gòu)性統(tǒng)計(jì)數(shù)據(jù)集合，生成與原始圖結(jié)構(gòu)類似的圖。對(duì)于給定的圖G，dK圖模型可以對(duì)其進(jìn)行分析以產(chǎn)生相應(yīng)的dK序列，然后使用相應(yīng)的生成器來(lái)構(gòu)造使用dK序列作為輸入的合成圖。

本文方案主要運(yùn)用2K圖模型，因此2K序列敏感度在其中起到至關(guān)重要的作用。設(shè)圖G=(V,E)，其中V是節(jié)點(diǎn)的集合，E是連接V中節(jié)點(diǎn)對(duì)的邊的集合。2K序列形式上是元組{dx,dy;k}的集合，其中，每個(gè)元組表示具有度dx和dy且連接分量為 2的節(jié)點(diǎn)對(duì)的數(shù)量為k。設(shè)m為元組的總數(shù)目，dmax是圖G中的最大節(jié)點(diǎn)度數(shù)，有，且在圖G為完全圖時(shí)取得最大值，因此

函數(shù)的敏感度被定義為當(dāng)函數(shù)域中的一個(gè)元素被修改時(shí)，函數(shù)輸出的最大曼哈頓距離。2K序列的域是圖G，G的鄰圖是所有與G相差至多一條邊的圖G′。改變G中的一條邊將導(dǎo)致在相應(yīng)的2K序列中改變一個(gè)或多個(gè)條目。因此，2K序列的敏感度等于所有G的鄰圖G′中的2K序列的最大變化數(shù)。

定理 32K序列敏感度上限[8]。2K序列的敏感度S2K的上限為4dmax+1。

證明見文獻(xiàn)[8]。

由定理1可知，對(duì)于給定的差分隱私參數(shù)ε，敏感度的上限決定實(shí)現(xiàn)差分隱私所必要的噪聲添加量，因此在這里只討論2K序列敏感度的上限。如果使用更高階的dK序列，將造成更高的敏感度值，這必然會(huì)降低生成的合成圖的精確度。

3.3 基于邊介數(shù)模型的差分隱私處理方案

3.3.1 方案算法流程

若直接對(duì)圖G的2K序列進(jìn)行隨機(jī)擾動(dòng)以滿足差分隱私，需引入大量的噪聲。根據(jù)定理 3，任意圖G上2K序列的敏感度S2K的上限為4dmax+1。為了顯著減少實(shí)現(xiàn)給定級(jí)別差分隱私所必須添加的噪聲量，本文方案根據(jù)各元組中邊中介中心性系數(shù)的平均值大小對(duì)2K序列進(jìn)行重新排序，將數(shù)據(jù)分割成一組組子序列，然后獨(dú)立地對(duì)每個(gè)子序列進(jìn)行擾動(dòng)以實(shí)現(xiàn)ε-差分隱私。下面本文將證明如果在每個(gè)劃分出的子序列上實(shí)現(xiàn)ε-差分隱私，在整個(gè)2K序列也將實(shí)現(xiàn)ε-差分隱私。具體算法流程如算法1所示。

算法1基于邊中介中心性系數(shù)的分組差分隱私

輸入由給定圖G生成的2K序列，用{dx,dy;k}表示，子序列數(shù)量n

輸出滿足差分隱私的新2K序列，用{d′x,d′y;k′}表示

1) 求出2K序列的元組數(shù)量q；

2) fori= 1 toq

4) end for

6) 將排序后的2K序列聚類為一組組子序列；

7) fori= 1 ton

8) 利用dK擾動(dòng)算法向子序列注入噪聲；

9) end for

10) 將擾動(dòng)的子序列合成為新的序列{d′x,d′y;k′}；

具體的實(shí)現(xiàn)過(guò)程將在3.3.2節(jié)～3.3.4節(jié)介紹。

3.3.2 邊介數(shù)排序算法

邊中介中心性系數(shù)（edge betweenness centrality）定義為網(wǎng)絡(luò)中所有最短路徑中經(jīng)過(guò)該條邊的路徑的數(shù)目占最短路徑總數(shù)的比例[15]，即網(wǎng)絡(luò)中包含成員i的所有最短路徑數(shù)占所有最短路徑數(shù)的百分比。它表示邊i的控制能力，其值越大就代表有越多的節(jié)點(diǎn)需要通過(guò)它才能與其他節(jié)點(diǎn)發(fā)生聯(lián)系[16]。對(duì)于給定圖G，N為其節(jié)點(diǎn)數(shù)目，i是圖G中任意一條邊，則邊i的中介中心性系數(shù)的計(jì)算式為

其中，nst表示節(jié)點(diǎn)s與節(jié)點(diǎn)t之間最短路徑的數(shù)目，而nst(i)表示節(jié)點(diǎn)s與節(jié)點(diǎn)t之間通過(guò)邊i的最短路徑的數(shù)目。

由3.2節(jié)可知，2K序列是元組{dx,dy;k}的集合，其中每個(gè)元組表示具有度dx和dy且連接分量為 2的節(jié)點(diǎn)對(duì)的數(shù)量為k，即度為dx的節(jié)點(diǎn)和度為dy的節(jié)點(diǎn)之間連接邊的數(shù)量為k。對(duì)于每個(gè)元組，求出其中包含的邊的中介中心性系數(shù)平均值，并根據(jù)中介中心性系數(shù)平均值由小到大對(duì)2K序列重新排序。具體算法流程如算法2所示。

算法2邊中介中心性系數(shù)平均值計(jì)算

輸入由給定圖G生成的2K序列，用{dx,dy;k}表示

輸出2K序列的邊中介中心性系數(shù)平均值

1) 求出2K序列的元組數(shù)量q；

2) fori= 1 toq

3) 篩選出符合{dx,dy}度分布的k條邊；

6) end for

7) 根據(jù)邊中介中心性系數(shù)平均值由小到大對(duì)2K序列重新排序；

邊中介中心性系數(shù)可以量化表示某一條邊在圖中的“重要性”，通過(guò)引入邊中介中心性系數(shù)，對(duì)2K序列重新排序，將“重要性”相同或相近的邊進(jìn)行聚類分組，在擾動(dòng)時(shí)能夠有效地保留原始圖的屬性與結(jié)構(gòu)特征，使加噪后的圖數(shù)據(jù)具有較好的研究意義。

3.3.3 分組差分隱私噪音添加

將排序后的2K序列R根據(jù)數(shù)據(jù)集大小劃分為n個(gè)子序列，第i個(gè)命名為Ri，i∈[1,n]。n的大小由數(shù)據(jù)集大小決定，若數(shù)據(jù)集較大，則選擇相對(duì)較大的n；若數(shù)據(jù)集較小，則選擇相對(duì)較小的n。依照下面2條規(guī)則對(duì)R序列進(jìn)行聚類。

1) 每個(gè)子序列只能獲取R序列中的連續(xù)元組。

2) 每個(gè)元組必須出現(xiàn)且僅可以出現(xiàn)在一個(gè)子序列中。

根據(jù)上述2條規(guī)則，可以獲得連續(xù)且相互不相交的子序列Ri。由定理3可知，這2條規(guī)則對(duì)于子序列敏感度性質(zhì)是非常重要的。

定理4子序列獨(dú)立性。對(duì)于排序后的2K序列R，當(dāng)i≠j時(shí)，R序列的任何子序列Ri與Rj的敏感度相互獨(dú)立。

證明該定理是基于以下假設(shè)利用反證法進(jìn)行證明的。假設(shè)Ri的敏感度受到發(fā)生在Rj中的變化的影響，i≠j。在不失一般性的前提下，假設(shè)i＜j，并且T(i′)是Ri中的元組，T(j′)是Rj中的元組。假設(shè)在節(jié)點(diǎn)v1和節(jié)點(diǎn)v2之間形成一條新邊，其中節(jié)點(diǎn)v1的相應(yīng)元組＜T(i),T(i+1),…＞∈Ri且節(jié)點(diǎn)v2的相應(yīng)元組＜T(j),T(j+1),…＞∈Rj。由于此事件可能發(fā)生的最大變化次數(shù)受v1和v2的度值的限制。令d1為v1的新度值，Ri中變化的元組的最大數(shù)目為d1-1個(gè)被刪除的元組和d1個(gè)添加的元組，即小于2d1。對(duì)稱地，令d2為v2的新度數(shù)，因此Rj中變化的元組的最大數(shù)目小于2d2。即使d1和d2等于它們的子序列中的最大度值dmax，如在定理3中規(guī)定的，每個(gè)子序列中涉及的變化的數(shù)目是2dmax＜4dmax+1，這意味著Ri和Rj的敏感度不會(huì)相互影響，與該假設(shè)相矛盾。

證畢。

利用dK擾動(dòng)算法，計(jì)算要注入2K序列的噪聲以滿足ε-差分隱私。dK擾動(dòng)算法是基于 Laplace分布 Lap(λ)中的隨機(jī)變量改變 2K序列的每個(gè)元組的噪音添加算法。

定義2設(shè)DK是對(duì)圖G生成的2K序列執(zhí)行差分隱私機(jī)制，使。對(duì)于至多相差一條邊的任何圖G和G′，如果滿足式(3)，則DK滿足ε-差分隱私。

其中，S2K為2K序列的Laplace機(jī)制敏感度，O為DK(G)可能的輸出，μ為2K序列的元組個(gè)數(shù)。

根據(jù)定理3，若直接對(duì)2K序列R添加噪聲，該噪聲為參數(shù)取值的Laplace分布，且μ值為整個(gè)2K序列R的元組個(gè)數(shù)。若如算法2所述，先對(duì) 2K序列進(jìn)行聚類分組，獲得連續(xù)且相互不相交的子序列Ri，則每個(gè)子序列的敏感度為再運(yùn)用定義 2對(duì)每個(gè)子序列Ri注入?yún)?shù)為的Laplace噪聲，這將大幅減小擾動(dòng)噪聲的添加量，理由如下。

設(shè)di為相應(yīng)子序列Ri中節(jié)點(diǎn)的最大度數(shù)，μi為相應(yīng)子序列Ri的元組個(gè)數(shù)，則該噪聲為參數(shù)且μi值為子序列Ri的元組個(gè)數(shù)。由于di≤dmax且μi≤μ，因此對(duì)噪聲添加量的縮減是指數(shù)級(jí)別的，這意味著在獲得相同隱私保護(hù)強(qiáng)度的情況下，聚類操作將很大程度上減小對(duì)原始圖結(jié)構(gòu)的擾動(dòng)。

隨后利用dK擾動(dòng)算法向每個(gè)子序列注入噪聲使每個(gè)子序列都滿足ε-差分隱私，再將加噪后的子序列整合為一個(gè)新的2K序列。下面將證明如果在每個(gè)劃分出的子序列上實(shí)現(xiàn)ε-差分隱私，在整合之后的2K序列上也將實(shí)現(xiàn)ε-差分隱私。

定理5子序列組合性質(zhì)。給定n個(gè)滿足ε-差分隱私的不同的Ri子序列，i∈[i,n]，它們合成的2K序列R也滿足ε-差分隱私。

證明對(duì)于n個(gè)滿足ε-差分隱私的子序列Ri。根據(jù)定理4，當(dāng)i≠j時(shí)，任何子序列Ri與Rj的敏感度相互獨(dú)立，即每個(gè)Ri引入噪聲量相互獨(dú)立。根據(jù)定理2，合成的2K序列R滿足ε-差分隱私。

證畢。

3.3.4 2K隨機(jī)圖生成算法

給定無(wú)向圖G=(V,E)，其節(jié)點(diǎn)數(shù)n=|V|，邊數(shù)m=|E|。設(shè)deg(v)為節(jié)點(diǎn)v的度數(shù)，Vk為度數(shù)為k的節(jié)點(diǎn)集合。

聯(lián)合度矩陣JDM定義為

此矩陣描述連接度為k的節(jié)點(diǎn)和度為l的節(jié)點(diǎn)之間的邊的數(shù)量，2K序列可以容易地由聯(lián)合度矩陣推導(dǎo)得出。根據(jù)同一個(gè)聯(lián)合度矩陣，2K序列可以構(gòu)造出不止一個(gè)在結(jié)構(gòu)和屬性上有略微差異的圖。

2K隨機(jī)圖生成算法如算法3所示。

算法32K隨機(jī)圖生成

輸入聯(lián)合度矩陣JDM′

輸出滿足JDM = JDM′的隨機(jī)圖

1) 創(chuàng)建|V|個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)擁有deg(v)個(gè)可用端口；

2) 對(duì)于所有(k,l)∈JDM′，令JDM (k,l) = 0；

3) for (k,l)∈JDM′(k,l)

4) while JDM (k,l)＜JDM′(k,l)

5) 任選不相連的 2個(gè)節(jié)點(diǎn)v∈Vk及w∈Vl；

6) ifv沒(méi)有可用端口

7) 調(diào)用算法4 NeighborSwitch(v)；

8) end if

9) ifw沒(méi)有可用端口

10) 調(diào)用算法4 NeighborSwitch(w)；

11) end if

12) JDM (k,l)++；JDM (l,k)++；

13) end while

14) end for

初始化過(guò)程中，創(chuàng)建|V|=n個(gè)節(jié)點(diǎn)，分別以它們的度數(shù)作為標(biāo)號(hào)。對(duì)每個(gè)節(jié)點(diǎn)v∈V，根據(jù)它們各自的度數(shù)分配 deg(v)個(gè)可用端口。初始狀態(tài)下全部節(jié)點(diǎn)都尚未連接，所以將JDM (k,l)中所有度數(shù)對(duì)(k,l)的值初始化為 0。隨后算法開始進(jìn)行迭代，在每次迭代中，選擇2個(gè)不相連的節(jié)點(diǎn)v和w，度數(shù)分別為k和l。當(dāng)JDM (k,l)沒(méi)有構(gòu)造完全時(shí)，將v的一個(gè)可用端口與w的一個(gè)可用端口連接起來(lái)以創(chuàng)建邊(v,w)，并且將相應(yīng)的2個(gè)項(xiàng)JDM (k,l)和JDM (l,k)的值增加1。直到當(dāng)前JDM的所有條目已經(jīng)達(dá)到其在JDM′(l,k)中的目標(biāo)值，2K圖構(gòu)造完成。

2K隨機(jī)圖生成算法的核心在于：當(dāng)JDM (deg(v),deg(w))尚未達(dá)到其目標(biāo)值時(shí)，即使不相連的2個(gè)節(jié)點(diǎn)v和w中的任一個(gè)或兩者都沒(méi)有可用端口時(shí)，也總是可以在它們之間添加一條邊。在添加邊(v,w)之前，對(duì)于沒(méi)有可用端口的每個(gè)節(jié)點(diǎn)，對(duì)邊執(zhí)行重新布線。這一操作被稱為“鄰節(jié)點(diǎn)轉(zhuǎn)換”。

將沒(méi)有可用端口的節(jié)點(diǎn)定義為飽和節(jié)點(diǎn)，將至少有一個(gè)可用端口的節(jié)點(diǎn)定義為不飽和節(jié)點(diǎn)。鄰節(jié)點(diǎn)轉(zhuǎn)換算法如下。

算法4鄰節(jié)點(diǎn)轉(zhuǎn)換算法（NeighborSwith）

輸入飽和節(jié)點(diǎn)i

輸出生成邊(i′,j)

1) 選擇不飽和節(jié)點(diǎn)i′；

2) if deg(i′) == deg(i)

3) 選擇與i相連且與i′不相連的節(jié)點(diǎn)j；

4) 刪除邊(i,j)；

5) 添加邊(i′,j)；

6) end if

對(duì)一個(gè)給定節(jié)點(diǎn)i進(jìn)行鄰節(jié)點(diǎn)轉(zhuǎn)換，可以在不改變當(dāng)前JDM的情況下為節(jié)點(diǎn)i釋放一個(gè)可用端口。由于deg(i′) == deg(i)，鄰接點(diǎn)轉(zhuǎn)換保證了JDM(deg(v),deg(w))的值不會(huì)改變。

4 實(shí)驗(yàn)仿真與性能分析

本節(jié)主要通過(guò)仿真實(shí)驗(yàn)來(lái)分析本文方案 BCPA的隱私保護(hù)性和數(shù)據(jù)可用性，并將其與同樣使用差分隱私機(jī)制的dK-PA方案和DRC方案進(jìn)行比較。其中，dK-PA模型是直接對(duì)2K序列進(jìn)行加噪處理，而另外2種模型都是基于2K序列排序聚類加噪算法。不同的是，DRC模型是基于節(jié)點(diǎn)度大小對(duì) 2K序列進(jìn)行排序，而BCPA是基于邊中介中心性系數(shù)進(jìn)行重新排序。

為了驗(yàn)證本文方案是否適用于社交網(wǎng)絡(luò)圖結(jié)構(gòu)，如表1所示，選取wiki-Vote和ego-Twitter這2個(gè)真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)集作為測(cè)試數(shù)據(jù)集，它們分別是維基百科who-votes-on-whom網(wǎng)絡(luò)數(shù)據(jù)和Twitter社交網(wǎng)絡(luò)數(shù)據(jù)。這2個(gè)數(shù)據(jù)集都具有以下2個(gè)顯著特征：1) 節(jié)點(diǎn)度的統(tǒng)計(jì)個(gè)數(shù)符合冪律分布；2) “小世界”的特征，更接近真實(shí)世界。

表1 測(cè)試數(shù)據(jù)集

4.1 隱私保護(hù)性評(píng)估

為了量化差分隱私保護(hù)算法對(duì)原始數(shù)據(jù)圖的具體擾動(dòng)，針對(duì)社交網(wǎng)絡(luò)圖結(jié)構(gòu)的特點(diǎn)，本文基于dK模型設(shè)計(jì)了一種基于鄰接度的隱私保護(hù)性衡量算法，具體如算法5所示。

算法5隱私保護(hù)性衡量算法

輸入原始圖G(V,E)，擾動(dòng)圖G′(V′,E′)

輸出隱私保護(hù)性P

1) 計(jì)算原始圖中的邊個(gè)數(shù)m，計(jì)算擾動(dòng)圖中的邊個(gè)數(shù)m′，Ddiff= 2mmax；

2) 對(duì)于節(jié)點(diǎn)u，u∈G，找出與u所連接的其他節(jié)點(diǎn)的度，降序排列并存儲(chǔ)在link(u)=(d1,d2, ... ,dn)，其中n表示節(jié)點(diǎn)u的度；

3) 反復(fù)執(zhí)行步驟2)和步驟3)，直至遍歷所有節(jié)點(diǎn)；

4) 對(duì)于節(jié)點(diǎn)u′，u′∈G′，找出與u′所連接的其他節(jié)點(diǎn)的度，降序排列并存儲(chǔ)在 link(u′)=(d1′,d2′, ... ,dn′′)，其中n′表示節(jié)點(diǎn)u′的度；

5) if id(u)==id(u′)

6) 找出 link(u)和 link(u′)相同的度關(guān)系，每找出一個(gè)，則Ddiff=Ddiff－1；

7) end if

8) 反復(fù)執(zhí)行步驟5)～步驟8)，直至遍歷所有節(jié)點(diǎn)；

9) 計(jì)算隱私保護(hù)性P；

分別生成原始圖相鄰節(jié)點(diǎn)度序列和擾動(dòng)圖相鄰節(jié)點(diǎn)度序列，比較2個(gè)序列，得到2個(gè)序列之間不相同的值的個(gè)數(shù)Ddiff，取原始圖的邊數(shù)量m和擾動(dòng)圖的邊數(shù)量m′。

2組數(shù)據(jù)中邊數(shù)量的最大值為

隱私保護(hù)性為

隱私保護(hù)性P的取值范圍為0～1，值越大，隱私保護(hù)程度越高。當(dāng)隱私保護(hù)性P較小時(shí)，表示鄰接節(jié)點(diǎn)的度改變較小，此時(shí)攻擊者仍然有很大概率實(shí)施結(jié)構(gòu)攻擊和度攻擊。

根據(jù)算法5，實(shí)驗(yàn)分別對(duì)BCPA、DRC和dK-PA這3種方案進(jìn)行了仿真，以達(dá)到比較3種算法的隱私保護(hù)效果，如圖2所示。

圖2 隱私保護(hù)性變化趨勢(shì)

由圖2可以看出，在不同ε值和不同大小的數(shù)據(jù)集中，相比于直接對(duì)2K序列進(jìn)行擾動(dòng)的dK-PA方案，聚類加噪的BCPA方案和DRC方案都表現(xiàn)出較優(yōu)異的隱私保護(hù)效果。這印證了本文中的理論分析，即聚類后加噪可以更有效地利用隱私預(yù)算以達(dá)到提高隱私保護(hù)強(qiáng)度的作用。BCPA方案和DRC方案在不同的ε值范圍下，隱私保護(hù)效果各有優(yōu)劣。無(wú)論是在體量較小的wiki-Vote網(wǎng)絡(luò)中，還是在體量較大的 ego-Twitter網(wǎng)絡(luò)中，在ε值較小的情況下(ε≤40)，即隱私保護(hù)強(qiáng)度較高時(shí)，BCPA方案表現(xiàn)更好；而當(dāng)ε值較大時(shí)(ε≥50)，隱私保護(hù)強(qiáng)度較弱，此時(shí) DRC方案的效果更勝一籌。這種結(jié)果差異性是排序算法不同造成的，2種排序算法基于不同的圖屬性重組2K序列，導(dǎo)致在根據(jù)加噪后的2K序列生成新圖時(shí)，新圖結(jié)構(gòu)的差異在隱私保護(hù)性衡量算法中反映出來(lái)。值得注意的是，當(dāng)ε值增加到一定值后(ε＞90)，3種方案的隱私保護(hù)效果差別較小，可見引入噪聲量較小時(shí)，3種方案的隱私保護(hù)性能差異不大。綜上，在隱私預(yù)算較小時(shí)，BCPA方案具有更高的隱私保護(hù)強(qiáng)度。

4.2 數(shù)據(jù)可用性評(píng)估

對(duì)于社交網(wǎng)絡(luò)圖數(shù)據(jù)而言，數(shù)據(jù)可用性分析主要是對(duì)社交網(wǎng)絡(luò)的結(jié)構(gòu)特征參數(shù)進(jìn)行分析。本實(shí)驗(yàn)通過(guò)將原始圖與擾動(dòng)圖的特征參數(shù)進(jìn)行比較分析，驗(yàn)證在不同的隱私預(yù)算下BCPA方案在數(shù)據(jù)可用性方面的優(yōu)勢(shì)。本實(shí)驗(yàn)選擇平均聚集系數(shù)、平均最短路徑和平均度分布這3個(gè)重要參數(shù)，用于衡量圖結(jié)構(gòu)特征。

由于2K序列非常敏感，其需要添加高水平的噪聲以提供高級(jí)別的隱私保護(hù)。然而，非常小的ε值需要引入非常大的噪聲值，雖然隱私強(qiáng)度很高，但會(huì)導(dǎo)致產(chǎn)生與原始圖結(jié)構(gòu)極不相似的合成圖。當(dāng)ε＜1時(shí)，對(duì)于較大的圖，所需的噪聲水平過(guò)高，以至dK圖生成器很難生成與所得到的dK分布匹配的合成圖。因此，為了取得較好的實(shí)驗(yàn)效果，本文分別生成ε=5、ε=10和ε=100的滿足ε-差分隱私的擾動(dòng)圖。

4.2.1 平均聚類系數(shù)

在社交網(wǎng)絡(luò)圖中，平均聚類系數(shù)的定義為其中，n為圖中節(jié)點(diǎn)總數(shù)，i為圖中某一節(jié)點(diǎn)，Ci為該節(jié)點(diǎn)的聚類系數(shù)。網(wǎng)絡(luò)的平均聚類系數(shù)可以很好地表示網(wǎng)絡(luò)中節(jié)點(diǎn)與其相鄰節(jié)點(diǎn)之間彼此連接的程度，即由3條邊連接三點(diǎn)形成的子圖三角形在當(dāng)前完整網(wǎng)絡(luò)中的密集程度。

由圖3可知，在ε值相同的情況下，BCPA方案生成圖的平均聚類系數(shù)與原始圖更相近，而加噪的差分隱私生成圖都呈現(xiàn)出同樣的趨勢(shì)：即當(dāng)ε值不斷減小時(shí)，生成圖的平均聚類系數(shù)逐漸增大。這是由于隱私保護(hù)需求的增大，引起更多的噪聲邊和噪聲節(jié)點(diǎn)的加入，三角形子圖密度增大，導(dǎo)致平均聚類系數(shù)值變大。

圖3 平均聚類系數(shù)柱狀圖

但即使是在ε=5的情況下，2個(gè)體量各異的真實(shí)社交網(wǎng)絡(luò)圖與BCPA方案生成圖之間的差異也沒(méi)有超過(guò)20%，因此，在保證較高隱私保護(hù)強(qiáng)度的情況下，BCPA較好地保留了原始圖屬性。

4.2.2 平均路徑長(zhǎng)度

由于真實(shí)社交網(wǎng)絡(luò)圖數(shù)據(jù)滿足“小世界”特征，即圖平均路徑長(zhǎng)度值為6左右。通過(guò)仿真實(shí)驗(yàn)比較wiki-Vote網(wǎng)絡(luò)和 ego-Twitter網(wǎng)絡(luò)的平均路徑長(zhǎng)度值與其滿足ε-差分隱私的擾動(dòng)生成圖的平均路徑長(zhǎng)度值，其結(jié)果如圖4所示。

圖4表明，2個(gè)真實(shí)社交網(wǎng)絡(luò)圖數(shù)據(jù)的平均路徑長(zhǎng)度均符合“小世界”特征，而其差分隱私生成圖隨著ε值的減小，平均路徑長(zhǎng)度也隨之變短。即，隨著ε值的減小，隱私保護(hù)需求不斷增大，所需引入的噪聲也隨之增多，添加了較大數(shù)量的擾動(dòng)邊，導(dǎo)致節(jié)點(diǎn)之間的連通路徑有了更多選擇。因此，平均路徑長(zhǎng)度隨著噪聲量的增大而不斷減小。

圖4 平均路徑長(zhǎng)度柱狀圖

由圖4可知，對(duì)于數(shù)據(jù)量不同的2個(gè)社交網(wǎng)絡(luò)圖數(shù)據(jù)，BCPA加噪生成圖的平均路徑長(zhǎng)度均更加接近于原始圖。因此，在給定隱私預(yù)算的情況下，BCPA能夠更好地保留原始圖的屬性，使擾動(dòng)數(shù)據(jù)具有更好的數(shù)據(jù)可用性。

4.2.3 節(jié)點(diǎn)度分布

節(jié)點(diǎn)度分布是對(duì)一個(gè)圖中節(jié)點(diǎn)度數(shù)的總體描述，對(duì)于本文方案所采用的2K隨機(jī)圖而言，節(jié)點(diǎn)度分布就是圖中頂點(diǎn)度數(shù)的概率分布。節(jié)點(diǎn)分布對(duì)比如圖5所示。

圖 5(c)和圖 5(f)表明，當(dāng)ε=100時(shí)，由于所引入的噪聲量較小，原始圖與BCPA和DRC的加噪生成圖的節(jié)點(diǎn)分布相差不大。而當(dāng)ε=5和ε=10時(shí)，wiki-Vote網(wǎng)絡(luò)和ego-twitter網(wǎng)絡(luò)的加噪生成圖都與原始圖結(jié)構(gòu)有較大差距。出現(xiàn)這種差異的原因是少數(shù)高度數(shù)節(jié)點(diǎn)連接大多數(shù)其他節(jié)點(diǎn)。因此，當(dāng)高度數(shù)節(jié)點(diǎn)引入了噪聲時(shí)，它會(huì)產(chǎn)生向圖的其余部分傳遞波動(dòng)的結(jié)構(gòu)變化?？梢姰?dāng)數(shù)據(jù)集所含節(jié)點(diǎn)數(shù)較多時(shí)，為實(shí)現(xiàn)較好的隱私保護(hù)效果，引入的大量噪聲顯著改變了圖結(jié)構(gòu)。

圖5 節(jié)點(diǎn)度分布對(duì)比

此外，由圖5可知，在節(jié)點(diǎn)度分布屬性上，BCPA和DRC的效果明顯優(yōu)于dK-PA，且DRC方案稍好于BCPA方案，但差距不明顯。這是由于DRC是根據(jù)節(jié)點(diǎn)度大小對(duì)2K序列進(jìn)行聚類分組，使加噪生成圖的節(jié)點(diǎn)度分布更接近原始圖。而BCPA是根據(jù)中介中心性系數(shù)對(duì)2K序列進(jìn)行聚類分組，在原始圖中“重要性”相同或相近的節(jié)點(diǎn)被聚類在同一子序列中，分組加噪時(shí)依然能保證不改變各節(jié)點(diǎn)的“重要性”。因此BCPA生成的差分隱私圖在平均路徑長(zhǎng)度和平均聚類系數(shù)這2項(xiàng)重要屬性上保留了更多的原始圖結(jié)構(gòu)特征。

5 結(jié)束語(yǔ)

本文針對(duì)基于差分隱私的社交網(wǎng)絡(luò)圖數(shù)據(jù)發(fā)布問(wèn)題，提出一種基于邊介數(shù)模型的差分隱私處理方案 BCPA，該方案結(jié)合dK模型對(duì)邊序列進(jìn)行聚類劃分，同時(shí)考慮到各邊在圖中的影響力程度，引入邊中介中心性系數(shù)來(lái)顯著減少2K序列敏感度。將BCPA方案與DRC和dK-PA方案進(jìn)行了實(shí)驗(yàn)仿真，通過(guò)對(duì)平均聚類系數(shù)、平均路徑長(zhǎng)度以及節(jié)點(diǎn)度分布等指標(biāo)的對(duì)比和分析，在較高隱私需求情況下，BCPA方案的隱私保護(hù)性和大部分?jǐn)?shù)據(jù)可用性都優(yōu)于DRC方案和dK-PA方案。下一步可進(jìn)行以下2個(gè)方面的工作：1) 在本文所提算法的基礎(chǔ)上，進(jìn)一步改進(jìn) 2K序列構(gòu)造算法而提升運(yùn)行效率；2) 在隱私需求較高的情況下，在引入噪聲量增大的同時(shí)，保證數(shù)據(jù)可用性維持在較高水準(zhǔn)。