基于不確定圖的隱私保護方法研究

胡 靜，史武超，顏 軍，吳振強

(陜西師范大學 計算機科學學院，陜西 西安 710119)

1 概 述

進入大數據時代，隨著移動互聯網的發展，人們在生活中可以隨時隨地產生數據，例如聊微信、轉發微博等。以微信為例，僅在2016年9月份，微信日登錄用戶達到了7.68億。由于社交網絡的發展與應用，越來越多的研究轉移到社交網絡，使得社交網絡分析成為諸多學科的研究熱點。然而，政府部門、商業機構對采集到的數據進行發布與共享時，會導致用戶個人隱私的泄露。因此，在發布數據的同時保護用戶的隱私信息就成了大數據環境下面臨的一個重大課題。

近年來，學者們在隱私保護方面做了大量的工作，而且取得了豐碩的成果。如Sweeney提出的k-匿名技術[1]，該技術要求發布數據對象個體在同一等價類中至少與其他k-1個對象不可區分，每個個體身份被識別出來的概率至多為1/k，從而降低了隱私泄露的風險。然而k-匿名技術不能抵抗同質性攻擊。為了解決這一問題，Machanavajjhala等[2]提出了l-多樣性，Li等[3]提出了t-緊密性等k-匿名技術的改進方法。但是這些方法難以定義攻擊者擁有的所有可能的背景知識，容易遭到背景知識攻擊且不能提供一種嚴格可證明的隱私保護程度。2006年Dwork提出的差分隱私技術解決了攻擊者可能的背景知識問題，并對隱私保護水平提供了量化評估方法[4]。

現有隱私保護方法主要適用于關系數據或者統計數據。在統計數據中，每個個體在統計上是相互獨立的；在關系數據中，關系隱私保護模型僅防范了將實體屬性值作為背景知識的隱私攻擊。然而，在社交網絡中，不僅要防止實體屬性值作為背景知識的攻擊，還要防止實體屬性值之間的關聯攻擊。因此，單純的關系數據或統計數據隱私保護方法不能滿足社交網絡中數據的隱私保護要求，需要提出與社交網絡數據特點相適應的隱私保護方法。在社交網絡中，網絡中個體間的關系、社交網絡結構、個體在結構中位置的重要性等均可作為攻擊者的背景知識進行隱私攻擊[5]。因此，社交網絡隱私保護一直是隱私保護研究的熱點領域。

社交網絡的隱私保護主要保護個體之間的關聯關系，因此將社交網絡抽象為網絡圖來進行研究。圖結構下的隱私保護算法可分為5種。

(1)頂點標識符替換方法。BackStrom等[6]提出在發布真實圖數據之前用合成標識符替換可識別屬性的匿名隱私保護方法，但容易受到背景知識的攻擊，攻擊者可以根據頂點結構特征推斷出頂點的身份信息。

(2)邊修改方法。該方法主要操作是隨機增減邊或交換邊，根據不同條件又分為無約束的邊修改和有約束的邊修改。前者如Hay等利用隨機添加/刪除邊策略提出隨機擾動方法來匿名圖[7]，Bonchi等[8]提出基于熵匿名等級量化及Sparsification方法；后者如Liu等[9]提出基于邊修改方法的k-度匿名，龔衛華等[10]提出保持網絡結構穩定的k-度匿名隱私保護模型。

(3)頂點和邊的聚類方法。該方法將圖中的頂點和邊經過泛化或聚類，變為超級頂點和超級邊，從而使某個頂點和邊的信息隱藏在這些超級頂點和超級邊中，如谷勇浩等[11]針對動態社交網絡數據發布提出一種基于聚類的動態圖發布算法；姜火文等[12]提出一種基于頂點連接結構和屬性值屬性圖聚類匿名化方法。

(4)頂點和邊的差分隱私方法。如Hay等[13]提出節點差分隱私和邊差分隱私的概念；文獻[14]綜述了社交網絡中的差分隱私以及差分隱私在社交網絡中的應用發展；蘭麗輝等[15]提出一種基于差分隱私的隨機擾動方法實現邊集邊權重的保護。

(5)邊的不確定性方法，即不確定圖方法。該方法通過對原始圖數據進行處理，將圖中所有邊出現的可能性變成[0，1]區間內的某個概率值，將確定的網絡圖以不確定圖的方式進行數據發布，從而保護了網絡圖中用戶的隱私信息。

