保持結(jié)點(diǎn)間可達(dá)性的社會(huì)網(wǎng)絡(luò)圖匿名技術(shù)

劉向宇，安云哲，周大海，夏秀峰

(沈陽航空航天大學(xué) 計(jì)算機(jī)學(xué)院，沈陽 110136)

?

信息科學(xué)與工程

保持結(jié)點(diǎn)間可達(dá)性的社會(huì)網(wǎng)絡(luò)圖匿名技術(shù)

劉向宇，安云哲，周大海，夏秀峰

(沈陽航空航天大學(xué) 計(jì)算機(jī)學(xué)院，沈陽 110136)

為了保護(hù)社會(huì)網(wǎng)絡(luò)隱私信息，提出了多種社會(huì)網(wǎng)絡(luò)圖匿名化技術(shù)。圖匿名化目的在于通過圖修改操作來防止隱私泄露，同時(shí)保證匿名圖在社會(huì)網(wǎng)絡(luò)分析和圖查詢方面的數(shù)據(jù)可用性。作為圖查詢操作的基礎(chǔ)，可達(dá)性查詢是衡量圖數(shù)據(jù)可用性的一項(xiàng)重要指標(biāo)。然而，圖匿名會(huì)對(duì)結(jié)點(diǎn)間的可達(dá)性造成影響，導(dǎo)致較大的可達(dá)性信息損失。為了保持匿名圖中結(jié)點(diǎn)間的可達(dá)性，提出可達(dá)性保持圖匿名化算法(簡稱RPA算法)。通過生成可達(dá)性保持最小子圖并在圖匿名化過程中保持該子圖的完整性，RPA算法實(shí)現(xiàn)了在匿名圖中保持結(jié)點(diǎn)間的可達(dá)性。基于真實(shí)數(shù)據(jù)集通過大量實(shí)驗(yàn)測試和分析，驗(yàn)證了RPA算法可以保證在匿名圖中進(jìn)行可達(dá)性查詢的高準(zhǔn)確度。

社會(huì)網(wǎng)絡(luò)；隱私；圖匿名；可達(dá)性

隨著社會(huì)網(wǎng)絡(luò)的快速發(fā)展和普及，社會(huì)網(wǎng)絡(luò)中隱私信息的安全性成為數(shù)據(jù)隱私保護(hù)研究的熱點(diǎn)問題。為了保護(hù)社會(huì)網(wǎng)絡(luò)隱私信息，提出了多種社會(huì)網(wǎng)絡(luò)圖匿名化技術(shù)[1-4]。圖匿名化目的在于通過圖修改操作來防止隱私泄露，同時(shí)保證匿名圖在社會(huì)網(wǎng)絡(luò)分析和圖查詢方面的數(shù)據(jù)可用性。

結(jié)點(diǎn)間的可達(dá)性是一項(xiàng)重要的圖查詢操作，包括查詢兩個(gè)結(jié)點(diǎn)是否存在路徑可達(dá)[5-6]或者兩個(gè)結(jié)點(diǎn)是否在一定距離閾值內(nèi)可達(dá)[7]；可達(dá)性也是衡量圖數(shù)據(jù)可用性的重要指標(biāo)。在社會(huì)網(wǎng)絡(luò)中，可達(dá)性查詢操作更加頻繁。例如，很多社會(huì)網(wǎng)絡(luò)(Facebook，QQ朋友網(wǎng)等)均支持人脈聯(lián)系查詢：輸入用戶u和v，返回u、v之間的可達(dá)路徑以及路徑上包含的用戶。顯然，此種人脈聯(lián)系查詢的本質(zhì)是結(jié)點(diǎn)間的可達(dá)性查詢操作。很多社會(huì)網(wǎng)絡(luò)應(yīng)用基于結(jié)點(diǎn)間的可達(dá)性來進(jìn)行好友推薦[8-9]，提高社會(huì)網(wǎng)絡(luò)的粘度和用戶活躍度。因此，保持社會(huì)網(wǎng)絡(luò)中結(jié)點(diǎn)間的可達(dá)性具有實(shí)際意義。然而，在文獻(xiàn)[10]中指出，由于當(dāng)前圖匿名技術(shù)沒有考慮圖修改操作對(duì)于結(jié)點(diǎn)間可達(dá)性的影響，從而導(dǎo)致結(jié)點(diǎn)可達(dá)性信息損失很大。

