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

吳振強,胡 靜,田堉攀,史武超,顏 軍

1(現(xiàn)代教學技術教育部重點實驗室(陜西師范大學),陜西 西安 710062)

2(陜西師范大學 計算機科學學院,陜西 西安 710119)

1 引 言

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

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

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

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

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

2 相關基礎知識

2.1 差分隱私的基本定義和相關概念

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

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

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

定義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(敏感度).給定一個函數(shù)f:G→G″,其中,G、G′具有相同的頂點集合,函數(shù)f的全局敏感度為

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

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

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

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

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

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

2.2 不確定圖

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

2.3 三元閉包

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

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

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

2.4 網(wǎng)絡結構熵

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

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

2.5k-度匿名

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

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

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

3 基于不確定圖的隱私保護算法

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

3.1 差分隱私法

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

1) 不確定圖模型

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

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

2) UGDP算法

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

Fig.4 The UGDP algorithm圖4 UGDP算法

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

(2) 為了構造不確定圖,每個噪聲值yi對應一個概率值pi,概率值pi=Pr[yi]=F(yi).

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

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

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

算法詳細描述如算法1所示.

算法1.UGDP算法.

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

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

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

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

3.2 三元閉包法

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

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

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

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

2) 算法描述

對于一個社交網(wǎng)絡圖G,它的點集為V,邊集為E.

(1) 加邊

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

Fig.6 Add-edges圖6 加邊

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

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

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

詳細的描述如算法2和算法3所示.

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

算法3.注入不確定.

(3) 注入不確定性

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

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

通過上述流程,我們在增加約束的條件下對原圖G注入不確定性,得到不確定圖G′.

3) 算法分析

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

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

4 分析與比較

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

4.1 隱私性度量

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

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

其中,Ente為不確定圖的邊熵,Ente值越大,表示不確定圖的不確定程度越大,對應隱私保護方法的隱私保護效果越好.

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

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

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

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

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

4.3 隱私性分析

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

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

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

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

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

(k,ε)-混淆算法將確定圖轉化為不確定圖時可以保持較好的數(shù)據(jù)效用性[18],為了把該算法達到的隱私保護效果與本文提出的算法進行直觀的對比,下面采用邊熵來進行隱私性度量.表 3為(k,ε)-混淆算法中邊熵的變化情況,由于篇幅和不同參數(shù)組合具有的多種可能性,下面只列出(k,ε)-混淆算法的一種情形來說明隱私保護效果,同時隱私度量的主要參數(shù)即混淆級別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的對比,如果利用邊熵來度量算法的隱私性,則UGDP算法在隱私保護程度上優(yōu)于(k,ε)-混淆算法,可以達到較好的隱私保護效果.通過表2和表3的對比,(k,ε)-混淆算法優(yōu)于三元閉包方法,可以達到較好的隱私保護效果.

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

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

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

Table 4 Comparison of data utility between uncertain graphs generated by UGDP algorithm whenε=0.1 and original graph表4 原始圖與ε=0.1時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時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ù)效用性.通過度量指標NE、AD、DV在原始圖和不確定圖中的對比,我們可以看出,該算法具有較好的數(shù)據(jù)效用性.

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

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

4.5 算法整體分析

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

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

5 基于網(wǎng)絡結構熵的度量算法

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

5.1 網(wǎng)絡結構熵的隱私性度量

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

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

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

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

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

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

5.2 圖結構數(shù)據(jù)效用性度量算法

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

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

詳細描述如算法4所示.

算法4.圖結構數(shù)據(jù)效用性度量算法.

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

6 結 論

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