徐 花，田有亮，3

(1.貴州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025；2.貴州省公共大數(shù)據(jù)重點實驗室，貴州 貴陽 550025；3.貴州大學(xué) 密碼學(xué)與數(shù)據(jù)安全研究所，貴州 貴陽 550025)

在互聯(lián)網(wǎng)技術(shù)日益成熟，社交網(wǎng)絡(luò)應(yīng)用平臺迅速普及的背景下，網(wǎng)絡(luò)用戶的個人隱私及社交關(guān)系隨數(shù)據(jù)發(fā)布和共享易遭受隱私泄露問題愈顯突出。如2018年社交平臺的泄露數(shù)據(jù)量占比56%，臉書和推特分別泄露22億條和3.36億條用戶數(shù)據(jù)的個人信息及用戶社交關(guān)系；黑客論壇出售LinkedIn用戶的個人資料，為證明數(shù)據(jù)真實，支付2美元便可查看其中200 000條記錄；此外，研究表明[1-5]，擁有一定背景知識的攻擊者對已發(fā)布的社交網(wǎng)絡(luò)數(shù)據(jù)進行分析，能以較高的概率精確識別用戶身份隱私和推測出用戶與用戶之間的社交關(guān)系隱私。惡意攻擊者掌握的用戶個人信息越多，則隱私泄露的風險越高。近年來，針對社交網(wǎng)絡(luò)中用戶的個人隱私，基于數(shù)據(jù)失真的社交網(wǎng)絡(luò)差分隱私保護方法受到了極大關(guān)注。因此，發(fā)布具有隱私保護的社交網(wǎng)絡(luò)數(shù)據(jù)的問題成為研究熱點。

目前，將社交網(wǎng)絡(luò)轉(zhuǎn)化為圖結(jié)構(gòu)研究的隱私保護方法可以分為4類：①k-匿名方法。ZOU等[6]提出采用k-自同構(gòu)方法，通過加邊將每個組內(nèi)的k個塊實現(xiàn)同構(gòu)，使原始社會網(wǎng)絡(luò)成為發(fā)布社交網(wǎng)絡(luò)的子圖，可抵御多種基于結(jié)構(gòu)查詢的攻擊；LI等[7]提出k-權(quán)重匿名通用模型對邊權(quán)重進行隱私保護，確保圖中的任意節(jié)點v至少存在其他k-1個節(jié)點與其有相同的權(quán)重屬性。② 圖聚類方法。BLONDEL等[8]利用模塊度作為衡量標準，將隱私用戶隱藏在模塊中以實現(xiàn)隱私保護；LIU等[9]利用結(jié)構(gòu)熵思想對原社交網(wǎng)絡(luò)加入最少的“非邊” 達到社區(qū)檢測欺騙，但該方法不能抵御節(jié)點的度攻擊。③ 圖結(jié)構(gòu)樹方法。XIAO等[10]提出一種層次隨機圖模型(Hierarchical Random Graph，HRG)表示原始社交網(wǎng)絡(luò)圖結(jié)構(gòu)，將HRG模型中的節(jié)點存儲為原始社交網(wǎng)絡(luò)圖節(jié)點之間的連接概率并添加隨機噪聲，該方法只適用于規(guī)模較小的社交網(wǎng)絡(luò)；NING等[11]針對邊權(quán)重和頻繁結(jié)構(gòu)隱私問題，將含噪聲的權(quán)重整合到生成圖中，同時在頻繁挖掘的過程中實現(xiàn)了圖結(jié)構(gòu)的隱私保護。④ 差分隱私方法。吳振強等[12]利用確定圖轉(zhuǎn)化為概率圖的方法，將圖中節(jié)點與節(jié)點之間的關(guān)系用概率表示，基于差分隱私的不確定圖導(dǎo)致較低的數(shù)據(jù)可用性；WANG等[13]針對社交網(wǎng)絡(luò)的邊權(quán)重隱私泄露問題，把邊權(quán)重序列當作一個無歸屬直方圖，利用差分隱私提出一種結(jié)合合并桶和一致性推理算法，缺點是待發(fā)布的社交網(wǎng)絡(luò)誤差較高；HUANG等[14]聯(lián)合聚類和隨機化算法提出PBCN(Privacy preserving approach Based on Clustering and Noise)方法，抵御社交網(wǎng)絡(luò)中的節(jié)點攻擊和度攻擊，損失了鄰接信息，并且其方法產(chǎn)生的誤差有噪聲誤差和圖重構(gòu)誤差。