將不確定圖引入隱私保護是近年來提出的新的圖結構數據隱私保護方法，該方法存在如下優勢：對個體間的關系進行了模糊化，將個體之間的確定關系變為不確定關系；相對于邊修改方法，保護了圖結構數據中實體之間的關系；沒有破壞數據的效用性，在保護隱私的基礎上不影響用戶進行數據挖掘的數據效用。

2012年Boldi等[16]提出給原始圖中的邊加入不確定性的方法，所提出的(k,ε)-混淆算法在抗頂點身份攻擊的同時也保證了圖結構數據的最小化失真；2013年Mittal等[17]提出了基于隨機游走的不確定圖數據發布方法，防止了鏈接攻擊；Nguyen等[18]在2014年提出基于方差最大化的方法來衡量隱私與效用之間的關系；2015年Nguyen等[19]在前期工作的基礎上又提出了基于不確定鄰接矩陣的通用匿名模型UAM，并將UAM引入到方差最大化算法中。綜上，文中主要研究已有的不確定圖隱私保護算法，通過對每種算法分析和對比，總結了每種算法的優缺點及各自的適用范圍，為隱私保護方法工程化實現提供技術參考[20]。

2 基礎知識

本節主要介紹不確定圖，(k,ε)-混淆，頂點唯一性和共性，隨機游走的轉移矩陣，不確定鄰接矩陣等概念。

定義1[16]：給定一個圖G(V,E)，如果映射p:V2→[0,1]是邊集中每條邊存在的概率函數，那么圖G'=(V,p)是關于圖G的不確定圖，其中V2表示集合V中所有可能的頂點對，即V2={(vi,vj)|1≤i

從定義1可知，確定圖G是不確定圖G'的一種特殊情況，確定圖G中的每條邊存在的概率均為1。

為了描述不確定圖，使用文獻[16]中的概率數據庫模型—可能世界模型(possible world model)，將生成的不確定圖G'的所有可能世界表示為W(G')，則對于某一不確定圖W=(V,EW)∈W(G')的概率為：

(1)

其中，E'為引入不確定性的頂點集合，E'?V2；p(e)為邊存在的概率，且不確定圖中不同的邊的概率分布是相互獨立的。

假定攻擊者知道某些頂點的屬性P，將屬性P的所有取值用ΩP表示。若屬性P是圖中所有頂點的度，則ΩP可以表示為：ΩP={0,1,…,n-1}。

給定一個不確定圖G'和某一個屬性P，對于每一個頂點v∈G'和ω∈ΩP，頂點v∈G且具有屬性P的概率Xv(ω)為：

(2)

對于式2，可以根據式1得到Pr(W)，而χv,ω(W)是一個[0,1]區間的變量，用來度量W中的頂點v是否具有屬性P。也就是說，Xv(ω)是所有可能世界模型中頂點v具有屬性P的概率之和。同時可以得到圖G中具有屬性值ω的頂點v在G'中像的概率Yω(v)為：

(3)

定義2[16]((k,ε)-混淆)：已知P是一個頂點屬性，k(k>1)是所需要達到的混淆級別，ε(0<ε<1)是一個容忍參數，如果G'中頂點的分布熵大于等于log2k，那么就說不確定圖G'是關于屬性P在頂點集合v屬于G上的k-混淆，即：H(YP(v))≥log2k。如果圖G'至少在混淆圖G中具有屬性P的(1-ε)n個頂點，那么就說不確定圖G'在屬性P中是(k,ε)-混淆的。

根據頂點在圖G所處位置及屬性的不同，文獻[17]給出了頂點唯一性和共性的定義，具體見定義3。

定義3[16]：已知P是定義在圖G頂點集合V上的一個屬性，P:V→ΩP，θ是一個大于0的參數，對于任意屬性值ω∈ΩP，則它的θ共性Cθ(ω)和θ唯一性Uθ(ω)為：

(4)

(5)

在定義3中，距離函數d為屬性P在ΩP范圍內的值。因此，對于每一對ω,ω'∈ΩP，總有d(ω,ω')>0。對于頂點度的屬性P1，距離函數d的值為P1中兩頂點度的差的絕對值。同時，Φ是高斯分布，見式6：