圖1 虛構(gòu)微博網(wǎng)絡(luò)G及結(jié)點(diǎn)的度

然而，圖G1、G2在保持結(jié)點(diǎn)間可達(dá)性方面具有不同效果。給定圖G和距離閾值d，Rd(G)表示G中所有最短路徑長度≤d的結(jié)點(diǎn)對(duì)集合；距離閾值d表示用戶感興趣的可達(dá)性查詢路徑長度。匿名化G得到匿名圖Gk，則Rd(Gk)和Rd(G)的相近程度衡量了Gk在d-可達(dá)性查詢上的數(shù)據(jù)可用性。在圖2中，當(dāng)距離閾值d=2時(shí)，G1比G減少了4個(gè)2-可達(dá)結(jié)點(diǎn)對(duì)〈v1,v7〉、〈v3,v7〉、〈v4,v7〉和〈v4,v12〉，增加了一個(gè)2-可達(dá)結(jié)點(diǎn)對(duì)v9,v11；而G2和G具有相同的2-可達(dá)結(jié)點(diǎn)對(duì)集合，顯然G2更好地保持了圖G中結(jié)點(diǎn)間可達(dá)性。已知圖G和可達(dá)性查詢距離閾值d，本文期望構(gòu)建G的k-度匿名圖Gk，使得Rd(Gk)和Rd(G)盡可能相近。

圖2 圖G的兩個(gè)2-度匿名圖

1 背景知識(shí)和問題定義

在本文中，將社會(huì)網(wǎng)絡(luò)表示為有向圖G=(V，E)，V(G)和E(G)分別表示G的結(jié)點(diǎn)集和邊集。結(jié)點(diǎn)對(duì)(u,v)表示從結(jié)點(diǎn)u指向v的邊；邊(u,v)稱為u的出邊、v的入邊；v是u的出邊鄰居，u是v的入邊鄰居。結(jié)點(diǎn)u的入邊數(shù)目是u的入度，記作din(u)；u的出邊數(shù)目是u的出度，記作dout(u)；結(jié)點(diǎn)u的度以(din(u),dout(u))的形式來表示。

本文假設(shè)攻擊者發(fā)動(dòng)度隱私攻擊，即將攻擊目標(biāo)的出度和入度作為背景知識(shí)進(jìn)行結(jié)點(diǎn)身份識(shí)別，下面給出社會(huì)網(wǎng)絡(luò)隱私保護(hù)模型。

定義1.k-度匿名. 已知圖G(V,E)和正整數(shù)k，對(duì)于?v∈V，如果G存在至少k-1個(gè)其他結(jié)點(diǎn)與v具有相同的出度和入度，則G為k-度匿名圖。

例如，圖2中的G1和G2均為2-度匿名圖。

數(shù)據(jù)發(fā)布者可以根據(jù)圖查詢和分析需求來選擇合適的d值，閾值d反映了對(duì)于保持匿名圖中結(jié)點(diǎn)間可達(dá)性的要求。通常情況下，d值不會(huì)很大，這是因?yàn)楦鶕?jù)社會(huì)網(wǎng)絡(luò)小世界理論(亦稱六度分隔理論)，任意兩個(gè)結(jié)點(diǎn)之間所間隔的結(jié)點(diǎn)通常不會(huì)超過六個(gè)，針對(duì)距離較遠(yuǎn)的兩個(gè)結(jié)點(diǎn)間關(guān)系的研究意義不大。在社會(huì)網(wǎng)絡(luò)中，d-可達(dá)性是結(jié)點(diǎn)鄰居查詢、可達(dá)性查詢、路徑計(jì)算、聚集查詢等圖查詢操作的基礎(chǔ)，因此保持匿名圖中結(jié)點(diǎn)間的d-可達(dá)性具有實(shí)際意義。

已知圖G(V,E)，正整數(shù)k和閾值d，本文研究如何生成k-度匿名圖Gk(Vk,Ek)，使得Gk較好地保持G中結(jié)點(diǎn)間的d-可達(dá)性。匿名過程中僅考慮結(jié)點(diǎn)添加操作，即V?Vk。問題1給出了可達(dá)性保持圖匿名化問題。