可見，在上述失真社交網(wǎng)絡(luò)隱私方法中難以兼顧社交網(wǎng)絡(luò)的隱私性與效用性。為解決該問題，筆者基于差分隱私保護模型提出邊權(quán)重直方圖統(tǒng)計的非交互式查詢的數(shù)據(jù)發(fā)布方法。首先，將邊權(quán)重統(tǒng)計直方圖作為查詢結(jié)果，構(gòu)建非交互式查詢模型，該查詢結(jié)果可重構(gòu)權(quán)重社交網(wǎng)絡(luò)，基于該模型提出社交網(wǎng)絡(luò)邊權(quán)重隨機擾動(Weighted Edge Random Disturbance，WERD)算法，實現(xiàn)滿足邊關(guān)系差分隱私保護的直方圖統(tǒng)計發(fā)布。其次，為減少WERD算法引入的噪聲量，提出了改進算法，即邊權(quán)重分組隨機擾動(Weighted Edge Grouping Random Disturbance，WEGRD)算法。該算法首先利用社區(qū)結(jié)構(gòu)熵對社交網(wǎng)絡(luò)的邊關(guān)系進行劃分，通過從社區(qū)層面分配并注入噪聲，實現(xiàn)從社區(qū)層面保護社交關(guān)系，減少社交網(wǎng)絡(luò)的效用誤差。最后，實驗分析表明，筆者提出的算法能夠?qū)崿F(xiàn)大范圍計數(shù)查詢的同時保證數(shù)據(jù)可用性，且適用于大型社交網(wǎng)絡(luò)。主要貢獻如下：

(1) 構(gòu)建非交互式查詢模型。對權(quán)重社交關(guān)系進行直方圖統(tǒng)計，設(shè)計滿足差分隱私的非交互式查詢模型，并設(shè)計低敏感度的隨機擾動算法，該查詢模型結(jié)果可重構(gòu)權(quán)重社交網(wǎng)絡(luò)。

(2) 設(shè)計隨機擾動改進算法。引入社區(qū)結(jié)構(gòu)熵對原始社交網(wǎng)絡(luò)的社交關(guān)系進行社區(qū)分組，以組為單位 注入隨機噪聲，減少噪聲量，從而提高待發(fā)布社交網(wǎng)絡(luò)的效用性。

(3) 在真實社交網(wǎng)絡(luò)上檢驗和分析文中算法。理論分析算法的差分隱私性和邊權(quán)重誤差程度，并利用一維結(jié)構(gòu)熵進行隱私性度量和社交網(wǎng)絡(luò)中的常用效用指標進行實驗與比較。

1 預(yù)備知識

1.1 結(jié)構(gòu)熵

針對復(fù)雜的圖形數(shù)據(jù)，基于香農(nóng)熵定理的結(jié)構(gòu)信息理論[15]，能夠利用一維結(jié)構(gòu)熵、社區(qū)結(jié)構(gòu)熵甚至高維結(jié)構(gòu)熵檢測圖數(shù)據(jù)中隱藏的價值信息。

1.2 差分隱私

差分隱私[16-19]的實現(xiàn)需要引入噪聲機制，并具有嚴格的數(shù)學(xué)定義和推理。

定義3查詢函數(shù)f。f為發(fā)布數(shù)據(jù)集提供的查詢函數(shù)f(D)：D→Rd，其中，Rd表示查詢輸出結(jié)果，d表示輸出結(jié)果維度。

定義4全局敏感度。對于一個數(shù)據(jù)集提供的查詢函數(shù)f和查詢結(jié)果，全局敏感度為在任意僅相差一條記錄相鄰數(shù)據(jù)集D和D′對查詢結(jié)果產(chǎn)生的最大影響，記Δf=maxD，D′‖f(D)-f(D′)‖1。

