圖數據連續發布中的隱私保護方法

朱黎明，丁曉波，龔國強

（1.三峽大學 計算機與信息學院，湖北 宜昌 443002；2.湖北省建筑質量檢測裝備工程技術研究中心，湖北 宜昌 443000）

0 概述

現有許多基于k 度匿名的社交網絡匿名模型都假設網絡結構不變，僅考慮網絡結構的一次性匿名發布。但是，真實社交網絡圖是不斷變化的，攻擊者很有可能根據社交網絡圖前后的變化進行關聯攻擊，此外，若每次對待發布數據重新進行一次匿名處理，將降低動態社交網絡數據匿名的靈活性，因此，考慮社交網絡發布數據的動態性十分有必要，研究人員在動態社區發現［1］、動態社交網絡節點影響力［2］、動態社交網絡表示學習［3］等領域，都需要對動態社交網絡進行深入分析，而隱私保護問題與人們的日常生活密切相關，研究動態社交網絡的隱私保護問題和隱私保護方法尤為重要。

針對單一社交網絡隱私保護問題，LIU 等［4］提出一種k 度匿名保護方案，其通過構造k 度向量來進行圖重構，以防止節點度數攻擊，但是，該圖重構技術極大地破壞了原圖中所有的節點關聯關系，帶來了很大的結構信息損失。TAI 等［5］提出了k2匿名方法，該方法通過構造k 個具有相同度序列的鄰居來防止依據好友身份進行的關聯攻擊。HAY 等［6］提出了k-candidate 匿名模型，用于防止頂點度數識別攻擊，并提出了基于聚類的匿名保護方案。ZΟU［7］和CHENG 等［8］通過研究社交圖的子圖結構，以對子圖分別進行k 同構和自同構構造，它們的不足之處在于需要同構判斷以及重構時的代價非常巨大。龔衛華等［9］根據k 度匿名提出SimilarGraph 模型，該模型先對度序列進行簇劃分，然后通過邊修改操作進行圖重構，其操作與k 度匿名模型類似。MITTAL 等［10］提出基于隨機游走的匿名技術以保護邊鏈接隱私，用戶i和j之間的一條邊被用戶i和u之間的邊替代，其中，用戶u是用戶j隨機游走到達的目的地。王路寧等［11］提出基于鏈路預測的方法，以對動態數據進行聚類泛化保護。MA 等［12］提出KDVEM 模型，其通過計算最小匿名代價，先對原圖進行邊修改操作，然后針對無法通過邊修改操作達到k 匿名性要求的節點，創建虛擬節點并與該節點建立邊，從而實現原始圖中所有節點的k 度匿名。周克濤等［13］提出了改進的基于鄰居度序列相似度的k 度匿名保護方法，其能抵抗基于鄰居度序列的背景知識攻擊。CHESTER［14］提出基于虛擬節點的k 度匿名方法，其通過添加虛擬節點使得任意節點滿足k 度匿名，并給出所添加節點數量的最小值以及為節點添加的最少下界，通過添加最少的下界使得原圖滿足k 度匿名性，再對新添節點進行k 度匿名。CASAS-RΟMA等［15］為了適應大型社交網絡的k 匿名化，提出單變量微聚合k 級匿名算法，該算法通過邊緣相關性測度保留重要的邊，減少了信息損失。CHEN 等［16］在k 度匿名的基礎上進行改進，通過最小的邊編輯方法給出所有圖修改操作，使得匿名圖盡可能與原圖相似。谷勇浩等［17］針對社交網絡動態變化的特性，提出基于聚類的動態社交網絡隱私保護方法，該方法通過計算聚類間的距離，將變化后的節點重新分配到聚類集合中，然后對變化的節點進行匿名處理。

董祥祥等［18］針對社交網絡動態變化的更新問題，提出動態社交網絡發布的匿名數據方法，其通過匿名更新已經匿名的數據，保證前后匿名圖具有相似的圖結構，但是，該方法并未考慮前后匿名圖存在的隱私泄露風險。金葉等［19］考慮網絡中社區結構屬性所帶來的隱私泄露風險，將節點分為邊緣節點和一般節點，然后對其進行匿名，從而保護度結構和社區結構。KIABΟD 等［20］考慮每次構造k 度向量會浪費很多時間，其通過構造k 度向量樹來保證在需要得到不同k 值時可以從k 度向量樹上直接得到k 度向量，從而大幅節省重新獲取k 度向量的時間。劉振鵬等［21］提出動態社交網絡差分隱私保護方法，其縮短了每一次更新匿名圖的時間，但是，差分隱私對度背景知識攻擊的抵抗性較差，需要添加較多的噪聲節點。張曉琳等［22］針對有向社交網絡提出大規模出入度匿名保護方法，其通過貪心算法分組并增加虛擬節點來匿名節點，在對虛擬節點進行合并刪除的過程中依據層次社區結構劃分保持節點所屬社區不變，從而較好地保護圖的基本屬性和社區結構。

