基于社區結構的匿名化方法研究

胡曉依 王宇

（曲阜師范大學軟件學院 山東省曲阜市 273100）

在社交網絡發布隱私保護的研究中，匿名處理技術可以分成兩類：聚類泛化和圖遷移技術。聚類泛化是一種能夠有效防止隱私泄露的方法，它被廣泛地應用于關系型數據和社會網絡數據中。Hay[1]提出了一種方法，根據相似性將社會網絡中的所有節點分配到不同的簇里。當發布數據時，每個節點類都被泛化成一個超節點；Jiao J[4]提出了一種個性化的隱私保護方法用于社會網絡數據的發布。圖遷移方法被用于k 子圖匿名模型中；Wu 等人[2]設計了一個基于簡單匿名社會網絡的隱私模型。對于任意一個匿名圖中的節點，都有至少k-1 個節點與之具有相似的結構。Wang[3]提出了一種基于局部擾亂的匿名算法用于保護社會網絡中的社區結構。Hu[9]提出了一種匿名化方法用來防止社會網絡動態發布中的鄰居標簽的攻擊。

例1：圖1（a）是一個簡單的匿名化社會網絡，圖1（b）是一個重構圖。從圖中可以看出有2 個社區{c1,c2}，在圖1中，攻擊者能夠以不高于1/2 概率唯一識別出目標節點，這滿足了2-匿名的隱私需求。

本文提出一個新的匿名化方法用于保護社會網絡中的社區結構，同時設計一種隨機擾亂算法，通過在社會網絡圖中引入不確定性來實現匿名化。

例2：圖2（a）是一個簡單的匿名后的社會網絡，圖2（b）是一種可能的匿名圖。在圖匿名化的情況下，本文的方法是一種隨機擾亂的方法，即隨機地刪除和添加邊。同時給添加的邊賦予一個0-1之間的概率。

本文具有以下貢獻：

（1）本文考慮到社區結構分析在社會網絡數據分析中的重要性，同時為了提高數據的有效性，提出一個社區結構關聯分析算法用于有效地保護發布數據中原始網絡的社區結構信息。

（2）本文結合聚類和隨機化技術提出一個新的隨機擾亂算法。使得在發布的數據中，攻擊者識別目標節點的概率不高于1/k，同時保護原始社會網絡中的社區結構信息。

（3）根據該方法的特點，融合常用的社區結構分析的評價指標和圖的結構特性，本文選取三種評價指標來評估本文提出的算法的性能。該方法的可行性和有效性已在三個真實數據集上被證明。

1 問題描述

1.1 隱私模型

在本文中，一個社會網絡能夠用G(V,E)來表示，一個隱私閾值為k，其中，V 是社會網絡中節點的集合，而E 是邊的集合，代表了目標個體之間的關系。在文中，我們只研究二元關系。此外，這個模型中所有節點之間的邊都是同一個類型，即無標簽、無權重和無方向。

定義 1（k-匿名社會網絡）：一個社會網絡由G=(V,E) 表示。如果攻擊者事先知道任何有關社會網絡G 的子圖信息，且G 中的節點在匿名化社會網絡圖G'中被重新識別的概率不大于1/k，則社會網絡圖G'是一個匿名社會網絡。

1.2 相關定義

社會網絡中的個體所形成的密切相關的簇被稱之為社區。這些社區最顯著的特征是，社區內部實體之間的聯系要比社區外部個體之間的聯系更加頻繁。

定義 2（社會網絡中的社區）：一個社會網絡由G=(V,E) 表示，而表示社區集，其中，且1≤i=j≤m。

定義 3（k-cluster 社會網絡）：社會網絡可由G=(V,E) 表示，k 用來表示一個被社會網絡數據所確定的閾值。對于一個給定節點V 的簇，與之對應的社會網絡表示為Gcl，其中，且1≤t=c≤n，對于任意的1≤i≤n 有|cli|≥k。

定義 4（節點與簇之間的距離）：一個節點Vp和一個簇 clq之間的距離可由以下公式計算：

1.3 問題陳述

在本文中，我們要解決以下問題。

定義 5（Local-Obfuscation）：用G 表示一個社會網絡圖。如果社會網絡G 中的每個節點 被識別的概率不高于1/k，則證明該社會網絡G 滿足k-匿名。

2 匿名化方法

在本章節，我們引入一個方法去匿名化一個社會網絡。首先，社會網絡中所有的節點都依據社區結構信息和節點之間的距離被分配到不同的簇，使得每個簇中元素的個數都不小于k，然后在簇中進行重構使每個簇之間的邊保持不變，最后生成局部擾亂圖。