問題1.可達(dá)性保持圖匿名化問題.已知圖G(V,E)，正整數(shù)k和d，構(gòu)建一個(gè)k-度匿名圖Gk(Vk,Ek)使得匿名信息損失C(G,Gk)最小化，其中C(G,Gk)包含三部分：

(1)d-可達(dá)性信息損失；

(2)結(jié)點(diǎn)修改信息損失；

(3)邊修改信息損失。

在問題1中，d-可達(dá)性信息損失采用|R(G)-|Rd(G)|+|Rd(G)-R(G)|進(jìn)行衡量，即在Rd(G)中增加和減少的d-可達(dá)結(jié)點(diǎn)對(duì)數(shù)目；結(jié)點(diǎn)和邊修改信息損失分別通過結(jié)點(diǎn)、邊修改數(shù)目來評(píng)估。

定理1.可達(dá)性保持圖匿名化問題是NP-hard問題。

定理1可以通過歸約NP-complete問題k-DIMENSIONAL PERFECT MATCHING[12]來進(jìn)行證明。

2 可達(dá)性保持最小子圖

為了保持匿名圖中結(jié)點(diǎn)間的d-可達(dá)性，可以生成保持發(fā)布圖可達(dá)性的最小子圖，并在圖匿名化過程中保持該子圖的完整性?；诖怂枷?，本節(jié)提出d-可達(dá)性保持最小子圖及其生成算法。

2.1 可達(dá)性保持子圖

定義3.可達(dá)性保持子圖. 已知圖G(V,E)和正整數(shù)d，假設(shè)G′(V′,E′)是G的一個(gè)子圖，并且滿足V′=V和E′?E；對(duì)于G中的任意d-可達(dá)結(jié)點(diǎn)對(duì)u,v，如果在G′中u到v仍然符合d-可達(dá)，則G′是G的一個(gè)d-可達(dá)性保持子圖(d-Reachability Preserving Subgraph, 簡稱d-RPG)，記作G′dG。

例如，對(duì)于圖1(a)中的G，圖3顯示了G的兩個(gè)3-RPG，即G33G和3G。為了保證圖匿名的低信息損失，希望找到G的最小d-RPG。

圖3 有向圖G的兩個(gè)最小3-RPG

定義4.可達(dá)性保持最小子圖.已知圖G(V,E)和正整數(shù)d，如果GddG并且Gd的任意子圖G′均不滿足G′dG，則Gd是G的d-可達(dá)性保持最小子圖，記作最小d-RPG。

定理2. 已知圖G(V,E)和正整數(shù)d，生成G的最小d-RPG是NP-hard問題。

可以通過歸約NP-complete問題DIRECTED HAMILTONIAN CIRCUIT[14]來對(duì)定理2證明。

2.2 生成最小d-RPG

已知圖G(V,E)和正整數(shù)d，算法1給出一種最小d-RPG生成算法。

算法1. 生成最小d-RPG.

輸入：圖G(V,E)和正整數(shù)d

輸出：最小d-RPGGd

(1)Gd←G；

(2)For each (u,v)∈Gddo

(3)G′←Gd{(u,v)}；

(4) IfR(G′) =R(Gd) then

(5)Gd←Gd{(u,v)}；

(6) end if

(7)end for

(8)returnGd.

算法1首先利用G來初始化Gd(1行)。對(duì)于Gd中的每條邊(u,v)，檢查該邊是否可以從Gd中刪除(2-4行)。在Gd中刪除邊(u,v)時(shí)，會(huì)發(fā)生兩種情況：(1)Rd(Gd)保持不變；(2)Rd(Gd)丟失一些d-可達(dá)結(jié)點(diǎn)對(duì)。如果Rd(Gd)保持不變，則邊(u,v)可以刪除并將其從Gd中刪除(4-5行)；如果Rd(Gd)發(fā)生變化，則邊(u,v)不可刪除。算法1為Gd中每條邊執(zhí)行驗(yàn)證和刪除操作后，輸出Gd作為結(jié)果。顯然，算法1生成的Gd是G的一個(gè)最小d-RPG。