上述大多數度匿名研究集中在單一社交網絡匿名保護方面，雖然可以對變化后的整個社交網絡重新匿名再進行發布，但是這樣的匿名方式會存在大量冗余計算，有少量節點和邊發生變化時還是需要對整個社交網絡進行全部匿名化處理。此外，攻擊者在分析前后匿名圖中的節點度變化時，根據前后不同時刻的匿名圖進行關聯攻擊，這存在一定的隱私泄露風險。針對上述問題，本文提出一種圖數據連續發布中的k 度時序匿名方法?？紤]連續圖中節點度數變化會泄露隱私的問題，通過構造k 度時序矩陣來保證前后匿名圖中節點度變化相同的節點個數不少于k 個，然后通過圖修改方法得到一系列匿名圖版本。

1 問題描述及相關定義

本文考慮的時序圖是無向無權的簡單圖的連續變化過程，用G={G1,G2,…,GT}表示圖的變化過程，在t時刻的社 交網絡圖為Gt={Vt,Εt}(1 ＜t＜T)，Vt和Εt表示t時刻圖中的節點和邊，對于每個節點而言，不同時間段其度可能發生變化。盡管當前社交網絡已經滿足k 度匿名性要求，但是，在有新的節點加入時，會破壞原有匿名圖的匿名性，這時需要重新對社交圖進行匿名化處理。此外，根據前后匿名圖，攻擊者有一定幾率能識別出特定的節點，導致該節點被唯一標識，進而導致隱私泄露，本文將其定義為度時序背景知識攻擊。

定義1（度時序背景知識攻擊）度時序背景知識攻擊也稱度變化背景知識攻擊，當攻擊者具有較強的度背景知識時，通過已知節點在不同時刻社交網絡中度數變化的唯一性，可以標識該節點。

定義1 增強了攻擊者的攻擊能力，為了更好地說明度時序攻擊的可能性，本文給出簡單的示例，如圖1 所示，t0時刻圖G0節點度序列為[3,3,2,2,1,1]，其為2 度匿名圖，當有新的節點ν7和ν8加入時，得到t1時刻圖G1，G1的節點度序列為[3,3,3,3,2,1,2,1]，也是一個2 度匿名圖。以度矩陣D的形式可以更直觀地體現各個節點度的變化情況，后續將D定義成度時序矩陣，其中，各個節點的度變化依次為［3，3］、［3，3］、［2，3］、［2，3］、［1，2］、［1，1］、［0，2］、［0，1］，共同組建成D，0 表示該節點未出現在該時刻的圖中。當攻擊者知道節點ν5的度數由1 變成2、節點ν7的度數由0 變成2、節點ν8的度數由0 變成1 時，由于這些節點度的變化在匿名圖中唯一，則攻擊者就能夠以很高的概率唯一標識這些節點，導致這些節點標識隱私泄露，由此可見，滿足k 度匿名并不能抵抗度時序背景知識攻擊。

圖1 不同時刻的2 度匿名圖Fig.1 2-degree anonymous graph at different times

由以上例子可以看出，在不同時間段，節點的度數會發生變化。為了更好地解決節點度數變化可能導致的隱私問題，本文將度變化定義成度時序，具體如定義2 所示。在多個社交網絡中，不同用戶在不同時刻圖中的度數組成度時序矩陣，具體如定義3所示。

定義2（度時序）在連續的圖數據發布中，節點的度數在不同時刻社交圖中會出現不同的值，節點度會隨著時間的變化而改變。節點i的度時序用Di·=[di1,di2,…,dit,…,diT]表示，其中，dit表示在時間t發布的社交網絡Gt中節點i的度數。

定義3（度時序矩陣）由各個節點的度時序向量共同組成的矩陣稱為度時序矩陣Dn×T，其中，n表示連續社交網絡中節點的最大值，T表示連續社交網絡中的圖個數。圖1 中的8×2 矩陣D為度時序矩陣。