(6)

在該定義中頂點屬性值的ω的共性是指，ω值在圖中頂點屬性中是否具有代表性的一種測量，唯一性是共性的逆。共性與唯一性的大小取決于θ值的大小，θ越大，不確定性越大，屬性值的取值范圍ΩP越廣，頂點屬性的共性越小，則唯一性越大。

定義4[17]：隨機游走的轉移概率矩陣為：

(7)

其中，deg(i)表示頂點i的度。

定義5[19]不確定鄰接矩陣UAM(uncertain adjacency matrix)：給定原始圖G及其對應的不確定圖G'，如果矩陣A滿足以下三點，則稱A為不確定圖G'的鄰接矩陣。

(1)Ai,j=Aj,i；

(2)Ai,j∈[0,1]且Ai,i=0；

3 基于不確定圖的隱私保護算法

本節主要對(k,ε)-混淆算法、隨機游走算法、優化的隨機游走算法和基于UAM模型的方差最大化算法進行對比研究。首先從算法的執行流程圖、算法功能等角度進行分析，然后從保護程度、數據效用性和圖結構失真程度等方面進行了對比，最后總結了四種算法的優缺點及其各自的適用場景。

3.1 算法流程分析

3.1.1 (k,ε)-混淆算法

(k,ε)-混淆算法主要包括兩個部分，主算法(見圖1)和子算法(見圖2)。

圖1 (k,ε)-混淆算法流程

主算法的目的是找到符合條件的具有最小不確定性的(k,ε)-混淆圖；子算法是在給定的標準差參數，即不確定預算σ的情況下，找到原始數據圖G的(k,ε)-混淆圖G'。為了更好地利用不確定預算σ，需要對圖中的數據進行預處理，即選擇唯一性最大的「ε/2|V|?個頂點組成篩選集合H，H作為未加入不確定性頂點集合，因此，該算法不針對圖中所有頂點。

圖2中頂點唯一性的計算見定義3，頂點的唯一性值越大，該頂點中需要引入的不確定性越大，因此與唯一性大的頂點相鄰邊的采樣概率Q(v)就越大。根據采樣概率Q(v)，按比例縮小集合V中的頂點v的唯一性級別。對于子算法，對于E'中的每條邊e，根據邊的唯一性σ(e)重新分配不確定性級別。

圖2 子算法流程

對于E'中邊e=(u,v),它的σ-唯一性級別為：

(8)

σ-不確定性集合為：

(9)

對于大多數頂點對，邊隨機擾動參數re服從隨機分布Rσ(e)(見式10)；對于少數頂點對，邊隨機擾動參數re服從[0,1]均勻分布。

(10)

其中，Φ0,σ為高斯分布的密度函數，見式6。

3.1.2 隨機游走算法

隨機游走算法(RandWalk，RW)是通過對原始數據圖中添加噪音，將原始圖結構轉化為不確定性的圖結構，即通過隨機游走方法遍歷圖中的頂點和邊，刪除一些原始數據圖中真實存在的邊和添加某些不存在的邊。在RW算法中，為了避免頂點自環或者多條重復邊的出現，該算法設置了實驗次數的閾值M。RW的處理流程如圖3所示。

圖3 RW算法流程

RW算法保護了原始圖中的局部圖特征，防止了惡意攻擊者對網絡數據圖中某個子圖的鏈接攻擊。在真實數據庫中進行驗證時，該算法對原始數據不進行預處理。隨機游走次數t越小，社交網絡上的社團結構保護效果越好，并且與引入噪音的大小無關。

3.1.3 優化的隨機游走算法

由于RW算法中存在誤差實驗次數M值的設置，使得算法難以進行對比分析，Nguyen等對RW算法進行了優化，提出了RandWalk-mod算法(RW-mod)。RW-mod算法通過增加參數α來消除RW算法中的M參數，其中α是介于0和1之間的一個值。RW-mod執行流程如圖4所示。

3.1.4 方差最大化算法