3 保持結(jié)點(diǎn)間可達(dá)性圖匿名化算法

本節(jié)提出一種保持結(jié)點(diǎn)間可達(dá)性的圖匿名化算法(Reachability Preserving Anonymization,簡稱RPA算法)。RPA算法通過在匿名過程中保持d-RPG的完整性，從而保持匿名圖中結(jié)點(diǎn)間的d-可達(dá)性。首先介紹RPA算法整體框架，然后介紹算法具體細(xì)節(jié)。

3.1 RPA算法整體框架

算法2顯示了RPA的整體框架。已知圖G(V,E)及其d-RPGGd、正整數(shù)k、信息損失權(quán)重參數(shù)α和β，RPA算法將G匿名化為k-度匿名圖Gk。

算法2. 可達(dá)性保持圖匿名化(RPA)算法.

輸入：圖G(V,E)及其d-RPGGd，正整數(shù)k，匿名信息損失權(quán)重參數(shù)α和β

輸出：k-度匿名圖Gk(Vk,Ek)

(1)基于Gd初始化G中結(jié)點(diǎn)標(biāo)簽和邊標(biāo)簽；

(2)repeat

(3)Seed←SearchSeedVertex(G)；

(4)VA←AnonymizationVertexSet(G,Seed,k,α,β)；

(5) if |VA|

(6) 將Seed標(biāo)記為”postprocessing”；

(7) else

(8) (din,dout)←OptimalDegree(VA,α,β)；

(9) for each vertexv∈VAdo

(10) 將結(jié)點(diǎn)v匿名化為度(din,dout)；

(11) end for

(12) end if

(13)untilUnAnonymized(G)<2k-1；

(14)匿名化”unanonymized”和”postprocessing”結(jié)點(diǎn)；

(15)基于G中結(jié)點(diǎn)和邊標(biāo)簽生成Gk；

(16)returnGk.

與傳統(tǒng)圖匿名算法中直接進(jìn)行圖修改操作不同，算法2通過標(biāo)記G上的結(jié)點(diǎn)和邊標(biāo)簽來進(jìn)行匿名(2-13行)，當(dāng)G中結(jié)點(diǎn)均標(biāo)記為”anonymized”時(shí)，基于結(jié)點(diǎn)和邊上的標(biāo)簽來生成匿名圖Gk(15行)。在匿名化過程中，算法2首先對(duì)G中結(jié)點(diǎn)標(biāo)簽和邊標(biāo)簽進(jìn)行初始化(1行)，結(jié)點(diǎn)標(biāo)簽初始化為”unanonymized”，存在于Gd中邊的標(biāo)簽初始化為”added”，其他邊標(biāo)簽初始化為”un-added”。算法2在標(biāo)記”unanonymized”的結(jié)點(diǎn)中選擇種子結(jié)點(diǎn)Seed(3行)。其中，匿名信息損失權(quán)重參數(shù)和由數(shù)據(jù)發(fā)布用戶根據(jù)數(shù)據(jù)發(fā)布用途和可用性來進(jìn)行設(shè)置，參數(shù)是用于衡量邊修改信息損失的權(quán)重參數(shù)，是衡量d-可達(dá)性信息損失的權(quán)重參數(shù)。基于種子結(jié)點(diǎn)Seed生成匿名結(jié)點(diǎn)集VA(4行)，其中VA包含k個(gè)結(jié)點(diǎn)并且結(jié)點(diǎn)具有相近的度。對(duì)于某些種子結(jié)點(diǎn)Seed，生成的VA包含結(jié)點(diǎn)數(shù)目可能小于k，將此類Seed結(jié)點(diǎn)標(biāo)記為”postprocessing”(5-6行)。基于VA和參數(shù)α、β，計(jì)算最優(yōu)結(jié)點(diǎn)度(din,dout)并將VA中每個(gè)結(jié)點(diǎn)的度匿名化為(din,dout)(8-11行)，匿名化后的結(jié)點(diǎn)標(biāo)記為”anonymized”。當(dāng)G中未匿名結(jié)點(diǎn)的數(shù)目小于2k-1時(shí)，迭代匿名化過程(2-13行)停止。此時(shí)，將標(biāo)記為”unanonymized”和”postprocessing”的結(jié)點(diǎn)進(jìn)行后期匿名(14行)。下面介紹算法具體細(xì)節(jié)。