定義2 和定義3 是對原始多個待發布圖的特征定義，考慮到攻擊者會根據度變化的唯一性進行攻擊，從而導致隱私泄露，因此，需要保證至少有k-1個節點的度時序相同，這樣才能滿足k 匿名性要求。

定義4（k 度時序匿名）在連續發布圖中，對于任意一個節點ν的度時序，至少存在k-1 個節點的度時序與之相同。

定義4 是傳統k 匿名保護方法的擴展，其能抵抗更強的背景知識攻擊，又同時具備原有k 匿名方法的隱私保護能力。

定理1若社交網絡圖滿足k 度時序匿名，則滿足每個時刻的社交圖是k 度匿名的。

證明在k 度時序匿名的連續圖中，對于任意一個節點ν，由于其滿足k 度時序匿名，則必定存在k-1 個節點的度時序向量是相同的，因此，在對應的時刻圖中，節點ν的度數至少與k-1 個節點的度是相同的，滿足k 度匿名性，因此，k 度時序匿名的時序圖中每一時刻的社交圖都是k 度匿名的。

由定理1 可知，滿足k 度時序匿名一定滿足k 度匿名，簡單而言，就是在能夠抵抗度攻擊的基礎上，還可以抵抗攻擊者根據度變化進行的攻擊。

定義5（k 度時序矩陣）如果連續圖數據發布中的度時序矩陣是k 度時序矩陣，那么在由節點度時序向量組成的度時序矩陣中，對于任意一個節點的度時序向量，至少有k-1 個節點的度時序向量與之相同，即在度時序矩陣中，對于任意一行，至少有k-1 行與其相同。

由定義5 可以看出，本文參考k 度匿名算法中的簡易思想原理，通過提取每個節點的度時序組成度時序矩陣，使度時序矩陣中的每一個行向量都有至少k-1 個行向量與之相同，那么連續圖數據就是k 度時序匿名的。在得到滿足k 匿名性的矩陣后，通過圖修改技術對原始圖進行邊和節點的修改操作，就可以得到所需的匿名圖并進行發布。

2 連續圖中的k 度時序匿名模型

為了滿足圖數據連續發布中的k 度時序匿名性，本文提出連續圖k 度時序匿名模型，其算法分為兩步：首先，獲取整個連續圖數據的度時序矩陣D，基于貪心策略進行度時序矩陣分組劃分，獲取連續圖的目標度時序矩陣D′；其次，為了減少冗余計算，對已經匿名處理的圖進行圖修改操作，結合t-1 時刻匿名圖和t時刻的k 度向量，對下一時刻的原圖Gt進行匿名化處理。為了更好地說明本文模型與傳統模型之間的差別，給出兩者的流程比較，如圖2 所示。

圖2 2 種匿名模型的對比Fig.2 Comparison of two anonymous models

從圖2 可以看出，對于多個待發布的圖數據而言，其k 度匿名模型需要對每一個待發布圖都進行匿名處理，這在很大程度上浪費了時間，而且不能很好地抵抗度時序攻擊，而k 度時序匿名不僅可以抵抗度時序攻擊，還可以更好地處理多個待發布圖，在增強隱私的同時更具靈活性。

2.1 基于貪婪劃分策略的k 度時序矩陣構造

對于社交圖的變化情況，本文考慮符合人們真實活動的社交網絡，即某一用戶在原社交圈認識新的朋友對應社交圖中邊的增加，有新的成員加入該社交圈子對應新節點的增加和新邊的增加。對于圖1 中的D而言，其不滿足2 度時序矩陣的要求，因此，首先要將其轉換成2 度時序矩陣，轉化后各個節點的度變化依次為［3，3］、［3，3］、［2，3］、［2，3］、［1，2］、［1，2］、［0，2］、［0，2］，這些變化共同組成D′。由此可見，D′中至少存在2 個相同的向量，是一個2 度時序矩陣，攻擊者就無法以高于1/2 的概率識別出具體節點，同時在每個時刻的圖中也不可能進行度攻擊。

基于以上考慮，對于度時序矩陣D，本文首先要將其劃分成多個組，其中，每個組中至少包含k 個行向量，使得每個行向量直接轉換成相同向量產生的匿名代價最小，因此，可以參考k 度匿名中對一維度序列的貪婪劃分策略［4］，將距離測度較小的向量合并到同一分組中，節點i和節點j的距離測度為：

