社交網(wǎng)絡(luò)下的不確定圖隱私保護(hù)算法*

吳振強(qiáng),胡 靜,田堉攀,史武超,顏 軍

1(現(xiàn)代教學(xué)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室(陜西師范大學(xué)),陜西 西安 710062)

2(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,陜西 西安 710119)

1 引 言

隨著互聯(lián)網(wǎng)技術(shù)的日益成熟和快速普及,越來越多的用戶通過社交網(wǎng)絡(luò)平臺(tái)進(jìn)行溝通并共享信息,導(dǎo)致社交網(wǎng)絡(luò)積累了大量的用戶行為數(shù)據(jù).這些數(shù)據(jù)中包含了大量的個(gè)人敏感信息,如身份信息、社會(huì)關(guān)系信息等,這些敏感信息容易引起不法分子的關(guān)注并成為安全攻擊的目標(biāo).例如2016年5月19日,美國(guó)社交網(wǎng)站LinkedIn宣布,有一個(gè)叫“peace”的黑客組織在黑市上以 5比特幣的售價(jià)公開銷售 1.67億個(gè)領(lǐng)英用戶登錄信息,其中有1.17億包括電子郵件和密碼;同年 6月初,同樣是代號(hào)為“peace”的黑客稱已經(jīng)拿到了全球第二大的社交網(wǎng)站MySpace的3.6億用戶賬號(hào)以及4.27億密碼,并且在暗網(wǎng)上以6個(gè)比特幣的價(jià)格公開出售[1],使得用戶的身心和財(cái)產(chǎn)安全遭到嚴(yán)重侵犯,除此之外,一些不法分子甚至利用這些賬號(hào)信息在用戶的親友之間行騙.因此,如何在方便用戶使用社交網(wǎng)絡(luò)的同時(shí),保護(hù)好用戶的個(gè)人敏感信息不被泄露成為了急需解決的社會(huì)問題.

社交網(wǎng)絡(luò)由多種角色構(gòu)成,它們之間的關(guān)系錯(cuò)綜復(fù)雜且相互影響.傳統(tǒng)數(shù)據(jù)的隱私保護(hù)方法已經(jīng)不適用于社交網(wǎng)絡(luò)中的隱私信息保護(hù),對(duì)社交網(wǎng)絡(luò)的研究不僅要關(guān)注每個(gè)社會(huì)角色的屬性,同時(shí)也要關(guān)注這些角色之間的關(guān)系.為了準(zhǔn)確描述社交網(wǎng)絡(luò)中實(shí)體之間的關(guān)系,可以將社交網(wǎng)絡(luò)抽象成圖(graph)結(jié)構(gòu),每個(gè)社會(huì)角色用節(jié)點(diǎn)表示,角色之間的關(guān)系通常用邊來表示,角色之間關(guān)聯(lián)程度可以通過對(duì)邊進(jìn)行加權(quán)重來表示[2].因此,對(duì)社交網(wǎng)絡(luò)的研究可以轉(zhuǎn)化為對(duì)圖結(jié)構(gòu)的研究.由于社交網(wǎng)絡(luò)中包含許多個(gè)人的敏感信息,將其抽象為圖結(jié)構(gòu)后,圖中的節(jié)點(diǎn)和邊也會(huì)涉及到個(gè)人隱私信息,因此,通過研究圖結(jié)構(gòu)的隱私保護(hù)來實(shí)現(xiàn)社交網(wǎng)絡(luò)隱私保護(hù)的目的.目前,社交網(wǎng)絡(luò)隱私保護(hù)方法可分為 5類.(1) 標(biāo)識(shí)符替換法.標(biāo)識(shí)符替換是采用偽名的思想,用合成的標(biāo)識(shí)符來替換掉身份證號(hào)或名字等唯一標(biāo)識(shí)屬性,這種方法實(shí)現(xiàn)簡(jiǎn)單但容易遭受背景信息攻擊.Backstrom[3]等人提出在發(fā)布真實(shí)圖數(shù)據(jù)之前用合成標(biāo)識(shí)符替換可識(shí)別屬性的隱私保護(hù)技術(shù),但是這種方法容易受到背景知識(shí)的攻擊,攻擊者可以根據(jù)頂點(diǎn)的結(jié)構(gòu)特征推斷出頂點(diǎn)的身份信息.(2) 差分隱私法.差分隱私[4]是一種具有嚴(yán)格可證明的數(shù)學(xué)定義和可量化評(píng)估的隱私保護(hù)模型,將差分隱私應(yīng)用到社交網(wǎng)絡(luò)圖結(jié)構(gòu)中,可以提供一種嚴(yán)格、有效的量化評(píng)估方法.Hay等人[5]基于差分隱私技術(shù)提出圖結(jié)構(gòu)中節(jié)點(diǎn)和邊差分隱私,其中邊的差分隱私相對(duì)較為簡(jiǎn)單,因此應(yīng)用更為廣泛.Day等人[6]基于聚類和累積直方圖提出了兩種在節(jié)點(diǎn)差分隱私下發(fā)布度分布的方法.Karwa等人[7]提出了一種嚴(yán)格、高效的邊差分隱私保護(hù)方法來發(fā)布實(shí)用性高的網(wǎng)絡(luò)數(shù)據(jù)統(tǒng)計(jì)信息.Task等人[8]提出了圖結(jié)構(gòu)中出度差分隱私,實(shí)現(xiàn)簡(jiǎn)單,但相較于節(jié)點(diǎn)保護(hù)能力較弱.(3) 圖聚類方法.圖的聚類[9]是將多個(gè)節(jié)點(diǎn)或邊聚合成一個(gè)超級(jí)節(jié)點(diǎn)集合,對(duì)外只公布超級(jí)節(jié)點(diǎn)的統(tǒng)計(jì)信息,從而保護(hù)了節(jié)點(diǎn)內(nèi)用戶的隱私.Hay等人[10]針對(duì)背景信息攻擊提出一種基于節(jié)點(diǎn)聚類實(shí)現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)匿名化的隱私保護(hù)方法.考慮到社交網(wǎng)絡(luò)中的關(guān)系對(duì)應(yīng)圖結(jié)構(gòu)中的邊,這些連接關(guān)系也會(huì)泄露個(gè)人隱私信息.Zheleva和Getoor[11]針對(duì)關(guān)系鏈識(shí)別攻擊提出了一種基于邊聚類的隱私保護(hù)方法.但聚類在一定程度上會(huì)降低原社交網(wǎng)絡(luò)圖數(shù)據(jù)的實(shí)用性,因此在滿足隱私保護(hù)的前提下,為了盡可能地保持原圖數(shù)據(jù)的實(shí)用性,引入邊/頂點(diǎn)修改技術(shù).(4) 邊/頂點(diǎn)修改技術(shù)是對(duì)圖的局部進(jìn)行修改來實(shí)現(xiàn)隱私保護(hù).針對(duì)社交網(wǎng)絡(luò)中角色關(guān)系復(fù)雜多樣的特點(diǎn),可以通過隨機(jī)修改圖中部分邊來實(shí)現(xiàn)社交網(wǎng)絡(luò)圖的匿名化,進(jìn)而實(shí)現(xiàn)隱私保護(hù)的目的.隨機(jī)邊修改技術(shù)主要包括隨機(jī)增添和刪除邊、隨機(jī)旋轉(zhuǎn)邊和隨機(jī)交換邊3種.Ying等人[12]研究了不同的隨機(jī)方法對(duì)于頂點(diǎn)之間關(guān)系的影響,提出了保護(hù)原始圖特征譜的算法.攻擊者依據(jù)原圖中節(jié)點(diǎn)的度信息,仍可以重新定義原圖數(shù)據(jù)信息.針對(duì)鏈接攻擊,Liu和Terzi[13]提出了k-度匿名概念.k-度匿名模型是k-匿名[14]在圖上的應(yīng)用與拓展.設(shè)圖G=(V,E)中的任意一個(gè)節(jié)點(diǎn)度數(shù)至少與k–1個(gè)節(jié)點(diǎn)的度數(shù)相同,則該圖為k-度匿名圖.(5) 不確定圖方法.不確定圖方法是向原社交網(wǎng)絡(luò)圖中的部分節(jié)點(diǎn)之間隨機(jī)添加或刪除小概率邊來注入不確定性.通過對(duì)數(shù)據(jù)更小的擾動(dòng)變化既可以實(shí)現(xiàn)隱私保護(hù),又可以保持原數(shù)據(jù)效用性.2012年,Boldi等人[15]首次提出了(k,ε)-混淆算法,該方法在抗頂點(diǎn)身份攻擊的同時(shí)保證了圖結(jié)構(gòu)數(shù)據(jù)的最小化失真;2013年,Mittal等人[16]提出了基于隨機(jī)游走的不確定圖數(shù)據(jù)發(fā)布方法,該方法可防止鏈接攻擊;2014年,Nguyen等人[17]提出了方差最大化的方法來衡量隱私與效用之間的關(guān)系;2015年,Nguyen等人[18]在前期工作的基礎(chǔ)上又提出了基于不確定鄰接矩陣UAM的通用匿名模型,并將UAM引入到方差最大化算法中.為了提高不確定圖方法的隱私保護(hù)效果,胡靜[19]利用邊差分隱私實(shí)現(xiàn)了對(duì)原圖基于任何背景知識(shí)攻擊的隱私保護(hù),并且經(jīng)過差分隱私的后置處理方法,提高了隱私保護(hù)的數(shù)據(jù)效用.