性質(zhì)2并行組合性。給定數(shù)據(jù)集D與差分隱私算法M1，M2，…，Mn，對于互不相交的數(shù)據(jù)子集D1，D2，…，Dn，即任意Di∩Dj=?(i≠j)，對應(yīng)隱私保護預(yù)算為ε1，ε2，…，εn，算法組合M(M1(D1)，M2(D2)，…，Mn(Dn))提供ε=max (εi)的差分隱私保護。

2 權(quán)重社交網(wǎng)絡(luò)隱私保護模型和算法

本節(jié)主要介紹針對權(quán)重社交網(wǎng)絡(luò)的非交互式直方圖發(fā)布模型和差分隱私保護算法。非交互式隱私發(fā)布模型，即通過預(yù)先添加噪聲獲得含噪數(shù)據(jù)，對用戶的數(shù)據(jù)查詢直接返回加噪結(jié)果。直方圖統(tǒng)計發(fā)布通常支持聚集查詢、范圍計數(shù)查詢以及數(shù)據(jù)挖掘等應(yīng)用[20]。直方圖的真實計數(shù)會泄露社交關(guān)系隱私，因此發(fā)布直方圖前需進行脫敏處理。針對權(quán)重社交網(wǎng)絡(luò)隱私發(fā)布，基于差分隱私保護模型構(gòu)建非交互式社交網(wǎng)絡(luò)發(fā)布模型，將邊權(quán)重統(tǒng)計直方圖作為向外部數(shù)據(jù)查詢者提供的查詢返回結(jié)果。在非交互式發(fā)布框架下，基于差分隱私的非交互式查詢支持批量查詢，會加入大量噪聲以混淆真實信息。而基于非交互式直方圖發(fā)布模型設(shè)計差分隱私保護算法，即WERD算法和WEGRD算法，將減少噪聲量的注入，并使待發(fā)布社交網(wǎng)絡(luò)數(shù)據(jù)滿足差分隱私。

2.1 非交互式社交網(wǎng)絡(luò)直方圖發(fā)布模型

針對權(quán)重社交關(guān)系的隱私保護問題，利用G(V，E，W)表示權(quán)重社交網(wǎng)絡(luò)，基于非交互式差分隱私保護模型和統(tǒng)計直方圖發(fā)布方法構(gòu)建社交網(wǎng)絡(luò)直方圖發(fā)布模型。該模型根據(jù)社交網(wǎng)絡(luò)完全圖序號向外部提供的查詢函數(shù)f且敏感度Δf=2，設(shè)計低敏感度的隨機擾動算法生成發(fā)布社交網(wǎng)絡(luò)數(shù)據(jù)集，對權(quán)重社交關(guān)系進行直方圖統(tǒng)計并發(fā)布，從而保留更高的社交網(wǎng)絡(luò)數(shù)據(jù)效用。查詢結(jié)果為社交關(guān)系的權(quán)重分布，即邊關(guān)系直方圖，在無隱和保護下，對該查詢模型連續(xù)查詢社交用戶數(shù)|V|的完全圖次，則查詢結(jié)果能重構(gòu)社交網(wǎng)絡(luò)。社交網(wǎng)絡(luò)直方圖發(fā)布模型下的社交網(wǎng)絡(luò)數(shù)據(jù)不僅滿足差分隱私且保留了社交關(guān)系的權(quán)重分布特征，這為社交網(wǎng)絡(luò)數(shù)據(jù)隱私保護數(shù)據(jù)發(fā)布提供了一種方法。非交互式社交網(wǎng)絡(luò)直方圖發(fā)布模型如圖1所示。

圖1 非交互式社交網(wǎng)絡(luò)直方圖發(fā)布模型

在該模型中，具有的社交網(wǎng)絡(luò)差分隱私保護相關(guān)定義如定義6至定義8描述。