基于定義5中的UAM矩陣，Nguyen等提出了方差最大化算法，該算法是高隱私保護算法RW和高數據可用性算法(k,ε)-混淆之間的一個均衡。方差最大化方法包括三個階段，該方法可闡述為：先將原始圖G分為s個子圖，每個子圖sG有ns=np/s條與附近頂點(頂點之間的默認距離為2)相連的邊數；在頂點的度不變的條件下，每個子圖sG形成一個有最大邊方差的不確定子圖sG'的二次規劃；最后將不確定子圖sG'合并成G'，并發布一些樣本圖。算法流程如圖5所示，在該算法中，可以利用二次規劃中的目標函數來計算原始數據圖的隱私保護程度。

3.2 算法比較

(1)(k,ε)-混淆算法利用頂點的唯一性和分布熵對圖中的頂點進行篩選，然后對篩選后的頂點進行邊混淆；RW算法和RW-mod算法利用馬爾可夫過程和轉移矩陣對原始圖進行邊的不確定化；方差最大化算法先利用圖分割技術將原始圖劃分為多個子圖，每個子圖對應一個二次規劃。

圖4 RW-mod算法流程

圖5 方差最大化算法流程

(2)(k,ε)-混淆算法的隱私保護程度最小；RW算法的隱私保護程度最大；RW-mod算法的隱私保護程度同RW算法；方差最大化算法的隱私保護程度介于(k,ε)-混淆算法和RW算法之間。

(3)通過(k,ε)-混淆算法，數據的可用性較高；通過RW算法，數據的可用性較差；RW-mod算法的數據可用性同RW算法；方差最大化算法數據可用性介于(k,ε)-混淆算法和RW算法之間。

(4)通過(k,ε)-混淆算法，圖結構失真較小；通過RW算法，保護了圖中的局部特征；RW-mod算法同RW算法；通過方差最大化算法，圖結構失真較大。

(5)(k,ε)-混淆算法中頂點的度保持不變；RW算法忽視了變換前后頂點度的關系；RW-mod算法中頂點的度保持不變；方差最大化算法中頂點的度保持不變。

(6)(k,ε)-混淆算法不允許自環；RW算法不允許自環，在構造不確定圖時造成了邊的丟失；RW-mod算法和方差最大化算法允許自環。

(7)(k,ε)-混淆算法和RW算法不允許兩頂點之間存在多條邊；RW-mod算法和方差最大化算法允許兩頂點之間存在多條邊。

(8)(k,ε)-混淆算法和RW算法符合定義5中的條件1和條件2；RW-mod算法在條件(1)中α=0.5時，符合定義5中的條件1和條件3；方差最大化算法符合定義5中的條件1～3。

(9)(k,ε)-混淆算法適合低隱私保護程度，高數據可用性的場景；RW算法和RW-mod算法適合高隱私保護程度，低數據可用性的場景；方差最大化算法適合高隱私保護程度，高數據可用性的場景。

在(k,ε)-混淆算法中，存在兩點不足之處：(1)σ最小化帶來的問題。σ越小，邊隨機擾動參數re大部分值集中在0附近，原始數據圖中真實存在的邊的概率1-re接近于1，不存在的邊的概率re接近于0，攻擊者可以根據舍入方法，將發布的不確定圖還原為原始數據圖；(2)該方法選擇頂點對，構造原始數據圖中不存在的邊時，沒有考慮到頂點的局部性，即頂點在子圖中所處的位置，好的子圖擾動可以減少圖結構的失真。RW算法是為了防止鏈接攻擊而提出的，是一種高隱私保護模型。但是RW算法中的試驗次數M及M值如何確定，使得算法難以進行比較分析。RW-mod算法不適合度為1的頂點，若頂點的度為1，則與該頂點相連的邊在原始數據圖上是真實存在的，在構造不確定圖時添加該條真實存在的邊的概率為1，而在RW-mod算法中，添加該邊的概率為0.5。方差最大化算法在子圖分割時造成了原始圖中邊的丟失，使得圖結構失真較大。

四種算法的比較見表1。

4 結束語

綜上所述，基于不確定圖的隱私保護方法在隱私保護中具有重要的使用價值。通過對(k,ε)-混淆算法、RW算法、RW-mod算法及方差最大化算法進行分析和比較，為基于不確定圖的隱私保護方法的改進和應用提供了技術支持。下一步重點研究將以上算法應用到有向圖或加權圖隱私保護中，同時引入新機制，如差分隱私，設計新的基于不確定圖的隱私保護方法。

表1 四種不確定圖實現算法的比較