目前,不確定圖已成為一種新的隱私保護(hù)方法,它的主要原理是將不確定性注入到社交網(wǎng)絡(luò)圖的邊中,發(fā)布經(jīng)混淆后的不確定圖來達(dá)到隱私保護(hù)的目的.該方法通過為圖中的邊分配概率值來實(shí)現(xiàn)隱私保護(hù),同時(shí)對(duì)原圖數(shù)據(jù)改變較小,一定程度上保持了較高的原數(shù)據(jù)效用,相較于完全去除或添加邊,保護(hù)效果更好.

本文針對(duì)社交網(wǎng)絡(luò)圖的隱私保護(hù),提出了兩種不確定圖隱私保護(hù)算法:基于差分隱私的不確定圖邊概率賦值算法和基于三元閉包的不確定圖邊概率分配算法.為了對(duì)現(xiàn)有算法和本文提出的算法進(jìn)行統(tǒng)一的隱私分析,我們采用邊熵來衡量算法的隱私保護(hù)程度.同時(shí),針對(duì)社交網(wǎng)絡(luò)的度量問題,提出了一種基于網(wǎng)絡(luò)結(jié)構(gòu)熵的圖結(jié)構(gòu)數(shù)據(jù)效用性的度量算法,該算法與k度匿名模型相比,能夠更加精確地反映出網(wǎng)絡(luò)結(jié)構(gòu)隱私性的變化過程.

本文第1節(jié)介紹背景和相關(guān)工作.第2節(jié)介紹本文算法的相關(guān)基礎(chǔ)知識(shí).第3節(jié)基于不確定圖中邊概率的賦值提出兩種社交網(wǎng)絡(luò)圖隱私保護(hù)算法:基于差分隱私的不確定圖邊概率賦值算法和三元閉包的不確定圖邊概率分配算法.第 4節(jié)對(duì)本文提出的兩種算法分別從數(shù)據(jù)的隱私性和效用性方面進(jìn)行實(shí)驗(yàn)驗(yàn)證分析.第 5節(jié)提出一種基于網(wǎng)絡(luò)結(jié)構(gòu)熵的圖結(jié)構(gòu)數(shù)據(jù)效用性度量算法.第6節(jié)總結(jié)全文并展望下一步工作.

2 相關(guān)基礎(chǔ)知識(shí)

2.1 差分隱私的基本定義和相關(guān)概念