定義6社交網(wǎng)絡(luò)差分隱私。在社交網(wǎng)絡(luò)中，假設(shè)節(jié)點數(shù)相同，邊至多相差一條記錄為相鄰數(shù)據(jù)集D和D′，即E=E′±1，記為|DΔD′|=1。M為一隨機化算法，Range(M)表示算法M的所有可能的輸出構(gòu)成的集合，S∈Range(M)。對于相應(yīng)的查詢函數(shù)f，算法M的輸出結(jié)果滿足：Pr(M[D]∈S]≤eεPr(M[D′]∈S]，則該算法滿足ε差分隱私(ε-Differential Privacy)。

定義7模型查詢函數(shù)f。社交網(wǎng)絡(luò)直方圖發(fā)布模型提供的查詢函數(shù)f(|V|)：G→R|W|-1，即返回結(jié)果為社交網(wǎng)絡(luò)各三元組(vi，vj，wi，j)中wi，j分量計數(shù)統(tǒng)計的實數(shù)向量，其中，|V|為社交網(wǎng)絡(luò)完全圖序號，維度d=|W|-1，|W|為邊權(quán)重取值個數(shù)。

定義8敏感度Δf。對僅相差一條權(quán)重社交關(guān)系的相鄰數(shù)據(jù)集，對f返回結(jié)果的影響最大值。該模型下的查詢函數(shù)最大敏感度為2，即相差一條邊權(quán)重最多改變直方圖的兩個桶值，則變化量Δf=2≤ΔW=WmaxWmin。

2.2 邊權(quán)重隨機擾動算法

基于非交互式直方圖查詢模型，文中提出WERD隱私保護算法，發(fā)布具有差分隱私保護的邊權(quán)重直方圖統(tǒng)計，實現(xiàn)社交網(wǎng)絡(luò)中用戶與用戶之間的關(guān)系隱私保護，WERD算法詳細描述如算法1。

WERD算法首先按照社交網(wǎng)絡(luò)用戶節(jié)點序列對邊關(guān)系進行正序排序，將邊關(guān)系的權(quán)重分量映射為一個向量W。然后利用敏感度為2的Laplace隨機噪聲擾動每條邊關(guān)系權(quán)重值，對小于0的權(quán)重值進行一致性后處理。最后將擾動后的邊權(quán)重向量合成待發(fā)布社交網(wǎng)絡(luò)。將噪聲大小由查詢函數(shù)敏感度Δf和隱私參數(shù)ε決定，為估計和量化Laplace噪聲帶來的誤差，對含噪聲的社交網(wǎng)絡(luò)進行均方誤差分析，并證明該算法是否滿足差分隱私。

算法1WERD算法。

輸入：原始社交網(wǎng)絡(luò)G(V，E，W)，隱私預(yù)算ε。

輸出：失真社交網(wǎng)絡(luò)邊權(quán)重向量W*。

① 按照節(jié)點序列排列邊關(guān)系，將邊權(quán)重映射為一個向量W，初始化W*=[]

② foriinW：

③wi*←wi+lap(2/ε)

④ foriinW*：

⑤ ifwi*< 0：//邊權(quán)重一致性處理

⑥wi*←wi*-min(W*)+1

⑦ returnW*。

(1)

結(jié)論2WERD算法滿足差分隱私。

證明 在非交互式隱私發(fā)布模型中，根據(jù)向外提供的查詢函數(shù)f向原始數(shù)據(jù)集預(yù)先添加Laplace噪聲獲得含噪的社交網(wǎng)絡(luò)數(shù)據(jù)。設(shè)有S∈range(f(G))，WERD算法輸出長度為L=|ΔW|-1的一維向量，設(shè)L={L1，L2，…，LΔw}，則差分隱私的定義計算可表示為

(2)

2.3 邊權(quán)重分組隨機擾動算法

為減少擾動社交網(wǎng)絡(luò)的噪聲量，引入社區(qū)結(jié)構(gòu)熵對社交網(wǎng)絡(luò)進行劃分[21]，在WERD算法的基礎(chǔ)上提出了隨機擾動改進算法，即WEGRD隱私保護算法。