3.2 匿名標(biāo)簽

在討論RPA算法匿名化過程之前，首先介紹結(jié)點(diǎn)和邊上的標(biāo)簽。邊標(biāo)簽包括”added”和”un-added”。在圖G中，標(biāo)記”added”的邊表示Gk中包含該邊，”un-added”邊表示Gk中無此邊。結(jié)點(diǎn)標(biāo)簽”anonymized”表示已匿名結(jié)點(diǎn)，”unanonymized”表示未匿名結(jié)點(diǎn)，需要后期匿名的結(jié)點(diǎn)標(biāo)記為”postprocessing”。當(dāng)算法2基于Gd對(duì)G中結(jié)點(diǎn)和邊的標(biāo)簽初始化時(shí)，結(jié)點(diǎn)均標(biāo)記為”unanonymized”，在Gd中的邊標(biāo)記為”added”，其他邊標(biāo)記為”un-added”。

對(duì)于G中未匿名結(jié)點(diǎn)u，根據(jù)在Gk中的結(jié)點(diǎn)、邊標(biāo)簽將u的出邊分為三類：exist，non-exist和may-exist。圖5中顯示如何基于標(biāo)簽來確定u的出邊類型。如圖5(a)所示，標(biāo)記為“added”的邊屬于exist類型，此類型邊均存在于Gk。圖5(b)中的邊(u,v4)雖然標(biāo)記了“un-added”，但是如果邊(u,v4)存在于Gk中會(huì)使得v4不符合k-匿名，因此該邊屬于non-exist類型而不存在于Gk。圖5(c)中的邊(u,v5)和(u,v6)屬于may-exist類型，即可能存在于Gk，因?yàn)閷⑦?u,v5)和(u,v6)添加入Gk中不會(huì)對(duì)v5、v6是否符合k-匿名造成影響。相似地，可以給出G中的入邊分類。

圖5 基于在Gk中的結(jié)點(diǎn)、邊標(biāo)簽將u的出邊分為三類：exist，non-exist和may-exist

定義5.最小出度和最大出度. 已知圖G(V,E)和結(jié)點(diǎn)u∈V，u的最小出度為u的exist出邊數(shù)目，記作MIN_OUT(u)；u的最大出度為u的exist和may-exist出邊數(shù)目之和，記作MAX_OUT(u)。

相似地，可以定義最小入度(記作MIN_IN)和最大入度(記作MAX_IN)。

3.3 結(jié)點(diǎn)匿名

算法2在匿名化結(jié)點(diǎn)u使其度為(din,dout)時(shí)(10行)，din和dout取值滿足din≥MIN_IN(u)和dout≥MIN_OUT(u)。本節(jié)介紹如何匿名化結(jié)點(diǎn)的出度，入度匿名過程與之相似。

當(dāng)MIN_OUT(u)≤dout≤MAX_OUT(u)時(shí)，算法2在u的may-exist出邊中隨機(jī)選擇dout-MIN_OUT(u)條邊并將其標(biāo)簽改為”added”；當(dāng)dout>MAX_OUT(u)時(shí)，不僅將u的所有may-exist出邊標(biāo)記為”added”，還需添加dout-MAX_OUT(u)個(gè)偽結(jié)點(diǎn)，并添加邊連接u至這些結(jié)點(diǎn)。由于新添加結(jié)點(diǎn)的度為(1, 0)或(0, 1)，根據(jù)社會(huì)網(wǎng)絡(luò)冪率度分布可知，具有該度的結(jié)點(diǎn)數(shù)目遠(yuǎn)大于k，新結(jié)點(diǎn)符合k-匿名并標(biāo)記為”anonymized”。如5.3節(jié)所示，匿名化真實(shí)社會(huì)網(wǎng)絡(luò)時(shí)添加的假點(diǎn)數(shù)目很小，在保證匿名圖安全性的同時(shí)不會(huì)對(duì)圖數(shù)據(jù)可用性產(chǎn)生影響。在匿名化結(jié)點(diǎn)u后，將結(jié)點(diǎn)u標(biāo)記為”anonymized”。