定義1(差分隱私).存在兩個(gè)相鄰數(shù)據(jù)集D,D′和算法K,K(D)表示算法K在數(shù)據(jù)集D上的輸出集合,O是算法K所有輸出值的集合,若算法K在數(shù)據(jù)集D和D′上任意輸出結(jié)果為滿足下面不等式(1):

則算法K滿足ε-差分隱私.ε稱為隱私保護(hù)預(yù)算,ε的取值決定了保護(hù)效果,ε取值的大小與保護(hù)效果成正比,與數(shù)據(jù)失真程度成反比.差分隱私以其嚴(yán)格的數(shù)學(xué)定義為隱私的評(píng)價(jià)提供了理論依據(jù).

差分隱私實(shí)現(xiàn)機(jī)制包括:指數(shù)機(jī)制、拉普拉斯機(jī)制和高斯機(jī)制.其中,指數(shù)機(jī)制一般應(yīng)用于非數(shù)值類數(shù)據(jù),拉普拉斯機(jī)制和高斯機(jī)制適用于數(shù)值型數(shù)據(jù)的隱私保護(hù).

定義2(鄰近圖).給定圖G1=(V1,E1),G2=(V2,E2),若在G1,G2中有 |V1⊕V2|+ |E1⊕E2|= 1 ,則稱G1、G2為鄰近圖.

本文中,由于V1=V2,只要 |E1⊕E2|= 1 ,即E1與E2的漢明距離為 1,我們就稱G1、G2為鄰近圖,如圖 1所示,圖1(a)和圖1(b)所示為鄰近圖.

Fig.1 The example of neighboring graphs圖1 鄰近圖示例

定義3(敏感度).給定一個(gè)函數(shù)f:G→G″,其中,G、G′具有相同的頂點(diǎn)集合,函數(shù)f的全局敏感度為

其中,G1、G2是鄰近圖,G″為經(jīng)過隨機(jī)算法后的輸出圖,f是查詢函數(shù),表示對(duì)于G1、G2中的邊ei,查詢邊ei是否存在于G1和G2中,圖 1(a)和圖 1(b)中的Δf=2.

定義4(邊差分隱私).給定一種隨機(jī)算法M,Range(M)為算法M的取值范圍,若算法M在鄰近圖G1、G2上的輸出結(jié)果S(S∈Range(M))滿足:

則稱算法M滿足ε-差分隱私,其中,ε表示隱私保護(hù)程度,Pr[.]表示算法M的隨機(jī)性.

為了實(shí)現(xiàn)邊差分隱私,通過拉普拉斯分布產(chǎn)生的噪聲值加入到真實(shí)輸出值實(shí)現(xiàn)邊數(shù)據(jù)的擾動(dòng),從而實(shí)現(xiàn)了差分隱私保護(hù).

定義5(Laplace機(jī)制).對(duì)于函數(shù)f:G→G′,若算法M的輸出結(jié)果滿足下列等式,則稱算法M是滿足ε-差分隱私的.

其中,Lap(Δf/ε)是添加到查詢結(jié)果中的期望值為0,位置參數(shù)是Δf/ε的拉普拉斯分布的噪聲.同時(shí),噪聲值的大小與敏感度Δf和隱私預(yù)算ε有關(guān).這種通過添加服從拉普拉斯的噪聲值實(shí)現(xiàn)差分隱私的機(jī)制稱為L(zhǎng)aplace機(jī)制.

2.2 不確定圖

定義 6(不確定圖).給定一個(gè)圖G=(V,E),如果映射p:Vp→[0,1]是邊集中每條邊存在的概率函數(shù),那么圖G′=(V,p)是關(guān)于圖G的不確定圖,其中,Vp表示集合V中所有可能的頂點(diǎn)對(duì),即Vp={(vi,vj)|1≤i

2.3 三元閉包

定義 7(鄰近潛在邊). Leskovec等人[20]指出,真實(shí)圖中節(jié)點(diǎn)之間的鏈接概率隨著它們層級(jí)之間相對(duì)距離的增加而減小,這些邊的存在可以減少基于最短路徑的統(tǒng)計(jì).Vázquez[21]提出最近鄰居可以解釋鄰居間的聚集系數(shù)、平均度和度分布的能量規(guī)律,這些屬性與對(duì)社交網(wǎng)絡(luò)圖的觀察結(jié)果完全一致.

三元閉包的基本原則:如果兩個(gè)人有共同的朋友,這兩個(gè)人將來成為朋友的可能性就會(huì)增加.例如,節(jié)點(diǎn)B和節(jié)點(diǎn)C具有共同的朋友A,則B和C成為朋友的概率會(huì)增加.類似地,節(jié)點(diǎn)A和節(jié)點(diǎn)E之間也會(huì)產(chǎn)生關(guān)聯(lián)邊,如圖 2所示.將三元閉包理論引入到社交網(wǎng)絡(luò)研究中,可以形成三角形網(wǎng)絡(luò)結(jié)構(gòu),利用三角形結(jié)構(gòu)特性將原圖轉(zhuǎn)變?yōu)椴淮_定圖.

Fig.2 The theory of triadic closure圖2 三元閉包理論模型

2.4 網(wǎng)絡(luò)結(jié)構(gòu)熵

熵表示系統(tǒng)的混亂程度.網(wǎng)絡(luò)結(jié)構(gòu)熵是對(duì)整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)是否有序的度量.網(wǎng)絡(luò)結(jié)構(gòu)熵Entropy定義如下:

其中,di為節(jié)點(diǎn)vi的度.當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)為全連接圖時(shí),其值最大,反之,無邊相連的孤立節(jié)點(diǎn)圖,其值最小.

2.5k-度匿名

k-度匿名模型是k-匿名在圖上的應(yīng)用與拓展,由Liu等人[13]首次提出,相關(guān)概念定義如下.

(1)k-匿名向量.如果一個(gè)向量中的每個(gè)值在該向量中出現(xiàn)的次數(shù)至少是k次,則這個(gè)向量被稱作k-匿名向量.例如向量v=[4,4,3,3,3],則該向量為2-匿名向量.

