基于社區(qū)結(jié)構(gòu)的匿名化方法研究

胡曉依 王宇

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

在社交網(wǎng)絡(luò)發(fā)布隱私保護(hù)的研究中，匿名處理技術(shù)可以分成兩類(lèi)：聚類(lèi)泛化和圖遷移技術(shù)。聚類(lèi)泛化是一種能夠有效防止隱私泄露的方法，它被廣泛地應(yīng)用于關(guān)系型數(shù)據(jù)和社會(huì)網(wǎng)絡(luò)數(shù)據(jù)中。Hay[1]提出了一種方法，根據(jù)相似性將社會(huì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)分配到不同的簇里。當(dāng)發(fā)布數(shù)據(jù)時(shí)，每個(gè)節(jié)點(diǎn)類(lèi)都被泛化成一個(gè)超節(jié)點(diǎn)；Jiao J[4]提出了一種個(gè)性化的隱私保護(hù)方法用于社會(huì)網(wǎng)絡(luò)數(shù)據(jù)的發(fā)布。圖遷移方法被用于k 子圖匿名模型中；Wu 等人[2]設(shè)計(jì)了一個(gè)基于簡(jiǎn)單匿名社會(huì)網(wǎng)絡(luò)的隱私模型。對(duì)于任意一個(gè)匿名圖中的節(jié)點(diǎn)，都有至少k-1 個(gè)節(jié)點(diǎn)與之具有相似的結(jié)構(gòu)。Wang[3]提出了一種基于局部擾亂的匿名算法用于保護(hù)社會(huì)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。Hu[9]提出了一種匿名化方法用來(lái)防止社會(huì)網(wǎng)絡(luò)動(dòng)態(tài)發(fā)布中的鄰居標(biāo)簽的攻擊。

例1：圖1（a）是一個(gè)簡(jiǎn)單的匿名化社會(huì)網(wǎng)絡(luò)，圖1（b）是一個(gè)重構(gòu)圖。從圖中可以看出有2 個(gè)社區(qū){c1,c2}，在圖1中，攻擊者能夠以不高于1/2 概率唯一識(shí)別出目標(biāo)節(jié)點(diǎn)，這滿(mǎn)足了2-匿名的隱私需求。

本文提出一個(gè)新的匿名化方法用于保護(hù)社會(huì)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，同時(shí)設(shè)計(jì)一種隨機(jī)擾亂算法，通過(guò)在社會(huì)網(wǎng)絡(luò)圖中引入不確定性來(lái)實(shí)現(xiàn)匿名化。

例2：圖2（a）是一個(gè)簡(jiǎn)單的匿名后的社會(huì)網(wǎng)絡(luò)，圖2（b）是一種可能的匿名圖。在圖匿名化的情況下，本文的方法是一種隨機(jī)擾亂的方法，即隨機(jī)地刪除和添加邊。同時(shí)給添加的邊賦予一個(gè)0-1之間的概率。

本文具有以下貢獻(xiàn)：

（1）本文考慮到社區(qū)結(jié)構(gòu)分析在社會(huì)網(wǎng)絡(luò)數(shù)據(jù)分析中的重要性，同時(shí)為了提高數(shù)據(jù)的有效性，提出一個(gè)社區(qū)結(jié)構(gòu)關(guān)聯(lián)分析算法用于有效地保護(hù)發(fā)布數(shù)據(jù)中原始網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)信息。

（2）本文結(jié)合聚類(lèi)和隨機(jī)化技術(shù)提出一個(gè)新的隨機(jī)擾亂算法。使得在發(fā)布的數(shù)據(jù)中，攻擊者識(shí)別目標(biāo)節(jié)點(diǎn)的概率不高于1/k，同時(shí)保護(hù)原始社會(huì)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)信息。

（3）根據(jù)該方法的特點(diǎn)，融合常用的社區(qū)結(jié)構(gòu)分析的評(píng)價(jià)指標(biāo)和圖的結(jié)構(gòu)特性，本文選取三種評(píng)價(jià)指標(biāo)來(lái)評(píng)估本文提出的算法的性能。該方法的可行性和有效性已在三個(gè)真實(shí)數(shù)據(jù)集上被證明。

1 問(wèn)題描述

1.1 隱私模型

在本文中，一個(gè)社會(huì)網(wǎng)絡(luò)能夠用G(V,E)來(lái)表示，一個(gè)隱私閾值為k，其中，V 是社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，而E 是邊的集合，代表了目標(biāo)個(gè)體之間的關(guān)系。在文中，我們只研究二元關(guān)系。此外，這個(gè)模型中所有節(jié)點(diǎn)之間的邊都是同一個(gè)類(lèi)型，即無(wú)標(biāo)簽、無(wú)權(quán)重和無(wú)方向。