其中：Di·表示度時序矩陣的第i行；Dj·表示第j行；||·||1表示行向量的1 范數。對于分組中含有不同的行向量，統一選取產生1 范數最大的行向量作為整個組的匿名標準（這一點與k 度匿名選取最大度作為分組的匿名標準相似），對分組進行統一匿名化，具體操作如算法1 所示。

算法1基于貪婪策略的分組劃分算法

2.2 基于圖修改的k 度時序匿名方法

在經過貪婪分組劃分后，得到滿足k 匿名性的k 度時序矩陣，接下來根據圖修改方法將連續社交圖G轉化成滿足匿名性的連續圖G′。對第一時刻的匿名圖G1，可以采用已有研究中的任何k 度匿名算法進行匿名操作，如何降低其對后續社交網絡的匿名處理時間是研究重點。首先，計算后續匿名圖與已匿名圖之間的差異，即k 度時序矩陣中當前列與下一列的差值，當兩者中的某些元素相同時，表示這些節點不需要進一步處理，當不相同時，需要對當前匿名圖對應的節點進行匿名處理，從而得到下一時刻的匿名圖。因此，首先計算當前匿名圖的k 度向量與下一個待匿名圖對應節點的差值：

如圖3 所示，由于圖1 中連續社交網絡并不滿足2 度時序匿名性，因此需要對其進行匿名化處理。首先根據D′得到需要匿名的節點ν6和ν8都需要增加1 度，通過圖修改方法可以直接在2 個節點之間增加一條邊，如圖3（b）所示，曲線即為添加的邊。

圖3 2 度時序匿名圖Fig.3 2-degree time series anonymous graph

通過圖修改操作來增加邊的過程為：如果節點i和節點j都需要增加度，并且i和j之間不存在邊，則添加一條邊（i，j）。通過圖修改操作來增加虛擬節點的過程為：如果節點i和節點j都需要增加度，但i和j之間存在邊，則創建虛擬節點k，其與節點i、j都相連。具體匿名步驟如算法2 所示。

算法2k 度時序匿名算法

在算法2 中：步驟3～步驟9 主要計算各個已匿名節點達到下一時刻匿名要求的差值，并將其保存到候選節點中；步驟10～步驟23 是對當前已經滿足k 度匿名性的圖進行修改，包括添加邊和添加虛擬節點，使其成為滿足下一時刻匿名要求的k 度匿名圖。算法整體的時間復雜度為Ο（n+c2+c），c表示下一時刻需要匿名的節點個數，待修改節點集合可以提前計算并保存，因此，圖修改方法的時間復雜度為Ο（c2+c）。而對于傳統k 度匿名重構算法而言，由于需要根據k 度向量重新構造匿名圖，因此每次都需要重新匿名處理，時間復雜度為Ο（T·kn），其中，kn為處理單個社交圖的匿名算法的復雜度［4］，T表示社交圖個數。因此，在匿名算法復雜度方面，本文算法性能較優。

3 實驗分析

本文從運行時間和數據屬性實用性2 個方面驗證所提匿名算法的可行性，同時將其與傳統kDA 算法［4］進行比較。kDA 算法是單一時刻社交網絡圖數據匿名算法，為了使其能夠適應圖數據連續發布中的度匿名保護，需要對每個時刻的社交圖都進行一次kDA 算法操作，以此得到整個連續社交圖在各個匿名算法下的實驗數據。所有實驗都是在Windows10 操作系統下進行，配置為16 GB 的RAM、3.40 GHz 的八核處理器i7-6700，編譯環境為Python3.6。

3.1 數據集

本文實驗使用Facebook 數據集，該數據集從斯坦福大學數據庫SNAP（http：//snap.stanford.edu/data/index.html）中得到，共包含4 039 個節點，88 234 條邊。由于該數據集是單個社交圖，因此本文通過隨機增加節點以及增加具有相同鄰居的節點之間的邊，以模擬圖數據連續發布過程。處理后的數據集具體信息如表1 所示。

表1 Facebook 數據集信息Table 1 Facebook dataset information

3.2 結果分析

為了驗證本文算法的有效性，首先，從運行效率上將其與kDA 算法［4］進行對比，運行時間為各個社交圖匿名時間的總和。其次，本文將圖結構的平均聚類系數、平均路徑長度、傳導性等［23］圖結構屬性作為評價指標，通過實驗來驗證本文算法的數據實用性。