首先通過社區(qū)結(jié)構(gòu)熵將用戶節(jié)點劃分為單個社區(qū)，以社區(qū)為單位將各個社區(qū)的內(nèi)部社交關(guān)系分別劃分為獨立的邊社區(qū)，而介于社區(qū)之間的邊關(guān)系組合成一個邊社區(qū)。然后根據(jù)社區(qū)大小分配相應(yīng)的噪聲量，并從社區(qū)層面加入噪聲，從而減少噪聲量的引入。最后將擾動后的邊權(quán)重向量合成待發(fā)布社交網(wǎng)絡(luò)。WEGRD算法流程如圖2所示，算法詳細描述如算法2所示。

圖2 WEGRD算法流程圖

算法2WEGRD算法。

輸入：原始社交網(wǎng)絡(luò)G(V，E，W)，隱私預(yù)算ε。

輸出：失真社交網(wǎng)絡(luò)邊權(quán)重向量W*。

① 初始化隱私預(yù)算ε，將G(V，E，W)邊權(quán)重映射為一個向量W，W*=[]，將

節(jié)點初始化為單個社區(qū)P={XC1，XC2，…，XCi，…，XCn}

② 設(shè)社區(qū)序列為P={XC1，XC2，…，XCi，…，XCl}

更新P={XC1，XC2，…，XCi，…，XCl-1，X}

⑤ for遍歷P：//社交網(wǎng)絡(luò)邊關(guān)系總劃分為l+1組

以各社區(qū)為單位將邊關(guān)系劃分為社區(qū)內(nèi)部邊關(guān)系(l組)和社區(qū)間邊關(guān)系(1組)

⑥ foriin range(l+1)：

for item in range(Vi)：

⑧ returnW*。

(3)

結(jié)論4WEGRD算法滿足差分隱私。

證明 同結(jié)論2。

3 分析與比較

為了對提出算法的隱私性和效用性進行驗證及度量，筆者利用權(quán)重社交網(wǎng)絡(luò)中一維結(jié)構(gòu)熵[22]衡量待發(fā)布社交網(wǎng)絡(luò)數(shù)據(jù)對原始社交網(wǎng)絡(luò)的隱私保護程度，利用社交網(wǎng)絡(luò)圖統(tǒng)計指標來度量算法的數(shù)據(jù)效用程度。文中的實驗數(shù)據(jù)來源自公開發(fā)布的真實社交網(wǎng)絡(luò)數(shù)據(jù)集和Pajek復(fù)雜網(wǎng)絡(luò)分析工具公開發(fā)布的無向有權(quán)網(wǎng)絡(luò)數(shù)據(jù)集，權(quán)重社交網(wǎng)絡(luò)分別有Contact (120個節(jié)點，348條邊，邊權(quán)重取值范圍0～4)和Geometry (6 158個節(jié)點，11 898條邊，邊權(quán)重取值范圍0～77)，均為簡單無向有權(quán)社交網(wǎng)絡(luò)數(shù)據(jù)集。

3.1 隱私性度量

在一般的差分隱私框架下，隱私預(yù)算能夠證明隱私保護程度，但對于復(fù)雜的社交網(wǎng)絡(luò)數(shù)據(jù)，隱私預(yù)算不能嚴格證明社交隱私保護的強度。在結(jié)構(gòu)信息理論中，一維結(jié)構(gòu)熵和社區(qū)結(jié)構(gòu)熵只是表達圖G的不同分區(qū)狀態(tài)，故可作為社區(qū)劃分好壞程度的評判標準。而在這一部分中，筆者建立了任意給定圖的一維結(jié)構(gòu)信息，H1(G)的計算公式為

(4)

其中，Vi表示節(jié)點i的權(quán)重體積，v(G)表示社交網(wǎng)絡(luò)的體積，本質(zhì)上與傳統(tǒng)信息理論中的香農(nóng)熵相同，表征隱私信息源的隱私信息量也是隱私信息源的隱私不確定性，可以衡量隱私保護的程度。因此，利用社交網(wǎng)絡(luò)一維結(jié)構(gòu)熵來反映圖結(jié)構(gòu)中隱私數(shù)據(jù)的整體保護程度。

3.2 效用性度量