定義 1（k-匿名社會(huì)網(wǎng)絡(luò)）：一個(gè)社會(huì)網(wǎng)絡(luò)由G=(V,E) 表示。如果攻擊者事先知道任何有關(guān)社會(huì)網(wǎng)絡(luò)G 的子圖信息，且G 中的節(jié)點(diǎn)在匿名化社會(huì)網(wǎng)絡(luò)圖G'中被重新識(shí)別的概率不大于1/k，則社會(huì)網(wǎng)絡(luò)圖G'是一個(gè)匿名社會(huì)網(wǎng)絡(luò)。

1.2 相關(guān)定義

社會(huì)網(wǎng)絡(luò)中的個(gè)體所形成的密切相關(guān)的簇被稱(chēng)之為社區(qū)。這些社區(qū)最顯著的特征是，社區(qū)內(nèi)部實(shí)體之間的聯(lián)系要比社區(qū)外部個(gè)體之間的聯(lián)系更加頻繁。

定義 2（社會(huì)網(wǎng)絡(luò)中的社區(qū)）：一個(gè)社會(huì)網(wǎng)絡(luò)由G=(V,E) 表示，而表示社區(qū)集，其中，且1≤i=j≤m。

定義 3（k-cluster 社會(huì)網(wǎng)絡(luò)）：社會(huì)網(wǎng)絡(luò)可由G=(V,E) 表示，k 用來(lái)表示一個(gè)被社會(huì)網(wǎng)絡(luò)數(shù)據(jù)所確定的閾值。對(duì)于一個(gè)給定節(jié)點(diǎn)V 的簇，與之對(duì)應(yīng)的社會(huì)網(wǎng)絡(luò)表示為Gcl，其中，且1≤t=c≤n，對(duì)于任意的1≤i≤n 有|cli|≥k。

定義 4（節(jié)點(diǎn)與簇之間的距離）：一個(gè)節(jié)點(diǎn)Vp和一個(gè)簇 clq之間的距離可由以下公式計(jì)算：

1.3 問(wèn)題陳述

在本文中，我們要解決以下問(wèn)題。

定義 5（Local-Obfuscation）：用G 表示一個(gè)社會(huì)網(wǎng)絡(luò)圖。如果社會(huì)網(wǎng)絡(luò)G 中的每個(gè)節(jié)點(diǎn) 被識(shí)別的概率不高于1/k，則證明該社會(huì)網(wǎng)絡(luò)G 滿(mǎn)足k-匿名。

2 匿名化方法

在本章節(jié)，我們引入一個(gè)方法去匿名化一個(gè)社會(huì)網(wǎng)絡(luò)。首先，社會(huì)網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都依據(jù)社區(qū)結(jié)構(gòu)信息和節(jié)點(diǎn)之間的距離被分配到不同的簇，使得每個(gè)簇中元素的個(gè)數(shù)都不小于k，然后在簇中進(jìn)行重構(gòu)使每個(gè)簇之間的邊保持不變，最后生成局部擾亂圖。

2.1 對(duì)社會(huì)網(wǎng)絡(luò)進(jìn)行聚類(lèi)

把當(dāng)前的節(jié)點(diǎn)列表按照度的大小進(jìn)行降序排列，即列表中的第一個(gè)元素是具有最大的度的節(jié)點(diǎn)。在一個(gè)新的組群中，在節(jié)點(diǎn)列表中具有最高的度的那些節(jié)點(diǎn)都被當(dāng)做種子節(jié)點(diǎn)，然后將最接近當(dāng)前組群的節(jié)點(diǎn)挑選出來(lái)，將其合并到節(jié)點(diǎn)列表中，直到組群中節(jié)點(diǎn)的個(gè)數(shù)等于k，然后開(kāi)始進(jìn)行下一個(gè)組群的構(gòu)建。

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 實(shí)驗(yàn)評(píng)估

實(shí)驗(yàn)的目的是根據(jù)匿名過(guò)程中匿名社會(huì)網(wǎng)絡(luò)數(shù)據(jù)的質(zhì)量，來(lái)評(píng)估本文提出的算法的性能。

3.1 數(shù)據(jù)集