(2)k-度匿名圖.G=(V,E)表示一個(gè)圖,如果這個(gè)圖的度序列所組成的向量是一個(gè)k-匿名向量,則該圖為k-度匿名圖.

3 基于不確定圖的隱私保護(hù)算法

本節(jié)主要介紹兩種基于不確定圖邊概率賦值的隱私保護(hù)算法,并分別對(duì)其給出詳細(xì)介紹.基于差分隱私的不確定圖邊概率賦值算法(簡(jiǎn)稱差分隱私法)提供了嚴(yán)格可證明的隱私保護(hù),并在一定程度上保護(hù)了數(shù)據(jù)效用.基于三元閉包的不確定圖邊概率分配算法(簡(jiǎn)稱三元閉包法)不僅實(shí)現(xiàn)了隱私保護(hù)的目的,而且有約束的分配邊概率可以保持較高的數(shù)據(jù)效用.

3.1 差分隱私法

下面首先將不確定圖的構(gòu)造過程抽象為一個(gè)模型,然后在該模型下提出一種基于差分隱私技術(shù)實(shí)現(xiàn)不確定圖邊概率賦值的隱私保護(hù)(uncertain graph based on differential privacy,簡(jiǎn)稱UGDP)模型,并對(duì)該模型進(jìn)行說明.然后給出UGDP算法的偽代碼并進(jìn)行分析.最后,證明了UGDP算法滿足差分隱私.

1) 不確定圖模型

Fig.3 Uncertain graph construction model of UGDP algrothm圖3 UGDP算法的不確定圖構(gòu)造模型

該模型(如圖3所示)包括3個(gè)部分,第1部分和第3部分為算法的輸入和輸出,其中,算法的輸入為原始數(shù)據(jù)圖,輸出為不確定圖,中間部分是該模型的主要環(huán)節(jié),研究者可以根據(jù)不同的需求提出不同的隱私保護(hù)算法來實(shí)現(xiàn)不確定圖的隱私保護(hù).在該模型下,我們提出了基于差分隱私的不確定圖邊概率賦值算法UGDP.

2) UGDP算法

UGDP算法是利用差分隱私技術(shù)來實(shí)現(xiàn)不確定圖邊概率賦值的隱私保護(hù)算法,算法的執(zhí)行框如圖 4所示,主要由以下4步組成.

Fig.4 The UGDP algorithm圖4 UGDP算法

(1) 利用 Laplace機(jī)制進(jìn)行加噪,產(chǎn)生的噪聲表示為Y=(y1,y2,…,yi,…,yN),將產(chǎn)生的噪聲加入圖G1或G2中,得到噪聲圖.

(2) 為了構(gòu)造不確定圖,每個(gè)噪聲值yi對(duì)應(yīng)一個(gè)概率值pi,概率值pi=Pr[yi]=F(yi).

(3) 將概率值pi加入到圖G1或G2中構(gòu)成不確定圖,將概率值pi作為頂點(diǎn)和頂點(diǎn)之間存在邊的概率.

其中,g(x)是服從期望值μ、位置參數(shù)b的拉普拉斯分布.

(4) 在進(jìn)行數(shù)據(jù)發(fā)布時(shí),為了更好地保護(hù)圖中的隱私信息,將鄰近不確定G′作為發(fā)布圖.

算法詳細(xì)描述如算法1所示.

算法1.UGDP算法.

定理.UGDP算法滿足差分隱私.

證明:令f(.)為函數(shù)f:G→G″,G″是算法輸出的不確定圖,G1、G2為鄰近圖即圖中邊的漢明距離為1.PG1表示UGDP(G1,f,ε)的概率密度函數(shù),PG2表示UGDP(G2,f,ε)的概率密度函數(shù).概率和噪聲的關(guān)系為yi～pi.G3是算法過程中得到的噪聲圖.因?yàn)樵肼晥D到不確定圖的過程符合差分隱私的后置處理技術(shù),因此為了證明 UGDP算法滿足差分隱私,只需要證明原圖到噪聲圖的過程滿足差分隱私即可.具體證明過程如下.

由于UGDP算法是在符合不確定圖隱私的同時(shí)滿足差分隱私,具有雙重的隱私保護(hù)效果,因此,UGDP算法具有較強(qiáng)的隱私保護(hù)的特征.在隱私性度量上我們采取差分隱私的度量方式,即用隱私預(yù)算ε來度量隱私保護(hù)程度.隱私預(yù)算ε越小,噪聲的取值范圍越廣,噪聲值對(duì)應(yīng)的概率的取值也越廣,在邊混淆時(shí)達(dá)到的混淆程度越好,因此隱私保護(hù)效果越好.反之,隱私預(yù)算ε越大,噪聲的取值范圍越窄,噪聲值對(duì)應(yīng)的概率的取值也越窄,在邊混淆時(shí)達(dá)到的混淆程度較差,因此隱私保護(hù)效果較差.

本文提出的 UGDP算法與原有的不確定圖算法相比,在滿足不確定圖的同時(shí)滿足差分隱私的所有特征,尤其它是一種嚴(yán)格可證明的隱私保護(hù)算法,然而,該算法也存在某些局限性,如數(shù)據(jù)的低可用性問題.

3.2 三元閉包法

本節(jié)首先構(gòu)建不確定圖模型,并在該模型下提出一種基于三元閉包的不確定圖邊概率分配算法來實(shí)現(xiàn)圖的匿名化,然后對(duì)該模型的 3個(gè)主要流程詳細(xì)描述并給出該算法的偽代碼.該算法在實(shí)現(xiàn)隱私保護(hù)的同時(shí)保持了原數(shù)據(jù)的效用性.

1) 基于三元閉包的不確定圖算法模型

如圖5所示,該模型包括5個(gè)部分,第1部分和第5部分為算法的輸入和輸出,其中,算法的輸入為原始數(shù)據(jù)圖,輸出為不確定圖,中間部分是該模型的主要環(huán)節(jié),該環(huán)節(jié)分為3個(gè)步驟,具體內(nèi)容詳見后續(xù)的算法描述.