利用社交網(wǎng)絡(luò)的常用相關(guān)指標來度量算法的數(shù)據(jù)效用性，包括NE為圖邊的數(shù)量、AWD為圖平均加權(quán)度和ASPL為圖特征路徑長度。社交網(wǎng)絡(luò)效用LNE、AWD和ASPL的計算公式如下：

(5)

(6)

(7)

其中，dv表示節(jié)點v的度，|V|表示社交網(wǎng)絡(luò)的節(jié)點數(shù)，wij表示節(jié)點i和節(jié)點j之間的邊權(quán)重值，lij表示節(jié)點i和節(jié)點j的最短路徑長度。

3.3 隱私性分析

衡量算法的隱私性為社交網(wǎng)絡(luò)一維結(jié)構(gòu)熵，此外，對社交網(wǎng)絡(luò)中圖結(jié)構(gòu)信息攻擊和節(jié)點度識別攻擊進行隱私性分析。由于筆者提出的WERD算法和WEGRD改進算法均只需隱私預(yù)算ε參數(shù)，取值范圍ε=[0.8，1.4，2.0，2.6，3.2]。基于權(quán)重社交網(wǎng)絡(luò)Contact和 Geometry，對筆者提出算法展開實驗，通過權(quán)重社交網(wǎng)絡(luò)一維結(jié)構(gòu)熵衡量算法的隱私保護效果，實驗結(jié)果如圖3所示。

(a) Contact社交網(wǎng)絡(luò)

(b) Geometry 社交網(wǎng)絡(luò)

圖3(a)和圖3(b)為筆者提出的算法分別對權(quán)重社交網(wǎng)絡(luò)Contact和Geometry隨隱私參數(shù)ε變化的一維結(jié)構(gòu)熵量化結(jié)果。由于兩種算法均為基于差分隱私模型設(shè)計的隱私保護算法，針對不同社交網(wǎng)絡(luò)規(guī)模，WERD算法的一維結(jié)構(gòu)熵值均高于WEGRD改進算法，是因為WERD算法對所有的邊關(guān)系進行噪聲擾動，從而不確定性增加。在Geometry社交網(wǎng)絡(luò)中，算法隨ε值的增大而隱私保護程度H1(G)差異則逐漸減小。

社交網(wǎng)絡(luò)圖結(jié)構(gòu)攻擊是指攻擊者試圖從失真社交網(wǎng)絡(luò)根據(jù)目標節(jié)點構(gòu)造一個特殊的子圖，以確定目標節(jié)點在真實社交網(wǎng)絡(luò)的結(jié)構(gòu)信息。WERD算法和WEGRD改進算法均對社交用戶與用戶之間的連接關(guān)系進行擾動，混淆了原有的用戶信息及社交信息。由于社交網(wǎng)絡(luò)復(fù)雜性，惡意攻擊者若構(gòu)造具有少量邊信息的特殊子圖，則無法從已發(fā)布的社交網(wǎng)絡(luò)數(shù)據(jù)圖中識別出目標節(jié)點。而對于節(jié)點度識別攻擊，即使攻擊者已知目標節(jié)點的度數(shù)，也不能獲得目標節(jié)點的真實信息。對文中提出算法與已有權(quán)重社交網(wǎng)絡(luò)隱私保護算法的節(jié)點度識別保護程度進行比較，選取的對比算法為MB_CI算法[13]。對Contact和Geometry社交網(wǎng)絡(luò)的節(jié)點度識別保護程度對比結(jié)果如圖4所示。

(a) Contact社交網(wǎng)絡(luò)

(b) Geometry 社交網(wǎng)絡(luò)

MB_CI算法的參數(shù)有分組參數(shù)k和隱私預(yù)算ε，筆者只考慮同等隱私預(yù)算下的保護概率。因此，對比算法為分析k=5時Contact社交網(wǎng)絡(luò)和k=10時Geometry社交網(wǎng)絡(luò)在不同隱私預(yù)算下，對社交網(wǎng)絡(luò)節(jié)點進行節(jié)點度識別保護的影響。如圖4(a)和圖4(b)所示，由于攻擊者進行節(jié)點識別攻擊是通過查詢結(jié)果，來獲取與目標對象相匹配的候選集的，故而匹配集越大，識別概率越小。在Contact社交網(wǎng)絡(luò)中，文中算法的節(jié)點度識別保護程度均略高于CB_CI算法，而在Geometry社交網(wǎng)絡(luò)中，WEGRD改進算法保護程度最高，因為將社交網(wǎng)絡(luò)中節(jié)點度相似的節(jié)點盡可能地劃分為同一個社區(qū)進行擾動，從而匹配概率更低。