2.1 對社會網絡進行聚類

把當前的節點列表按照度的大小進行降序排列，即列表中的第一個元素是具有最大的度的節點。在一個新的組群中，在節點列表中具有最高的度的那些節點都被當做種子節點，然后將最接近當前組群的節點挑選出來，將其合并到節點列表中，直到組群中節點的個數等于k，然后開始進行下一個組群的構建。

Algorithm 1 k-Cluster(G)Inpu Outpt: Social network G and the threshold k ut: A k-cluster graph Gcl and the number of clusters

1: ;2: u=the first node in V;3: while do 4: cluster cl=new cluster{u}5: while do 6: for each u do 7: ;9: end for 10: if the same community then 11:images/BZ_252_1485_2596_1585_2641.png12:13: end while 14: end while 15: if then 16:17: for each do 18: According to the distance,the nodes in current cli are divided into other groups;19: end for 20: end if

2.2 不確定性

Algorithm 2 Obfuscation(G)Input: A k-cluster graph Gcl the group set Cli Output: An anonymized social network G’1: while |cli|>0 do 2: repeat 3: pick randomly;4: until 5: Sample with probability ;6: end while 7: return G’

3 實驗評估

實驗的目的是根據匿名過程中匿名社會網絡數據的質量，來評估本文提出的算法的性能。

3.1 數據集

本次實驗在3 個真實數據集上驗證數據的可用性[4]：

·WebKB(http://linqs.umiacs.umd.edu/projects//projects/lbc/index.html)

·Citation(http://www.cs.umd.edu/projects/linqs/projects/lbc/index.html).

·Cora(http://www.cs.umd.edu/projects/linqs/projects/lbc/index.html).

3.2 評價指標

GN 算法[8]是一個經典的社區檢測算法，它能夠檢測出原始社會網絡和匿名化社會網絡中的社區結構。假設最初的社會網絡G 中的社區是匿名化的社區為

本文采用兩種評價指標來評估匿名前和匿名后社區結構的完整性：杰卡德相似系數和模塊化變化。

杰卡德相似系數常被用于評估兩個集合的相似程度。在社會網絡的社區結構研究中，它也被用來比較社區結構劃分的準確程度。本文利用杰卡德相似系數來衡量匿名前和匿名后社區結構的相似性。具體的公式如下：

在本文中，整體的平均值被用作全部社區保護的標準，見公式（3）：

模塊化在社區檢測算法中是一個重要的參數，主要用來評估社區的劃分程度。本文根據匿名前和匿名后模塊化的差異值來衡量原始社會網絡中社區結構的保護程度。見公式（4）：

本文將所有節點的平均局部聚類系數作為評價標準[3]。具體的定義和描述見公式（5）：

3.3 實驗結果和分析

首先，我們分析在不同隱私要求下不同數據集的杰卡德相似系數，圖3顯示了不同k 值下的杰卡德相似性。隨著隱私水平k 的增大，原始社會網絡社區結構被保護的程度呈現下降趨勢，這是因為隨著k 的增大，簇中節點的個數也跟著增大，使得某些新增的節點不屬于同一個社區，最終對社區結構造成極大的破壞。因此，原始社會網絡和匿名化社會網絡之間的相似系數會降低，原始社區結構信息的保護程度也隨之降低。

在選取不同的k 值后，本文提出的Local-obsfucation 方法比Local-perturbation 方法[3]具有更大的杰卡德相似系數，說明本文提出的方法能夠更好地保護社區結構。

圖4顯示了在三個不同時期，三個數據集的平均聚類系數隨著k 的變化而變化。當增大k 時，經過兩種匿名化方法處理后的社會網絡圖的平均聚類系數會變小。

隨著隱私匿名化需求的增大，對原始社會網絡結構的破壞也在增大，與此同時，平均聚類系數會變小，并且與之對應的整體平均局部聚類系數也跟著變小。

為了更好的理解圖5中k 值的影響，我們討論了在不同保護程度要求k 下的。隨著k 的增大，被兩種匿名化方法處理后的社會網絡的模塊化的差異值也逐步增大，而且對原始社區的破壞也在增大，不同社區之間的邊界也開始變得模糊。差值越大，對原始社會網絡中社區結構的破壞就越嚴重。與本文所提出的算法相比，具有更好的效果。

4 結論

為了解決在社會網絡數據發布中k 匿名技術導致社區結構信息被嚴重破壞的問題，本文提出了一種新的隱私保護方法，該方法是一種結合聚類技術和隨機化技術的局部擾亂方法。同時，本文給出了詳細的算法流程和實現步驟。該方法不僅能夠保護隱私，還能保護社會網絡中的原始特征。