Fig.5 Uncertain graph based on triadic closure algorithm圖5 基于三元閉包的不確定圖構(gòu)造模型

2) 算法描述

對(duì)于一個(gè)社交網(wǎng)絡(luò)圖G,它的點(diǎn)集為V,邊集為E.

(1) 加邊

該過程(如圖6所示)首先集中在收集圖中所需的信息以獲得節(jié)點(diǎn)集V和一個(gè)邊集E.我們隨機(jī)選擇點(diǎn)u,v∈V且邊(u,v)?E,若兩點(diǎn)之間的距離dis(u,v)等于2,則將邊(u,v)加到圖G中.如圖6所示,最多可以增加3條邊.

Fig.6 Add-edges圖6 加邊

(2) 確定三角形數(shù)量

當(dāng)添加邊(u,v)時(shí),這個(gè)邊與其附近的兩個(gè)鄰近邊可以形成一個(gè)三角形,繼續(xù)執(zhí)行上一步,可以得到多個(gè)三角形.為了得到需要的三角形,在選擇三角形時(shí)必須附加一些約束條件.如果兩個(gè)三角形具有公共邊,必須選擇一個(gè)并放棄一個(gè).最終得到一個(gè)三角形集合,該集合中任意兩個(gè)三角形沒有公共邊.例如,在圖7中,當(dāng)添加邊AE和邊BE時(shí),得到ΔAED和ΔBEC.然后判斷兩個(gè)三角形是否具有公共邊.如圖7所示,這兩個(gè)三角形沒有公共邊,則可以將邊AE和邊BE添加到圖中.與邊AE和邊BE相反,邊CD被放棄,因?yàn)榘ㄟ匒E的ΔAED與ΔDEC具有相同邊ED.

Fig.7 Determine the triangle圖7 確定三角形數(shù)量

詳細(xì)的描述如算法2和算法3所示.

算法2.加邊和選取三角形.

算法3.注入不確定.

(3) 注入不確定性

對(duì)三角形集合中每個(gè)三角形的3條邊隨機(jī)分配概率,為了使原圖的邊概率保持不變,本文規(guī)定每個(gè)三角形3條邊的概率和,且原圖中不屬于三角形的邊的概率值為 1.通過向所有邊注入概率值,可以將原圖轉(zhuǎn)換為不確定圖.當(dāng)所有的邊完成概率賦值后,可以得到,E等于原圖中邊的個(gè)數(shù).通過對(duì)邊注入不G確定性生成的不確定圖如圖8所示.

Fig.8 Injecting probability圖8 注入不確定性

通過上述流程,我們?cè)谠黾蛹s束的條件下對(duì)原圖G注入不確定性,得到不確定圖G′.

3) 算法分析

為了實(shí)現(xiàn)較高的隱私保護(hù)效果,將原圖轉(zhuǎn)換為不確定圖,則攻擊者按組合方法只能以比較低的概率從不確定圖中恢復(fù)出原圖,因此本算法能夠?qū)崿F(xiàn)對(duì)原圖的概率性保護(hù).在基于三元閉包的不確定圖邊概率分配算法中,首先基于三元閉包原理對(duì)原圖加邊,實(shí)現(xiàn)對(duì)原圖的修改.然后,選擇加邊形成的三角形,對(duì)其三邊分配一定的概率值得到一個(gè)不確定圖.若具有概率值的三角形越多,則能夠得到原圖的概率越低,因此該算法能夠?qū)υ瓐D進(jìn)行隱私保護(hù).在轉(zhuǎn)換過程中,對(duì)于三角形的概率分配進(jìn)行限制,使得三邊的概率之和等于 2,目的是確保加邊前后的邊概率之和保持不變.在這種約束條件下,得到的不確定圖的邊數(shù)概率之和等于原圖的邊數(shù)概率之和.同時(shí),這種約束條件可以提高不確定圖的數(shù)據(jù)效用.因此,基于三元閉包的不確定圖算法既能實(shí)現(xiàn)隱私保護(hù),又保持了較高的數(shù)據(jù)效用性.

提出的基于三元閉包的不確定圖邊概率分配算法,通過加邊構(gòu)建三角形集合并對(duì)選擇后的三角形集合中所有的邊注入不確定性,將原社交網(wǎng)絡(luò)圖轉(zhuǎn)化為不確定圖,進(jìn)而實(shí)現(xiàn)對(duì)社交網(wǎng)絡(luò)的隱私保護(hù).該算法在對(duì)社交網(wǎng)絡(luò)隱私保護(hù)的同時(shí)保持了原網(wǎng)絡(luò)數(shù)據(jù)效用,與其他已有算法相比,在處理簡(jiǎn)單的社交網(wǎng)絡(luò)數(shù)據(jù)時(shí),該算法運(yùn)行效率更高.由于該算法是對(duì)網(wǎng)絡(luò)圖的局部進(jìn)行擾動(dòng),所以對(duì)于更復(fù)雜的網(wǎng)絡(luò)圖還需要進(jìn)一步加以探索.

4 分析與比較

為了對(duì)不同隱私保護(hù)方法的隱私效果進(jìn)行評(píng)價(jià),下面利用不確定圖的邊概率信息,引入邊熵來衡量所發(fā)布不確定圖的隱私保護(hù)程度,并以此為評(píng)價(jià)依據(jù)衡量變換前后隱私程度的變化情況.同時(shí),為了驗(yàn)證算法對(duì)數(shù)據(jù)的效用性影響程度,又定義了一些圖統(tǒng)計(jì)指標(biāo)來說明本文算法的數(shù)據(jù)效用性.然后,利用Python語(yǔ)言及第三方功能包 NetworkX對(duì)本文算法進(jìn)行程序編程和仿真實(shí)驗(yàn).實(shí)驗(yàn)數(shù)據(jù)分為兩部分,一部分為真實(shí)數(shù)據(jù)集,一部分為合成數(shù)據(jù)集.真實(shí)數(shù)據(jù)集來自于Karate和Dolphin俱樂部,合成數(shù)據(jù)集分別為200和500個(gè)節(jié)點(diǎn),連接概率為0.2的隨機(jī)網(wǎng)絡(luò)圖.為了減少隨機(jī)性,實(shí)驗(yàn)進(jìn)行了10次模擬取平均值.