3.4 計(jì)算匿名化信息損失

將結(jié)點(diǎn)u的度匿名化為(din,dout)時(shí)，匿名信息損失計(jì)算公式為：

Cost(u,din,dout) =Costin(u,din) +Costout(u,dout)

其中，Costin(u,din)表示入度匿名信息損失，Costout(u,dout)表示出度匿名信息損失。入度匿名信息損失Costin(u,din)可計(jì)算為：

其中參數(shù)α是用于衡量邊修改信息損失的權(quán)重參數(shù)，β是衡量d-可達(dá)性信息損失的權(quán)重參數(shù)。當(dāng)MIN_IN(u)≤din≤MAX_IN(u)時(shí)，Costin(u,din)衡量了刪邊信息損失；當(dāng)din>MAX_IN(u)時(shí)，Costin(u,din)計(jì)算了在添加結(jié)點(diǎn)和邊后所增加的d-可達(dá)結(jié)點(diǎn)對(duì)導(dǎo)致的信息損失?？梢钥闯?，Costin(u,din)同時(shí)考慮了邊修改信息損失和d-可達(dá)性信息損失。相似地，出度匿名信息損失Costout(u,dout)計(jì)算為：

3.5 選擇種子結(jié)點(diǎn)和生成匿名結(jié)點(diǎn)集

已知圖G(V,E)，算法2在選擇種子結(jié)點(diǎn)Seed時(shí)，將具有最大MAX_IN(u)+MAX_OUT(u)的結(jié)點(diǎn)u作為Seed，然后選擇k-1個(gè)與Seed具有最相似的度的結(jié)點(diǎn)來生成VA并進(jìn)行匿名化。通過計(jì)算結(jié)點(diǎn)v和Seed在出、入度上的Manhattan距離來衡量兩結(jié)點(diǎn)的度近似程度，距離越近表明兩結(jié)點(diǎn)的度近似程度越高。

算法3. AnonymizationVertexSet.

輸入：圖G(V,E),種子結(jié)點(diǎn)Seed,匿名參數(shù)k、α和β

輸出：匿名結(jié)點(diǎn)集VA

(1)din←MAX_IN(Seed),dout←MAX_OUT(Seed)；

(2)VA←φ；

(3)VertexList←V中合法的未匿名結(jié)點(diǎn)；

(4)基于Cost(v,din,dout) 升序排列VertexList中結(jié)點(diǎn)；

(5)repeat

(6)v←VertexList.head,將v從VertexList中刪除；

(7) ifv與VA中其他結(jié)點(diǎn)無邊連接 then

(8)VA←VA∪{v}；

(9) end if

(10)until |VA|=k或者VertexList=φ；

(11)returnVA.

已知種子結(jié)點(diǎn)Seed，算法3給出匿名結(jié)點(diǎn)集VA生成算法。在算法3中，合法結(jié)點(diǎn)u需要滿足MIN_IN(u)≤din和MIN_OUT(u)≤dout。如果結(jié)點(diǎn)v與VA中其他結(jié)點(diǎn)具有邊連接，則不加入VA(7行)，保證匿名化結(jié)點(diǎn)v不會(huì)影響VA中其他結(jié)點(diǎn)。給定種子結(jié)點(diǎn)Seed，需要檢查O(n)個(gè)結(jié)點(diǎn)來生成VA，因此算法3的時(shí)間復(fù)雜度為O(n)。

為了獲得最小匿名化信息損失，算法2基于VA計(jì)算最優(yōu)度(din,dout)(8行)，其中din和dout的取值范圍為：