本次實(shí)驗(yàn)在3 個(gè)真實(shí)數(shù)據(jù)集上驗(yàn)證數(shù)據(jù)的可用性[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 評(píng)價(jià)指標(biāo)

GN 算法[8]是一個(gè)經(jīng)典的社區(qū)檢測(cè)算法，它能夠檢測(cè)出原始社會(huì)網(wǎng)絡(luò)和匿名化社會(huì)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。假設(shè)最初的社會(huì)網(wǎng)絡(luò)G 中的社區(qū)是匿名化的社區(qū)為

本文采用兩種評(píng)價(jià)指標(biāo)來(lái)評(píng)估匿名前和匿名后社區(qū)結(jié)構(gòu)的完整性：杰卡德相似系數(shù)和模塊化變化。

杰卡德相似系數(shù)常被用于評(píng)估兩個(gè)集合的相似程度。在社會(huì)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)研究中，它也被用來(lái)比較社區(qū)結(jié)構(gòu)劃分的準(zhǔn)確程度。本文利用杰卡德相似系數(shù)來(lái)衡量匿名前和匿名后社區(qū)結(jié)構(gòu)的相似性。具體的公式如下：

在本文中，整體的平均值被用作全部社區(qū)保護(hù)的標(biāo)準(zhǔn)，見(jiàn)公式（3）：

模塊化在社區(qū)檢測(cè)算法中是一個(gè)重要的參數(shù)，主要用來(lái)評(píng)估社區(qū)的劃分程度。本文根據(jù)匿名前和匿名后模塊化的差異值來(lái)衡量原始社會(huì)網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的保護(hù)程度。見(jiàn)公式（4）：

本文將所有節(jié)點(diǎn)的平均局部聚類(lèi)系數(shù)作為評(píng)價(jià)標(biāo)準(zhǔn)[3]。具體的定義和描述見(jiàn)公式（5）：

3.3 實(shí)驗(yàn)結(jié)果和分析

首先，我們分析在不同隱私要求下不同數(shù)據(jù)集的杰卡德相似系數(shù)，圖3顯示了不同k 值下的杰卡德相似性。隨著隱私水平k 的增大，原始社會(huì)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)被保護(hù)的程度呈現(xiàn)下降趨勢(shì)，這是因?yàn)殡S著k 的增大，簇中節(jié)點(diǎn)的個(gè)數(shù)也跟著增大，使得某些新增的節(jié)點(diǎn)不屬于同一個(gè)社區(qū)，最終對(duì)社區(qū)結(jié)構(gòu)造成極大的破壞。因此，原始社會(huì)網(wǎng)絡(luò)和匿名化社會(huì)網(wǎng)絡(luò)之間的相似系數(shù)會(huì)降低，原始社區(qū)結(jié)構(gòu)信息的保護(hù)程度也隨之降低。

在選取不同的k 值后，本文提出的Local-obsfucation 方法比Local-perturbation 方法[3]具有更大的杰卡德相似系數(shù)，說(shuō)明本文提出的方法能夠更好地保護(hù)社區(qū)結(jié)構(gòu)。

圖4顯示了在三個(gè)不同時(shí)期，三個(gè)數(shù)據(jù)集的平均聚類(lèi)系數(shù)隨著k 的變化而變化。當(dāng)增大k 時(shí)，經(jīng)過(guò)兩種匿名化方法處理后的社會(huì)網(wǎng)絡(luò)圖的平均聚類(lèi)系數(shù)會(huì)變小。

隨著隱私匿名化需求的增大，對(duì)原始社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)的破壞也在增大，與此同時(shí)，平均聚類(lèi)系數(shù)會(huì)變小，并且與之對(duì)應(yīng)的整體平均局部聚類(lèi)系數(shù)也跟著變小。

為了更好的理解圖5中k 值的影響，我們討論了在不同保護(hù)程度要求k 下的。隨著k 的增大，被兩種匿名化方法處理后的社會(huì)網(wǎng)絡(luò)的模塊化的差異值也逐步增大，而且對(duì)原始社區(qū)的破壞也在增大，不同社區(qū)之間的邊界也開(kāi)始變得模糊。差值越大，對(duì)原始社會(huì)網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的破壞就越嚴(yán)重。與本文所提出的算法相比，具有更好的效果。

4 結(jié)論

為了解決在社會(huì)網(wǎng)絡(luò)數(shù)據(jù)發(fā)布中k 匿名技術(shù)導(dǎo)致社區(qū)結(jié)構(gòu)信息被嚴(yán)重破壞的問(wèn)題，本文提出了一種新的隱私保護(hù)方法，該方法是一種結(jié)合聚類(lèi)技術(shù)和隨機(jī)化技術(shù)的局部擾亂方法。同時(shí)，本文給出了詳細(xì)的算法流程和實(shí)現(xiàn)步驟。該方法不僅能夠保護(hù)隱私，還能保護(hù)社會(huì)網(wǎng)絡(luò)中的原始特征。