4.1 隱私性度量

信息熵是信息論中用于度量信息量的一個(gè)概念,一個(gè)系統(tǒng)越是有序,信息熵就越低;反之,一個(gè)系統(tǒng)越是混亂,信息熵就越高,在不確定圖隱私度量中,由于不確定圖的邊具有很強(qiáng)的隨機(jī)性,我們引入邊熵Ente來衡量隱私保護(hù)效果.根據(jù)邊的不確定程度,使用邊熵來衡量不確定圖的不確定性,即不確定圖對(duì)原始圖的隱私保護(hù)程度,不確定圖的邊熵定義如以下公式所示.

其中,ei∈G′,p(ei)是該條邊存在的概率.

其中,Ente為不確定圖的邊熵,Ente值越大,表示不確定圖的不確定程度越大,對(duì)應(yīng)隱私保護(hù)方法的隱私保護(hù)效果越好.

4.2 數(shù)據(jù)效用性度量

根據(jù)文獻(xiàn)[15,18]中提出的相關(guān)指標(biāo)來度量算法的數(shù)據(jù)效用性,其中,NE表示圖中邊的個(gè)數(shù),AD表示圖中節(jié)點(diǎn)的平均度,DV表示圖中節(jié)點(diǎn)的度方差.

在圖數(shù)據(jù)中,我們用d1,d2,…,dn來表示圖中節(jié)點(diǎn)度的序列.由于不確定圖中每條邊是以概率的形式出現(xiàn)的,因此我們不能直接用確定圖中節(jié)點(diǎn)的度來表示不確定圖中節(jié)點(diǎn)的度.在不確定圖中,節(jié)點(diǎn)度的序列d1,d2,…,dn是一些隨機(jī)變量.我們利用節(jié)點(diǎn)的期望度來表示不確定圖中節(jié)點(diǎn)的度,也就是說,對(duì)于任意的節(jié)點(diǎn)v∈V,節(jié)點(diǎn)v的期望度是與它相連的邊的概率之和,見等式(11).

在公式(11)中我們規(guī)定i=v或者j=v且i≠j.

原始圖中NE、AD的計(jì)算見公式(12)、公式(13),不確定圖中NE′、AD′的計(jì)算見公式(15)、公式(16),其中,DV在原始圖與不確定圖中的計(jì)算方式一致,見公式(14).

4.3 隱私性分析

為了對(duì)本文所提出的方法和已有方法的隱私性進(jìn)行統(tǒng)一度量,我們利用邊熵的變化情況來說明隱私保護(hù)效果.表1為UGDP算法邊熵的變化情況,表2為三元閉包法中邊熵的變化情況,表3為(k,ε)-混淆算法中邊熵的變化情況.

邊熵是用來度量圖的不確定性程度,邊熵的值越大表明圖的不確定程度越大.表1表示的是UGDP算法中邊熵的變化情況,隨著節(jié)點(diǎn)個(gè)數(shù)的增加,邊熵也對(duì)應(yīng)增大,表明整個(gè)圖的不確定程度在加大,即隱私保護(hù)效果越好.由于 UGDP算法是符合差分隱私的,根據(jù)差分隱私的特性可知,隱私預(yù)算ε越小,則隱私保護(hù)程度越高.但是,在利用UGDP算法將確定圖轉(zhuǎn)化為不確定圖時(shí),邊概率的賦值服從拉普拉斯分布,具有一定的隨機(jī)性,因此,邊熵的變化也具有隨機(jī)性,與差分隱私的隱私保護(hù)程度不一定完全相符,也就是說,隱私預(yù)算越小,邊熵的值不一定越大.

Table 1 The changes of edge-entropy in UGDP algorithm表1 UGDP算法中邊熵的變化情況

基于三元閉包的不確定圖邊概率分配算法在生成不確定圖的過程中,對(duì)原圖進(jìn)行加邊,然后對(duì)選擇后的三角形的邊賦予概率值.在表 2中,隨著邊數(shù)的增加,得到的不確定圖的邊熵也在增加,表現(xiàn)為同步增長(zhǎng)趨勢(shì).這種趨勢(shì)反映了圖隱私保護(hù)的效果越來越好,同時(shí)證明了三元閉包法能夠?qū)崿F(xiàn)隱私保護(hù)的目的m為不確定圖的生成過程中總共添加的邊數(shù),c為調(diào)節(jié)加邊數(shù)的因子,實(shí)際添加的邊數(shù)為m.c.

Table 2 The changes of edge-entropy in triadic closure algorithm表2 三元閉包法中邊熵的變化情況

(k,ε)-混淆算法將確定圖轉(zhuǎn)化為不確定圖時(shí)可以保持較好的數(shù)據(jù)效用性[18],為了把該算法達(dá)到的隱私保護(hù)效果與本文提出的算法進(jìn)行直觀的對(duì)比,下面采用邊熵來進(jìn)行隱私性度量.表 3為(k,ε)-混淆算法中邊熵的變化情況,由于篇幅和不同參數(shù)組合具有的多種可能性,下面只列出(k,ε)-混淆算法的一種情形來說明隱私保護(hù)效果,同時(shí)隱私度量的主要參數(shù)即混淆級(jí)別k的取值分別為10和20,其他參數(shù)分別為ε=0.1,c=1,q=0.01.

Table 3 The changes of edge-entropy in (k,ε)-obfuscation algorithm表3 (k,ε)-混淆算法中邊熵的變化情況

通過表1和表3的對(duì)比,如果利用邊熵來度量算法的隱私性,則UGDP算法在隱私保護(hù)程度上優(yōu)于(k,ε)-混淆算法,可以達(dá)到較好的隱私保護(hù)效果.通過表2和表3的對(duì)比,(k,ε)-混淆算法優(yōu)于三元閉包方法,可以達(dá)到較好的隱私保護(hù)效果.