圖4 所示為本文算法和kDA 算法的總體運行時間對比，其中，kDA 算法的時間是匿名不同時刻社交圖的時間總和。從圖4 可以看出，隨著隱私程度k 值的不斷增大，算法處理的節點數量不斷增多，因此，2 個算法的總體運行時間都在增加，但是本文所提算法的運行時間總體上都小于kDA 算法，這是因為在后續處理匿名圖時，本文算法可以在第一個匿名圖的基礎上進行圖修改操作，以得到后續的匿名圖，大幅減少了所處理節點的數量，而kDA 算法要重新遍歷整個原始圖進行重構操作，在很大程度上浪費了時間。因此，本文所提算法總體運行時間優于kDA 算法。圖5 所示為本文算法和kDA 算法在不同數據集上通過匿名操作引起的平均聚類系數變化。從圖5 可以看出，隨著隱私程度k 的不斷增大，2 種算法都會改變原始圖的平均聚類系數，但是，kDA 算法中的重構匿名在較大程度上改變了原圖的平均聚類系數，而本文所提算法在原始圖的基礎上進行圖修改，改變平均聚類系數較少，雖然兩者改變程度相似，但是本文算法對度時序背景知識攻擊具有很好的抵抗性，相當于增強了原始圖抵抗去匿名化的能力，本文通過圖修改方法較少地改變了平均聚類系數屬性，較好地保留了原始圖結構，能夠更好地抵抗度時序背景知識攻擊。

圖4 2 種算法的運行時間對比Fig.4 Comparison of running time of two algorithms

圖5 平均聚類系數變化情況Fig.5 Change of average clustering coefficient

圖6 所示為在不同時刻社交圖上通過匿名操作后引起的平均最短路徑變化。從圖6 可以看出，隨著匿名程度的增加，2 個算法引起平均最短路徑的變化越來越大，但是，kDA 算法引起的變化較大，這是因為在圖重構算法中重構具有隨機性，并且會存在強行改變原始圖節點分布的情況，較大地改變了平均路徑長度，而本文算法分析邊操作滿足不了k 匿名性的問題，對無法通過邊操作的節點，通過構建虛擬節點來滿足k 匿名性，這就增大或者減小了一些節點的最短路徑長度，平均最短路徑長度變化較小，從而較好地保留了數據實用性。

圖6 平均最短路徑變化情況Fig.6 Change of average shortest path

圖7 所示為2 種算法中圖的傳導性相對于隱私程度k 的變化情況。從圖7 可以看出，隨著k 值的增加，2 種算法都輕微地影響原圖傳導性的值，相對于其他圖結構屬性而言，傳導性影響較小，但是，本文算法的影響程度總是小于kDA 算法，其較好地保留了原圖的結構屬性。

圖7 傳導性變化情況Fig.7 Change of conductivity

為了更好地說明本文匿名算法的性能，將2 個算法的總體邊變化率的平均值進行比較，如圖8 所示。從圖8 可以看出，kDA 算法較大地改變了原始圖中的邊，這是因為重構算法是根據目標度序列重新生成匿名圖，原有節點的邊可能在重構中轉換成與其他節點相連的邊，這就導致圖中原有邊發生較大改變。而本文算法是在原圖的基礎上進行修改，保證了原有邊不會發生改變，較好地保留了原始邊，因此，在邊的改變情況上體現出性能優勢。

圖8 總體邊變化率Fig.8 Overall edge change rate

4 結束語

傳統k 度匿名在連續社交網絡發布中存在隱私泄露風險，為了保證節點度變化的k 匿名性，本文提出一種k 度時序匿名保護方法。通過提取每個節點在每個時刻圖中的度時序矩陣，構建滿足k 匿名性要求的k 度時序矩陣，利用圖修改技術進行匿名化處理，完成每個時刻社交圖的k 度時序匿名，匿名后的圖不僅在每個時刻都滿足k 度匿名的要求，而且可以抵抗攻擊者基于節點度變化進行的推理攻擊，加強了節點在連續發布圖中的匿名強度。實驗結果驗證了該方法在運行效率上的優勢以及在圖結構屬性上的可用性。本文方法在對社交圖進行匿名保護時引起的結構屬性變化較大，后續將研究如何通過較小的圖結構屬性改變來滿足圖數據連續發布中的匿名保護要求。