最優(yōu)度(din,dout)是指使得匿名VA中結(jié)點(diǎn)代價(jià)∑u∈VACost(u,din,dout最小化的入度和出度。

3.6 后期匿名處理

當(dāng)算法2停止迭代匿名后，需要后期匿名化標(biāo)記為”unanonymized”和”postprocessing”的結(jié)點(diǎn)(14行)：將剩余結(jié)點(diǎn)的MAX_IN最大值作為din，MAX_OUT最大值作為dout，并通過添加結(jié)點(diǎn)和邊來匿名化這些結(jié)點(diǎn)的度。

當(dāng)基于G中結(jié)點(diǎn)和邊的標(biāo)簽來生成匿名圖Gk時(shí)(15行)，首先將V(Gk)初始化為V(G)，然后將G中標(biāo)記”added”的邊添加進(jìn)E(Gk)中。

4 實(shí)驗(yàn)結(jié)果與分析

本節(jié)對(duì)RPA算法進(jìn)行性能分析和評(píng)價(jià)，采用社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集HepTh和Epinions進(jìn)行測試(數(shù)據(jù)集可在http://snap.stanford.edu/data/下載)。表2給出了實(shí)驗(yàn)數(shù)據(jù)集的統(tǒng)計(jì)信息。除了實(shí)現(xiàn)本文的RPA算法，同時(shí)實(shí)現(xiàn)了文獻(xiàn)[15]中的圖匿名算法(記作Ngr-Degree)進(jìn)行對(duì)比。在Ngr-Degree算法中，將邊修改數(shù)目作為匿名信息損失度量的唯一標(biāo)準(zhǔn)，保證通過較少邊修改數(shù)目來生成度匿名圖。由于只考慮了邊信息損失，因此理論上Ngr-Degree算法會(huì)導(dǎo)致更大的可達(dá)性信息損失。

表2 實(shí)驗(yàn)測試數(shù)據(jù)集統(tǒng)計(jì)信息

實(shí)驗(yàn)測試的軟硬件環(huán)境為：(1)硬件環(huán)境：Intel Core 2 Duo 2.33 GHz CPU，4 GB DRAM 內(nèi)存；(2)操作系統(tǒng)平臺(tái)：Microsoft Windows XP；(3)編程環(huán)境：Java，Eclipse。本實(shí)驗(yàn)測試了圖匿名化執(zhí)行時(shí)間和匿名圖數(shù)據(jù)可用性。RPA算法中權(quán)重參數(shù)默認(rèn)設(shè)定為α=40和β=1。實(shí)驗(yàn)測試中距離閾值d在{2,4,6,|V|}中取值，當(dāng)d=|V|時(shí)，希望匿名圖保持原圖中所有可達(dá)結(jié)點(diǎn)對(duì)間的可達(dá)性。

4.1 圖匿名化執(zhí)行時(shí)間

圖6顯示了圖匿名執(zhí)行時(shí)間隨k值的變化情況。如圖6所示，Ngr-Degree算法的執(zhí)行時(shí)間少于RPA算法，這是因?yàn)镹gr-Degree沒有考慮可達(dá)性信息損失，因此執(zhí)行效率較高。當(dāng)k增大時(shí)，RPA的執(zhí)行時(shí)間降低，符合第5節(jié)中所分析的RPA算法時(shí)間復(fù)雜度。對(duì)于相同k值，d-RPA的執(zhí)行時(shí)間隨著d值的增大而增加。

圖6 圖匿名化執(zhí)行時(shí)間

4.2 可達(dá)性信息損失

圖7 當(dāng)k=20時(shí)，Gk和G之間的可達(dá)性相似度

圖8 Gk和G之間的4-可達(dá)性相似度隨k值變化情況

4.3 結(jié)點(diǎn)和邊信息損失

表3給出了當(dāng)d=2、4、6時(shí)RPA生成匿名圖中所添加的假點(diǎn)數(shù)目。當(dāng)d保持不變時(shí)，隨著k值的增大，假點(diǎn)數(shù)目增加；在相同的k值下，d值越大，假點(diǎn)數(shù)目越少。在匿名圖中，假點(diǎn)只占圖中結(jié)點(diǎn)很小的比例。以數(shù)據(jù)集HepTh為例，當(dāng)k=5和d=4時(shí)，添加的假點(diǎn)數(shù)目為92，而匿名圖中具有度(1, 0)和(0, 1)的結(jié)點(diǎn)數(shù)目為1268，遠(yuǎn)大于假點(diǎn)數(shù)目。

表3 匿名圖中添加的假點(diǎn)數(shù)目

圖9 邊修改信息損失

5 結(jié)束語

本文針對(duì)圖匿名技術(shù)對(duì)于結(jié)點(diǎn)間可達(dá)性的影響問題展開研究，提出了一種可達(dá)性保持圖匿名化算法RPA。RPA算法基本思想是在圖匿名化過程中保持最小d-RPG的完整性，從而實(shí)現(xiàn)結(jié)點(diǎn)間d-可達(dá)性的保持?；谡鎸?shí)數(shù)據(jù)集進(jìn)行了大量實(shí)驗(yàn)測試和分析，驗(yàn)證RPA算法可以保證匿名圖中結(jié)點(diǎn)間的可達(dá)性。