4.4 數(shù)據(jù)效用性分析

在隱私保護(hù)的同時(shí),我們通過NE、AD、DV對(duì)數(shù)據(jù)效用性進(jìn)行了測(cè)量,見表4～表7.表4和表5列出UGDP算法的數(shù)據(jù)效用性.在表4中,對(duì)原始數(shù)據(jù)圖的數(shù)據(jù)效用及ε=0.1時(shí)UGDP算法生成的不確定圖的數(shù)據(jù)效用進(jìn)行了對(duì)比,可以看出,UGDP算法的數(shù)據(jù)效用性較低.同時(shí),表 5表示的是不同隱私預(yù)算ε下的數(shù)據(jù)效用性的對(duì)比,我們得出隱私預(yù)算ε越大,隱私保護(hù)程度越差,數(shù)據(jù)效用性相對(duì)較好的結(jié)論.

表6列出的是三元閉包法的數(shù)據(jù)效用性.在表6中,通過三元閉包法得到的不確定圖與原圖比較可以得出,在度量指標(biāo)NE、AD中,數(shù)據(jù)效用性保持不變,這說明,通過該方法得到的不確定圖具有較好的數(shù)據(jù)效用性.同時(shí),DV在網(wǎng)絡(luò)中明顯增加,這說明,對(duì)原圖進(jìn)行修改時(shí)節(jié)點(diǎn)的度發(fā)生了變化.

Table 4 Comparison of data utility between uncertain graphs generated by UGDP algorithm whenε=0.1 and original graph表4 原始圖與ε=0.1時(shí)UGDP生成的不確定圖的數(shù)據(jù)效用性比較

Table 5 Comparison of data utility whenε=0.01 andε=1 in uncertain graphs generated by UGDP algorithm表5ε=0.01與ε=1時(shí)UGDP算法生成的不確定圖的數(shù)據(jù)效用性比較

Table 6 Comparison of data utility between uncertain graphs generated by triadic closure algorithm and original graph表6 原始圖與三元閉包法生成的不確定圖的數(shù)據(jù)效用性比較

表7列出了不同k值情況下(k,ε)-混淆算法的數(shù)據(jù)效用性.通過度量指標(biāo)NE、AD、DV在原始圖和不確定圖中的對(duì)比,我們可以看出,該算法具有較好的數(shù)據(jù)效用性.

Table 7 Data utility comparison for differentk values in (k,ε)-obfuscation algorithm表7 (k,ε)-混淆算法中不同k值的數(shù)據(jù)效用性對(duì)比

通過不同算法的數(shù)據(jù)效用性比較,我們可以得出以下結(jié)論:UGDP算法的數(shù)據(jù)效用性較差,三元閉包法的數(shù)據(jù)效用性最好,(k,ε)-混淆算法的數(shù)據(jù)效用性介于這兩種算法之間.

4.5 算法整體分析

數(shù)據(jù)的隱私性與效用性本身是一對(duì)矛盾體,如果要達(dá)到高的隱私保護(hù)程度,通常就需要犧牲數(shù)據(jù)的效用性.在第4.3節(jié)和第4.4節(jié)中通過與現(xiàn)有的(k,ε)-混淆算法進(jìn)行對(duì)比可以看出,本文提出的UGDP算法具有較高的隱私保護(hù)性,但是這種高隱私保護(hù)程度是通過犧牲數(shù)據(jù)的效用性而得到的.同時(shí),三元閉包方法具有高數(shù)據(jù)效用性,然而該方法的隱私保護(hù)性偏低.

不同的場(chǎng)景可能需要不同的需求,若需要達(dá)到高隱私保護(hù)程度或者高數(shù)據(jù)效用性,則可以根據(jù)不同的需求來選擇不同的隱私保護(hù)算法.

5 基于網(wǎng)絡(luò)結(jié)構(gòu)熵的度量算法

本節(jié)首先介紹網(wǎng)絡(luò)結(jié)構(gòu)熵可作為隱私度量的評(píng)價(jià)依據(jù)來度量圖的隱私性,其次使用網(wǎng)絡(luò)結(jié)構(gòu)熵來衡量不確定圖算法對(duì)原始圖的破壞程度.

5.1 網(wǎng)絡(luò)結(jié)構(gòu)熵的隱私性度量

相關(guān)匿名算法[22]提出對(duì)隱私進(jìn)行量化可以檢驗(yàn)隱私保護(hù)算法的優(yōu)劣,因此對(duì)圖結(jié)構(gòu)的隱私進(jìn)行度量具有重要的理論意義和應(yīng)用價(jià)值.網(wǎng)絡(luò)結(jié)構(gòu)熵是對(duì)整個(gè)結(jié)構(gòu)是否有序的度量,自然可以用于研究圖結(jié)構(gòu)隱私度量..根據(jù)k度匿名圖模型,圖9(a)和圖9(b)都是1度匿名圖,圖9(c)是2度匿

如圖 9所示,4個(gè)節(jié)點(diǎn)的連通網(wǎng)絡(luò)結(jié)構(gòu)的節(jié)點(diǎn)間連接方式不同,它們的度序列向量分別是名圖,圖9(d)是4度匿名圖.毫無疑問,圖9(d)達(dá)到最高匿名級(jí)別,圖9(c)達(dá)到中等匿名級(jí)別,圖9(a)和圖9(b)達(dá)到相同匿名級(jí)別但具有不同的結(jié)構(gòu).可以看出,從1度匿名到2度匿名存在一個(gè)逐漸變化的過程,但k度匿名圖模型并不能準(zhǔn)確地反映出這個(gè)變化過程.

Fig.9 Four kinds of graphs with the same nodes but different linking relationships圖9 4種具有相同節(jié)點(diǎn)但不同鏈接關(guān)系的圖結(jié)構(gòu)