3.4 效用性分析

隨參數(shù)ε的取值變化對社交關(guān)系進行隱私保護的同時，利用NE、AWD和ASPL等衡量待發(fā)布社交網(wǎng)絡(luò)的效用程度，實驗結(jié)果如圖5和圖6所示。

(a) NE

(b) AWD

(c) ASPL

(a) NE

(b) AWD

(c) ASPL

由圖5(a)和圖6(a)可見，隨ε增加，WEGRD算法的邊數(shù)NE均小于WERD算法的且變化較平緩，這是因為WEGRD算法引入了社區(qū)結(jié)構(gòu)熵進行社區(qū)分組，在分組的過程中，將聯(lián)系密切的邊關(guān)系劃分為一組，且注入的噪聲量低于WERD算法的；如圖5(b)所示，WEGRD算法平均加權(quán)度AWD效用低于WERD算法的，但圖6(b)中兩者算法的AWD效用相差不大；圖5(c)和圖6(c)隨ε的增加WEGRD算法針對社交網(wǎng)絡(luò)的ASPL效用均優(yōu)于WERD算法的。在不同規(guī)模的社交網(wǎng)絡(luò)中，由于數(shù)據(jù)的隱私性與效用之間的對立性和噪聲的隨機性，比較可得，WEGRD改進算法的數(shù)據(jù)效用保留程度較穩(wěn)定。

綜上，針對Contact和Geometry權(quán)重社交網(wǎng)絡(luò)隨ε值變化的數(shù)據(jù)效用性比較可得，筆者提出的WERD算法和WEGRD算法的待發(fā)布社交網(wǎng)絡(luò)，隱私性都較高且保留了較高的數(shù)據(jù)效用。由于噪聲的隨機性，針對不同數(shù)據(jù)效用的保留情況，可根據(jù)需求選擇相對應(yīng)的隱私保護算法，筆者提出的算法均能保證發(fā)布具有可接受的數(shù)據(jù)效用。由于AWD效用度量評估與邊權(quán)重取值有關(guān)，當權(quán)重分布范圍較大時可選擇WEGRD算法，如在Geometry社交網(wǎng)絡(luò)中保留了較為穩(wěn)定的數(shù)據(jù)效用；但在取值范圍較小的社交網(wǎng)絡(luò)中，需要達到高AWD效用，則選擇WERD算法。當需求為高ASPL數(shù)據(jù)效用時，則可選擇WEGRD隱私保護算法，因為WEGRD算法能夠保留更多原始社交網(wǎng)絡(luò)中存在的最短特征路徑。

4 結(jié)束語

基于差分隱私保護模型，筆者提出非交互式邊權(quán)重直方圖發(fā)布查詢模型和兩種社交網(wǎng)絡(luò)隨機擾動算法。查詢模型是將權(quán)重序列進行噪聲擾動后生成失真社交網(wǎng)絡(luò)數(shù)據(jù)集，將直方圖統(tǒng)計作為查詢結(jié)果；該直方圖可重構(gòu)權(quán)重社交網(wǎng)絡(luò)，且能保證權(quán)重社交關(guān)系的隱私。筆者提出的社交網(wǎng)絡(luò)隨機擾動算法WERD和WEGRD算法，能夠避免大范圍計數(shù)查詢時的噪聲過度累加，而導(dǎo)致的數(shù)據(jù)可用性降低問題，能保證社交差分隱私的同時，保證更高的數(shù)據(jù)可用性。該算法的不足之處是誤差仍較高。

進一步研究工作是考慮如何在動態(tài)更新的社交網(wǎng)絡(luò)下，優(yōu)化算法降低誤差，發(fā)布和共享具有隱私保護的實時社交網(wǎng)絡(luò)。