[1]Cheng J,Fu A,and Liu J.K-isomorphism:privacy preserving network publication against structural attacks[C].SIGMOD′10,2010:459-470.

[2]Gao J,Yu J,Jin R,et al.Neighborhood-privacy protected shortest distance computing in cloud [C].SIGMOD Conference,2011:409-420.

[3]Yuan M,Chen L,and Yu P S.Personalized privacy protection in social networks[C].VLDB′10,2010:141-150.

[4]Zou L,Chen L,and Ozsu M.K-automorphism:A general framework for privacy preserving network publication[C].VLDB′09,2009:946-957.

[5]Chen Y and Chen Y.An efficient algorithm for answering graph reachability queries[C].ICDE′08,2008:893-902.

[6]Jin R,Xiang Y,Ruan N,et al.Efficient answering reachability queries on very large directed graphs[C].SIGMOD′08,2008:595-608.

[7]Jin R,Liu L,Ding B and Wang H.Distance-constraint reachability computation in uncertain graphs[C].VLDB′11,2011:551-562.

[8]Nowell D L and Kleinberg J.The link prediction problem for social networks[C].CIKM′03,2003:556-559.

[9]Caragea D,Bahirwani V,Alj W,et al.Ontology-based link prediction in the livejournal social network[C].AAAI′09,2009.

[10]Liu X,Wang B and Yang X.Efficiently anonymizing social networks with reachability preservation[C].Proceedings of the 22th ACM Conference on Information and Knowledge Management (CIKM′13),2013:1613-1618.

[11]Liu K and Terzi E.Towards identity anonymization on graphs[C].SIGMOD′08,2008:93-106.

[12]Hazan E,Safra S,and Schwartz O.On the complexity of approximating k-dimensional matching[C].Approximation,Randomization,and Combinatorial Optimization Algorithms and Techniques,2003:59-70.

[13]Aho A,Garey M,and Ullman J.The transitive reduction of a directed graph[J].SIAM Journal on Computing,1972,1(2):131-137.

[14]Naddef,Denis.50 Years of integer programming 1958-2008[M].New York:Springer,2010:219-241.

[15]Zhou B and Pei J.Preserving privacy in social networks against neighborhood attacks[C].ICDE′08,2008:506-515.

(責(zé)任編輯：劉劃 英文審校：劉飛)

On reachability preserving graph anonymization in social networks

LIU Xiang-yu,AN Yun-zhe,ZHOU Da-hai,XIA Xiu-feng

(College of Computer Science,Shenyang Aerospace University,Shenyang 110136,China)

With increasing privacy concerns for social networks,graph anonymization has been extensively studied and numerous algorithms are proposed.The goal of graph anonymization is to avoid disclosure of privacy in social networks through graph modifications meanwhile to preserve data utility of the anonymized graph for social network analysis and graph queries.Reachability is an important data utility of the anonymized graph as reachability queries are not only common on graph databases,but they also serve as fundamental operations for many other graph queries.In practice,the reachability of vertices in the anonymized graph is nontrivially distorted.In this work,we solved the problem by designing a reachability preserving graph anonymization (RPA for short)algorithm.The main idea of RPA is to find a minimal subgraph that preserves the reachability of the vertices and keeps it unchanged during the anonymization.Extensive experiments on real datasets illustrate that anonymized social networks generated by our method can be used to answer reachability queries with high accuracy.

social networks;privacy;anonymization;reachability

2095-1248(2015)06-0050-09

2015-07-01

國家自然科學(xué)基金青年基金(項(xiàng)目編號(hào)：61502316)

劉向宇(1981-)，男，遼寧鐵嶺人，講師，博士，主要研究方向：數(shù)據(jù)隱私保護(hù)，E-mail：neulxy@gmail.com。

TP301

A

10.3969/j.issn.2095-1248.2015.06.006