k-度匿名圖模型的核心思想是度序列向量的匿名性.在一個(gè)k匿名向量中,在沒有任何輔助信息的前提下,任何一個(gè)元素被識(shí)別出來的概率不超過1/k.因此,許多圖修改算法都通過加減邊或者節(jié)點(diǎn)的方法來使圖的度序列分布得更加均勻,而網(wǎng)絡(luò)靜態(tài)特征是用來描述網(wǎng)絡(luò)特征的微觀數(shù)量分布統(tǒng)計(jì)或宏觀數(shù)量平均值統(tǒng)計(jì).為了更加細(xì)致地描繪度序列的變化過程,本文采取網(wǎng)絡(luò)靜態(tài)特征之一的網(wǎng)絡(luò)結(jié)構(gòu)熵作為隱私度量指標(biāo)來度量圖的隱私性變化情況.

度序列分布反映了圖的“形狀”信息,而熵反映了圖的“形狀”是否有規(guī)律.圖的形狀越有規(guī)則,隨機(jī)性就越小,因此熵就越小;若熵越大,圖的度序列分布也越均勻.根據(jù)式(5)和式(6),在k鄰近圖中網(wǎng)絡(luò)熵取最大值Entroymax=log2n,在星型圖中其取得最小值Entropymin=log24(n–1)/2,其中,n表示圖中所有節(jié)點(diǎn)的個(gè)數(shù).

在圖 9(a)到圖9(d)的網(wǎng)絡(luò)結(jié)構(gòu)熵依次為 1.242、1.321、1.366和1.386.因此,隱私程度越高,網(wǎng)絡(luò)結(jié)構(gòu)熵越大.盡管圖9(a)和圖9(b)在k-度匿名下的隱私程度相同,但網(wǎng)絡(luò)結(jié)構(gòu)熵仍然可以區(qū)分這兩個(gè)不同結(jié)構(gòu)的隱私變化.

5.2 圖結(jié)構(gòu)數(shù)據(jù)效用性度量算法

網(wǎng)絡(luò)結(jié)構(gòu)熵的變化還可以用來衡量網(wǎng)絡(luò)結(jié)構(gòu)的變化,在衡量不確定圖算法對(duì)原始圖結(jié)構(gòu)的破壞程度時(shí),我們提出了基于網(wǎng)絡(luò)結(jié)構(gòu)熵的數(shù)據(jù)效用性度量算法.利用該算法可以判斷原始圖和不確定圖結(jié)構(gòu)熵的變化情況,從而可以衡量圖結(jié)構(gòu)的失真程度.不確定圖的結(jié)構(gòu)熵與原始圖的結(jié)構(gòu)熵越接近,說明不確定圖對(duì)原始圖的改變程度較小,較好地保持了原圖的數(shù)據(jù)效用性.

結(jié)構(gòu)熵是衡量網(wǎng)絡(luò)結(jié)構(gòu)的重要指標(biāo),可以精確、簡(jiǎn)潔地度量復(fù)雜網(wǎng)絡(luò)的非同質(zhì)性,當(dāng)網(wǎng)絡(luò)受損分裂成幾個(gè)隨機(jī)網(wǎng)或者多數(shù)節(jié)點(diǎn)在非連通的情況下,網(wǎng)絡(luò)結(jié)構(gòu)熵會(huì)變小.從表 8中我們可以看出,原始圖的結(jié)構(gòu)熵與經(jīng)過差分隱私法及三元閉包算法得到的不確定圖的結(jié)構(gòu)熵的差值不大,且不確定圖中的網(wǎng)絡(luò)結(jié)構(gòu)熵相對(duì)于原始網(wǎng)絡(luò)圖來說較小,兩者之間的誤差值固定在0.2之內(nèi).表8只列出了節(jié)點(diǎn)個(gè)數(shù)小于等于500時(shí)網(wǎng)絡(luò)結(jié)構(gòu)熵的變化情況.隨著節(jié)點(diǎn)個(gè)數(shù)的增加,兩者網(wǎng)絡(luò)結(jié)構(gòu)熵的差值在逐漸減小.這說明,本文的算法在大數(shù)據(jù)場(chǎng)景下很好地保持了網(wǎng)絡(luò)的結(jié)構(gòu)特性.因此,與原始圖的結(jié)構(gòu)熵相比,4種數(shù)據(jù)集在不同算法下得到的不確定圖的結(jié)構(gòu)熵與原始圖的結(jié)構(gòu)熵基本保持不變,從而說明我們提出的不確定圖算法可以很好地保持原始圖的結(jié)構(gòu)特征.

詳細(xì)描述如算法4所示.

算法4.圖結(jié)構(gòu)數(shù)據(jù)效用性度量算法.

Table 8 The changes of network structure-entropy表8 網(wǎng)絡(luò)結(jié)構(gòu)熵的變化情況

6 結(jié) 論

本文基于不確定圖方法針對(duì)社交網(wǎng)絡(luò)隱私保護(hù)提出兩種不確定圖算法:基于差分隱私的不確定圖邊概率賦值算法和基于三元閉包的不確定圖邊概率分配算法.差分隱私法將差分隱私與不確定圖結(jié)合,不僅符合不確定圖隱私保護(hù)方法,同時(shí)具有差分隱私的嚴(yán)格可證明特征,可以達(dá)到雙重隱私保證,但其數(shù)據(jù)效用性有待提高.三元閉包法將三元閉包理論與不確定圖結(jié)合實(shí)現(xiàn)了社交網(wǎng)絡(luò)隱私保護(hù),并在一定程度上保持了較高的數(shù)據(jù)效用,與(k,ε)-混淆算法相比,在處理簡(jiǎn)單的社交網(wǎng)絡(luò)圖數(shù)據(jù)時(shí)運(yùn)行效率更高.因此,在下一步工作中,我們將探索三元閉包法在大規(guī)模社交網(wǎng)絡(luò)圖中的實(shí)證研究.同時(shí),根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)熵的特征,提出了一種基于網(wǎng)絡(luò)結(jié)構(gòu)熵的數(shù)據(jù)效用性度量算法,用來衡量對(duì)原始圖結(jié)構(gòu)的破壞程度,對(duì)于這方面內(nèi)容的內(nèi)在機(jī)理是未來重點(diǎn)探索的內(nèi)容.