差分隱私下的權重社交網絡隱私保護

徐 花，田有亮，3

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

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

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

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

(1) 構建非交互式查詢模型。對權重社交關系進行直方圖統計，設計滿足差分隱私的非交互式查詢模型，并設計低敏感度的隨機擾動算法，該查詢模型結果可重構權重社交網絡。

(2) 設計隨機擾動改進算法。引入社區結構熵對原始社交網絡的社交關系進行社區分組，以組為單位 注入隨機噪聲，減少噪聲量，從而提高待發布社交網絡的效用性。

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

1 預備知識

1.1 結構熵

針對復雜的圖形數據，基于香農熵定理的結構信息理論[15]，能夠利用一維結構熵、社區結構熵甚至高維結構熵檢測圖數據中隱藏的價值信息。

1.2 差分隱私

差分隱私[16-19]的實現需要引入噪聲機制，并具有嚴格的數學定義和推理。

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

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

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

2 權重社交網絡隱私保護模型和算法

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

2.1 非交互式社交網絡直方圖發布模型

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

圖1 非交互式社交網絡直方圖發布模型

在該模型中，具有的社交網絡差分隱私保護相關定義如定義6至定義8描述。

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

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

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

2.2 邊權重隨機擾動算法

基于非交互式直方圖查詢模型，文中提出WERD隱私保護算法，發布具有差分隱私保護的邊權重直方圖統計，實現社交網絡中用戶與用戶之間的關系隱私保護，WERD算法詳細描述如算法1。

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

算法1WERD算法。

輸入：原始社交網絡G(V，E，W)，隱私預算ε。

輸出：失真社交網絡邊權重向量W*。

① 按照節點序列排列邊關系，將邊權重映射為一個向量W，初始化W*=[]

② foriinW：

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

④ foriinW*：

⑤ ifwi*< 0：//邊權重一致性處理

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

⑦ returnW*。

(1)

結論2WERD算法滿足差分隱私。

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

(2)

2.3 邊權重分組隨機擾動算法

為減少擾動社交網絡的噪聲量，引入社區結構熵對社交網絡進行劃分[21]，在WERD算法的基礎上提出了隨機擾動改進算法，即WEGRD隱私保護算法。

首先通過社區結構熵將用戶節點劃分為單個社區，以社區為單位將各個社區的內部社交關系分別劃分為獨立的邊社區，而介于社區之間的邊關系組合成一個邊社區。然后根據社區大小分配相應的噪聲量，并從社區層面加入噪聲，從而減少噪聲量的引入。最后將擾動后的邊權重向量合成待發布社交網絡。WEGRD算法流程如圖2所示，算法詳細描述如算法2所示。

圖2 WEGRD算法流程圖

算法2WEGRD算法。

輸入：原始社交網絡G(V，E，W)，隱私預算ε。

輸出：失真社交網絡邊權重向量W*。

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

節點初始化為單個社區P={XC1，XC2，…，XCi，…，XCn}

② 設社區序列為P={XC1，XC2，…，XCi，…，XCl}

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

⑤ for遍歷P：//社交網絡邊關系總劃分為l+1組

以各社區為單位將邊關系劃分為社區內部邊關系(l組)和社區間邊關系(1組)

⑥ foriin range(l+1)：

for item in range(Vi)：

⑧ returnW*。

(3)

結論4WEGRD算法滿足差分隱私。

證明 同結論2。

3 分析與比較

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

3.1 隱私性度量

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

(4)

其中，Vi表示節點i的權重體積，v(G)表示社交網絡的體積，本質上與傳統信息理論中的香農熵相同，表征隱私信息源的隱私信息量也是隱私信息源的隱私不確定性，可以衡量隱私保護的程度。因此，利用社交網絡一維結構熵來反映圖結構中隱私數據的整體保護程度。

3.2 效用性度量

利用社交網絡的常用相關指標來度量算法的數據效用性，包括NE為圖邊的數量、AWD為圖平均加權度和ASPL為圖特征路徑長度。社交網絡效用LNE、AWD和ASPL的計算公式如下：

(5)

(6)

(7)

其中，dv表示節點v的度，|V|表示社交網絡的節點數，wij表示節點i和節點j之間的邊權重值，lij表示節點i和節點j的最短路徑長度。

3.3 隱私性分析

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

(a) Contact社交網絡

(b) Geometry 社交網絡

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

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

(a) Contact社交網絡

(b) Geometry 社交網絡

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

3.4 效用性分析

隨參數ε的取值變化對社交關系進行隱私保護的同時，利用NE、AWD和ASPL等衡量待發布社交網絡的效用程度，實驗結果如圖5和圖6所示。

(a) NE

(b) AWD

(c) ASPL

(a) NE

(b) AWD

(c) ASPL

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

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

4 結束語

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

進一步研究工作是考慮如何在動態更新的社交網絡下，優化算法降低誤差，發布和共享具有隱私保護的實時社交網絡。