帶權(quán)值的大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)隱私保護方法

黃海平 張東軍 王 凱 朱毅凱 王汝傳

1(南京郵電大學(xué)計算機學(xué)院 南京 210023)2(江蘇省無線傳感網(wǎng)高技術(shù)研究重點實驗室(南京郵電大學(xué)) 南京 210023)3(南京大學(xué)網(wǎng)絡(luò)信息中心 南京 210023)

隨著移動終端及網(wǎng)絡(luò)技術(shù)的更迭,移動社交網(wǎng)絡(luò)在世界范圍內(nèi)發(fā)展極為迅速,國內(nèi)移動社交軟件微信的注冊用戶已超10億,微博的活躍用戶數(shù)也日益增加至超大規(guī)模的數(shù)據(jù)量級.社交網(wǎng)絡(luò)平臺為人們提供分享、交流信息等服務(wù),同時用戶的真實信息和敏感數(shù)據(jù)要被社交網(wǎng)絡(luò)收集和歸檔,隨之而來的是各類的隱私泄露問題[1-2],例如Facebook的隱私泄露事件.傳統(tǒng)的隱私保護理論和技術(shù)逐漸體現(xiàn)出疲軟之態(tài),已無法涵蓋大數(shù)據(jù)隱私的內(nèi)涵,大數(shù)據(jù)隱私保護問題需要重新思考與定位[3].其中,社交網(wǎng)絡(luò)圖結(jié)構(gòu)數(shù)據(jù)的匿名發(fā)布及隱私保護問題已成為大數(shù)據(jù)及隱私保護領(lǐng)域備受關(guān)注的研究方向之一.而大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)的時效性和可用性與現(xiàn)存匿名保護算法的低執(zhí)行效率之間的矛盾成為解決該問題的最大挑戰(zhàn)之一.

關(guān)于社交網(wǎng)絡(luò)中的隱私保護問題,現(xiàn)存的方法主要有2類：一是基于聚類的方法,如Casas-Roma等人[4]提出的基于k-匿名的保護方法,這一類方法主要是將節(jié)點(邊)按規(guī)則分為不同組,并隱藏組內(nèi)的詳細(xì)信息,能實現(xiàn)較高的隱私保護程度,但隱藏子圖的內(nèi)部信息嚴(yán)重影響了社交網(wǎng)絡(luò)的局部結(jié)構(gòu)分析,從而降低了數(shù)據(jù)可用性,因此如何進行有效的分組以提高數(shù)據(jù)的可用性成為這類方法需要解決的最大問題.另一類是基于網(wǎng)絡(luò)圖結(jié)構(gòu)的擾動算法,如通過添加、刪除和交換等操作修改網(wǎng)絡(luò)圖結(jié)構(gòu)[5-6],使得發(fā)布數(shù)據(jù)和原始數(shù)據(jù)產(chǎn)生差異從而起到隱私保護作用,同時也保持了社交網(wǎng)絡(luò)的原有規(guī)模,相比于聚類方法往往具有更高的數(shù)據(jù)可用性.其后,Dwork[7]提出差分隱私的概念,能實現(xiàn)數(shù)據(jù)的強隱私保護.這2類方法均可很好結(jié)合差分隱私的模型和定義,例如通過添加、刪除等操作修改網(wǎng)絡(luò)結(jié)構(gòu)圖并使其滿足差分隱私的需求[8-9].

然而,隨著超大規(guī)模社交網(wǎng)絡(luò)的出現(xiàn),需要在大量的社交關(guān)系中劃分出不同敏感程度的邊關(guān)系,并為這些邊關(guān)系賦予不同的權(quán)值.相比于無權(quán)值的社交網(wǎng)絡(luò)處理方法,能有效減少需要擾動的邊數(shù)量.然而,網(wǎng)絡(luò)中的邊權(quán)值也包含著許多重要的隱私信息.例如,對某個社交網(wǎng)絡(luò)群體進行傳染病或者遺傳病研究時,個體間的關(guān)系強弱可能會決定傳染或者遺傳的擴散趨勢,這對于個體而言是極其隱私的信息.針對帶權(quán)值的社交網(wǎng)絡(luò)的數(shù)據(jù)隱私保護,目前研究者們提出了多種對邊權(quán)值擾動的方法[10-11],然而這些方法不能有效地解決圖結(jié)構(gòu)攻擊的問題：當(dāng)攻擊者掌握某節(jié)點的鄰接度序列時,仍然可以確定該節(jié)點在圖中的位置,子圖攻擊仍然奏效.針對此,本文提出了一種非交互式的基于差分隱私的帶權(quán)社交網(wǎng)絡(luò)隱私保護方法,在對邊權(quán)值擾動的同時,通過添加邊和節(jié)點噪音對圖結(jié)構(gòu)進行擾動從而抵御圖結(jié)構(gòu)攻擊.

本文的主要貢獻有3個方面:

1) 針對帶權(quán)值的社交網(wǎng)絡(luò)圖的特征,在約束模型下區(qū)分圖中的關(guān)鍵邊和非關(guān)鍵邊,基于差分隱私模型,分別添加不同的噪音達到隱私保護的同時最大程度保留了數(shù)據(jù)的可用性;

2) 設(shè)計了帶權(quán)社交網(wǎng)絡(luò)中的節(jié)點和邊的擾動策略,使得算法具有抵御圖結(jié)構(gòu)攻擊的能力;

3) 將提出的隱私保護方法與已有方法進行比較,實驗結(jié)果表明,本文方法具有更高的運行效率,有效解決了大規(guī)模數(shù)據(jù)集發(fā)布的隱私保護和數(shù)據(jù)可用性及時效性的問題.

1 相關(guān)工作

近年來針對無權(quán)值的社交網(wǎng)絡(luò)隱私保護,研究者們提出了許多解決方案.Zhou等人[12]提出的基于k-匿名保護方法將圖結(jié)構(gòu)中的節(jié)點(邊)按規(guī)則分組,隱藏組內(nèi)的詳細(xì)信息以達到保護目的,通過k-匿名和l-多樣性來抵御社交網(wǎng)絡(luò)中的鄰域攻擊.Zou等人[13]提出k-字同構(gòu)方法來實現(xiàn)隱私保護,該方法也是先將原始圖分割成若干組,不同于k-匿名方法的是它通過向組內(nèi)添加邊使得k個塊同構(gòu),在可抵御圖結(jié)構(gòu)攻擊的同時也保留了原始圖的規(guī)模.Chen等人[8]提出了DER(density-based exploration and reconstruction)算法對社交網(wǎng)絡(luò)圖結(jié)構(gòu)進行聚類劃分,基于差分隱私模型添加噪音來保護數(shù)據(jù)安全,這類方法對于抵御攜帶背景知識的攻擊有著顯著的效果.

針對帶權(quán)值的社交網(wǎng)絡(luò)圖的隱私保護,Sala等人[9]基于節(jié)點聚類的方法,通過構(gòu)建超邊和超點(其中超邊的邊權(quán)值為2個超點邊權(quán)值的平均值)實現(xiàn)隱私保護,但是和無權(quán)值網(wǎng)絡(luò)中的k-匿名方法有著相同的缺陷：較嚴(yán)重降低了數(shù)據(jù)的可用性.也有研究者提出了基于差分隱私策略的保護方法.Wang 等人[10]提出采用高斯隨機乘法在權(quán)值中加入噪音,從而實現(xiàn)隱私保護.這種方法雖然對權(quán)值起到了很好的保護作用,但是社交網(wǎng)絡(luò)的屬性參數(shù)也容易被改變,不能很好地抵御圖結(jié)構(gòu)攻擊.針對圖結(jié)構(gòu)的保護,Wang等人[14]提出一種新的k-匿名算法,擾動節(jié)點對之間的路徑,使得存在k條相同長度的最短路徑,當(dāng)路徑數(shù)小于k時,則擾動全部路徑長度使其等于最短路徑長度.該方法雖然能保持最短路徑長度不變,然而卻未能保存其他圖屬性參數(shù).為解決圖屬性數(shù)據(jù)功用問題,Das等人[11]提出應(yīng)用線性不等式捕獲網(wǎng)絡(luò)中的某些參數(shù)特征,對權(quán)值進行擾動,使得發(fā)布的社交網(wǎng)絡(luò)圖保持原有的線性屬性.蘭麗輝等人[15]設(shè)計了滿足差分隱私的查詢模型——WSQuery,該模型可以捕獲社交網(wǎng)絡(luò)的結(jié)構(gòu)特征,并將結(jié)果集以三元組序列輸出,降低了數(shù)據(jù)誤差提高數(shù)據(jù)可用性.

2 約束模型和算法描述

2.1 差分隱私定義和模型

差分隱私是Dwork等人[7]提出的一種抵御背景知識攻擊的強隱私保護模型.該模型最早應(yīng)用于數(shù)據(jù)庫隱私中.給定2個數(shù)據(jù)集D1和D2,其中只有1條數(shù)據(jù)記錄不同,表示為|D1ΔD2|=1,即稱D2為D1的鄰近數(shù)據(jù)集,可表示為D2∈Nb(D1).

定義1.ε-差分隱私.對于隨機算法M:D→SK,Range(M)用來表示算法的所有可能的輸出結(jié)果集,即對于D1與D2的算法輸出結(jié)果S∈Range(M),若滿足ε-差分隱私,則有：

Pr[M(D1)∈S]≤eεPr[M(D2)∈S]，

(1)

其中，概率Pr表示隱私被揭露的風(fēng)險,由算法M進行隨機性的控制,隱私保護程度由隱私預(yù)算參數(shù)ε表示,ε越小則隱私保護程度越高,表示鄰近數(shù)據(jù)集結(jié)果越接近越不容易區(qū)分,但這卻是以增加噪音為代價的[15].

定義2.查詢函數(shù)敏感度.假設(shè)查詢函數(shù)定義為f:D→Rd,輸入為數(shù)據(jù)集D,輸出為一個d維的實數(shù)向量,對于2個鄰近數(shù)據(jù)集D1和D2,有全局敏感度：

(2)

定理1.假設(shè)存在n個隨機算法,其中Ai滿足εi-差分隱私,則Ai(0

定理2.假設(shè)存在n個隨機算法,其中Ai滿足εi-差分隱私,并且任意2個算法的操作數(shù)據(jù)集沒有交集,則Ai(0

上述性質(zhì)將運用到本文的隱私算法設(shè)計中.

2.2 約束模型

假設(shè)在一個帶有邊權(quán)值的社交網(wǎng)絡(luò)圖中,圖的一系列屬性可以用邊權(quán)值的線性組合來表示,則當(dāng)我們改變邊權(quán)值且保證它仍然滿足原來的線性關(guān)系時,圖的屬性并不會被改變.在本文討論的社交網(wǎng)絡(luò)圖中,權(quán)值均大于0,基于這一假設(shè),Das等人[11]提出可以通過建立線性不等式模型來反映圖屬性.給定原加權(quán)圖G=(V,E,W),其中E為圖中全體邊的集合,V為全體節(jié)點集合,W為邊對應(yīng)的權(quán)值集合,模型的目標(biāo)是用邊權(quán)值間的關(guān)系來模擬線性不等式系統(tǒng).例如,在Dijkstra算法中,每次從可到達的節(jié)點中選擇路徑最短的節(jié)點,將其添加到集合S中.令v為在第i次迭代中選擇的節(jié)點,f(u0,v)為源點u0到v的距離,同時f(u0,v′)為第i+1次迭代中選擇的節(jié)點v′到源點的距離,則有f(u0,v)≤f(u0,v′).對于連續(xù)迭代過程中每次選擇的邊對(u,v)和(u′,v′),由于每次選擇添加距離最小的節(jié)點到集合中,設(shè)w(u,v)和w(u′,v′)為2次迭代中更新的邊,則有f(u0,v)+w(u,v)≤f(u0,v′)+w(u′,v′).顯然除了距離約束,其他約束條件也可轉(zhuǎn)化成該形式添加到模型中,如式(3)所示記作AX≤B,最終構(gòu)建的模型可以通過其中1組或多組約束不等式體現(xiàn)出原圖的屬性.

(3)

如果邊權(quán)值被重新分配為式(3)中的不等式系統(tǒng)的任何解,則將確保被建模的算法的圖屬性保持不變.因此,該模型可以表示為線性規(guī)劃問題：

(4)

其中F是線性目標(biāo)函數(shù)對應(yīng)于圖的屬性,因此圖中任何能表示為邊權(quán)值的線性組合的屬性問題都可以轉(zhuǎn)化為符合該模型的線性規(guī)劃問題.而目前社交網(wǎng)絡(luò)分析中使用的屬性參數(shù)都可以用邊權(quán)值的線性組合表示.因此這種模型可以完美應(yīng)用于社交網(wǎng)絡(luò)分析領(lǐng)域,并且在模型建立之后,有大量完善的線性規(guī)劃問題求解方法來求得式(4)問題的解.通過這一模型可以輕易地解決傳統(tǒng)隱私保護方式會改變圖屬性的問題,只需保證數(shù)據(jù)擾動之后仍然滿足該模型約束即可.模型的復(fù)雜度是確定模型所必需的不等式的數(shù)量即矩陣A的規(guī)模.矩陣A的列對應(yīng)于系統(tǒng)中的變量,即圖中邊的數(shù)量,行對應(yīng)于模型產(chǎn)生的不等式,顯然當(dāng)不等式數(shù)量大于邊數(shù)時即可認(rèn)為圖屬性被保留.

3 差分隱私擾動模型

3.1 單源最短路徑約束模型

在本節(jié)中,通過單源最短路徑算法建立圖的約束模型.設(shè)G為原始社交網(wǎng)絡(luò)圖,E為圖中全體邊的集合,V為全體節(jié)點集合,W為邊對應(yīng)的權(quán)值集合.初始化V0={v0},其中v0為給定的源點.通過改進的Dijkstra算法[16]在每一步選擇節(jié)點添加到生成樹的過程中構(gòu)造約束不等式,具體算法如下：

算法1.約束模型建立.

輸入：G,E,V,W,V0={v0};

輸出：約束矩陣A生成樹序列T={t1,t2,…,ti,…}.

① FORv∈V-V0且(v0,v)∈E

②Q=Q+{v};*設(shè)置Q集合為下一步可到達的所有點集合*

③ END FOR

④ IFQ=?且V-V0≠?*當(dāng)圖G不聯(lián)通時,遍歷完1個聯(lián)通區(qū)域后重新設(shè)置源點*

⑤V=V-V0;

⑥v0=rand(V);

⑦V0={v0};

⑧ GOTO ①;

⑨ END IF

⑩ WHILEQ≠?

w(u,v)};

w(u,v)};

算法1的過程類似于Dijkstra算法.由于社交網(wǎng)絡(luò)圖的稀疏性,圖G往往是非連通的,因此當(dāng)算法執(zhí)行到集合Q為空即從源點出發(fā),剩余節(jié)點均不可到達時終止此次循環(huán),將生成樹ti添加到生成樹序列T中,重新從未添加的節(jié)點集合中選擇源點,重復(fù)上述過程直到所有節(jié)點均被添加到序列T中.每次構(gòu)建生成樹ti的過程與Dijkstra算法相同,從集合Q中選擇出到集合V0權(quán)值最小的節(jié)點記作u,將節(jié)點u添加到集合V0中并更新V0到集合Q中節(jié)點的路徑,根據(jù)更新的路徑生成約束條件,同時pre_u為上一步從Q選擇出添加到V0的節(jié)點,生成約束條件A(u,pre_u),最后使得pre_u=u,更新集合Q.其中生成約束不等式的規(guī)則如下：

1) Dijkstra算法的執(zhí)行過程是貪心選擇的過程,因此pre_u作為上次步驟中選擇的節(jié)點,D(v0,pre_u)≤D(v0,u)將必然成立.所構(gòu)建的約束不等式為

f(v0,pre_u)≤f(v0,u).

2) 若通過節(jié)點u可以優(yōu)化D(v0,v)，即D(v0,v)≥D(v0,u)+w(u,v),則將D(v0,v)更新為D(v0,u)+w(u,v),同時構(gòu)建約束不等式為

f(v0,v)≥f(v0,u)+w(u,v).

3) 若通過節(jié)點u不可優(yōu)化D(v0,v)，即D(v0,v)≤D(v0,u)+w(u,v),則構(gòu)建的約束不等式為

f(v0,v)≤f(v0,u)+w(u,v).

已知Dijkstra算法的時間復(fù)雜度為O(n2),考慮到社交網(wǎng)絡(luò)圖數(shù)據(jù)的稀疏性,可以對該算法進行優(yōu)化.將邊權(quán)值信息使用堆結(jié)構(gòu)存儲,則選擇最短路徑時可優(yōu)化為O(mlbn),其中m表示邊數(shù),n表示節(jié)點數(shù),建堆過程時間復(fù)雜度為O(nlbn),因此優(yōu)化后的復(fù)雜度為O((m+n) lbn).

對Dijkstra算法的改進并沒有增加它的復(fù)雜度,同為O((m+n) lbn).算法1中～步,選擇最短路徑時添加構(gòu)造約束不等式過程,循環(huán)次數(shù)為O(mlbn),程序步增量為c,則有T(m,n)=mlbn+clbn,當(dāng)m,n趨向于無窮大時,由于c為常數(shù)，則T(m,n)(mlbn+clbn)與T(m,n)(mlbn)同階,則漸進時間復(fù)雜度可記為O(mlbn).建堆過程與Dijkstra算法一致,因此本方法與Dijkstra有相同的時間復(fù)雜度O((m+n) lbn).

此外,還可以通過其他方式建立模型,如在構(gòu)建最小代價生成樹的Kruskal算法中,每次選擇剩余邊集合中權(quán)值最小的邊,同時保證不產(chǎn)生回路,將其添加到生成樹中.該過程建立的約束不等式類型只有1種,即w(u,v)≤w(u′,v′),其中(u,v)為在第i次迭代中選擇的邊,(u′,v′)為第i+1次迭代中選擇的邊.

另外度序列也可用來建立約束不等式模型,如Havel定理用于圖重構(gòu)時,設(shè)di為第i次迭代的節(jié)點度,di+1為第i+1次迭代的節(jié)點度,則有di≥di+1.當(dāng)不等式組規(guī)模足夠大時,所有滿足約束模型且可簡單圖化的度序列都可以看作是同構(gòu)的,只是該方法需要將圖先度序列化，再將度序列重構(gòu)為圖.

相比于以上2種方式，針對帶權(quán)值的社交網(wǎng)絡(luò)數(shù)據(jù)而言,單源最短路徑可以直接在圖結(jié)構(gòu)上操作執(zhí)行，其簡明性、應(yīng)用廣泛和較高的執(zhí)行效率也使之成為各類隱私保護方案中最常用的模型,因此本文選擇單源最短路徑來建立模型.

3.2 差分隱私噪音添加

在帶權(quán)值的社交網(wǎng)絡(luò)圖中的噪聲添加不同于無權(quán)值圖,一條邊的權(quán)值改動將會影響整個圖的結(jié)構(gòu),如最短路和最小代價生成樹,都會發(fā)生相應(yīng)的改變.因此本文采用算法1表示的約束模型對添加噪音進行線性約束.

因此f的敏感度為

w(u′,v′)|,

(5)

其中，P(u,v)表示節(jié)點u和節(jié)點v間的最短路徑的邊集合,w′和w分別表示擾動前后邊(u′,v′)和(u,v)的權(quán)值.

具體添加算法如下：

算法2.約束噪音添加算法.

輸入：G,E,V,W,A,T,ε1;

輸出：G′.

① FOR (u,v) ∈ET

②w′(u,v) =w(u,v)+laplace(S(f)ε1);

③ END FOR

④ FOR (u,v) ∈EN

⑤w′(u,v)=value→answer(A)+laplace(S(f)ε1);*value→answer(A)為式(4)中線性規(guī)劃的求解結(jié)果*

⑥ END FOR

⑦E=E+{(u,v)|rand(u,v)∩ET=?};

⑧w(u,v)=min(ti,maxwt).

算法2的輸入是需要添加噪音擾動的原始圖數(shù)據(jù)G,E,V,W,生成樹序列T,以及約束矩陣A和隱私預(yù)算ε1,最終得到擾動圖G′.首先我們將集合E分成ET和EN兩個部分,其中ET為構(gòu)成生成樹的邊集合；先對ET中的邊權(quán)值添加Laplace噪聲,再將加噪之后的權(quán)值帶入約束不等式中,可解得EN中的邊權(quán)值約束,并生成新的權(quán)值.在每個生成樹ti中,我們選擇若干原來不存在邊的節(jié)點對(u,v)構(gòu)造一條新邊,比較ti中最大邊權(quán)值與f(u,v),選擇其中較小的一個作為邊權(quán)值.

由于節(jié)點的添加或刪除具有很大的敏感性,添加或者刪除某個節(jié)點時,同時連接在該節(jié)點的邊關(guān)系會隨之改變,顯然會引入大量的噪音.本文提出的虛假節(jié)點添加方法可以有效地降低對數(shù)據(jù)可用性的影響.對于節(jié)點u′的刪除操作,函數(shù)f(u,v)的敏感度定義為

(6)

其中D′(u,v),D(u,v)表示刪除節(jié)點后的最短路徑長度和原最短路徑長度,由此可見直接刪除節(jié)點會造成巨大的影響.節(jié)點添加時只要保證邊權(quán)值足夠大即可極大程度地降低對數(shù)據(jù)可用性的影響,但是過大的邊權(quán)值會很容易被攻擊者識別出.本文的節(jié)點擾動方式分為2步：1)刪除度低于閾值的節(jié)點,同時對于連接到該節(jié)點的所有節(jié)點,如果他們之間存在邊關(guān)系,則修改其邊權(quán)值；2)添加虛假節(jié)點,虛假節(jié)點的度等于定義的閾值.其中閾值由用戶根據(jù)應(yīng)用需求定義.具體算法流程如下：

算法3.節(jié)點擾動算法.

輸入：G,E,V,W,degree_value,ε2,ε3;

輸出：G′.

①Nnoise=|laplace(ε2)|;*通過用戶定義的隱私預(yù)算計算擾動節(jié)點個數(shù)*

②rand(v)∈V且v.degree≤degree_value;

③Nnoise=Nnoise-1;

④ FOR each nodeu1,u2∈V且(u1,v)∈E且(u2,v)∈E

⑤ IFf(u1,u2)≥w(u1,v)+w(u2,v)

⑥ IF {(u1,u2)}∩E=? THEN

E=E+{(u1,u2)};

⑦w(u1,u2)=w(u1,v)+w(u2,v)+

laplace(S(f)ε3);

⑧ END IF

⑨ END IF

⑩ END FOR

算法3的輸入包括了原始圖數(shù)據(jù)G,E,V,W以及由用戶自己定義的節(jié)點度的閾值degree_value和隱私預(yù)算ε2,ε3,輸出為擾動圖G′.首先執(zhí)行刪除擾動方式,由于查詢函數(shù)對節(jié)點增刪的敏感度很高,因此我們選擇度小于degree_value的節(jié)點以減小對查詢函數(shù)的影響,選擇擾動節(jié)點個數(shù)Nnoise=|laplace(1ε2)|(增加或刪除節(jié)點的敏感度為1).當(dāng)選擇節(jié)點v之后對所有連接到節(jié)點v的節(jié)點兩兩進行如下操作：假設(shè)u1和u2都有到v的邊且f(u1,u2)=w(u1,v)+w(v,u2),則令w(u1,u2)=w(u1,v)+w(v,u2)；若u1和u2之間不存在邊則構(gòu)造一條邊,最后刪除節(jié)點v以及所有的邊.虛假節(jié)點的插入也以度小于degree_value的節(jié)點為基準(zhǔn),選擇到基準(zhǔn)節(jié)點v之后添加虛假節(jié)點v1并且構(gòu)造邊(v1,v),該邊權(quán)值可設(shè)置為v的邊權(quán)值的平均值.為了使虛假節(jié)點v1的度不被攻擊者識破,將所有與v連接的節(jié)點都構(gòu)造一條邊連接到節(jié)點v1.權(quán)值取值方式如下：設(shè)節(jié)點u與v直接存在邊關(guān)系,則w(v1,u)=w(u,v)+laplace(S(f)ε3).

由算法3所生成的邊節(jié)點擾動對圖的平均最短路徑幾乎沒有影響,但是會增加三角計數(shù),具體計算為

(7)

其中，Ctri表示原圖中的三角計數(shù),Vfake為添加的虛假節(jié)點集合.由式(7)可以看出,當(dāng)添加的虛假節(jié)點度越高,三角計數(shù)越高.而虛假節(jié)點的度又與構(gòu)建節(jié)點時的基準(zhǔn)節(jié)點有關(guān),因此我們選擇度較小的節(jié)點作為基準(zhǔn)節(jié)點.

3.3 隱私保護分析

差分隱私算法的隱私保護程度與添加噪聲的過程有關(guān),其中添加噪聲的敏感度已在對應(yīng)算法處給出分析.本文的擾動方法分為2個步驟：1)通過約束模型,對邊權(quán)值添加差分隱私噪聲,隱私預(yù)算為ε1；2)節(jié)點擾動,即節(jié)點的刪除和虛假節(jié)點的添加,隱私預(yù)算為ε2,構(gòu)造噪音邊權(quán)值的隱私預(yù)算為ε3.首先,在算法2中步驟2是對組成生成樹的邊權(quán)值全部添加隱私預(yù)算為ε1的Laplace噪聲,敏感度函數(shù)

由定義1可知,算法2通過約束條件得出的擾動權(quán)值滿足ε1-差分隱私.

在基于Laplace機制的噪音分配過程中算法2和算法3的噪音分配是相互獨立的,由定理2可知,當(dāng)算法2與算法3作用在圖G時滿足(ε1+ε2+ε3)-差分隱私,令ε=ε1+ε2+ε3,本文提出的帶權(quán)值的大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)的隱私保護方法符合ε-差分隱私.

4 實驗與結(jié)果

本節(jié)主要用仿真實驗來分析本方法(在實驗中簡寫為dp-noisy)的數(shù)據(jù)可用性、隱私保護程度和執(zhí)行效率.如表1所示,本實驗通過爬取新浪微博的社交網(wǎng)絡(luò)參數(shù),隨機生成聚集系數(shù)為0.01的社交圖模擬數(shù)據(jù)集：1 000節(jié)點、5 000節(jié)點、10 000節(jié)點和30 000節(jié)點.本方法的隱私預(yù)算ε1,ε2,ε3分配方式并不固定,可根據(jù)不同場景進行分配.多次實驗中我們發(fā)現(xiàn),取ε1∶ε2∶ε3=2∶1∶2時實驗效果較好(ε2控制添加的節(jié)點噪音,因為節(jié)點數(shù)規(guī)模較大,需要添加大量節(jié)點噪音,所以ε2取值分配較小).

Table 1 Number of Nodes and Edges in 4 Data Sets表1 4個不同數(shù)據(jù)集的節(jié)點數(shù)和邊數(shù)

4.1 性能分析

本文在表1中4個不同規(guī)模的數(shù)據(jù)集上將dp-noisy方法與Das等人[11]提出的lp-noisy方法,Wang等人[14]提出的K-MPNP(K-shortest path privacy)方法以及蘭麗輝等人[15]提出的LWSPA(protection algorithm based on Laplace noise for weighted social networks)方法的運行效率進行了對比.如圖1(a)所示,其中dp-noisy方法、lp-noisy方法和K-MPNP都是采用單源最短路徑原理來擾動社交網(wǎng)絡(luò)圖中的邊權(quán)值.圖1中橫坐標(biāo)表示數(shù)據(jù)集的編號,縱坐標(biāo)表示運行時間(單位s).

Fig. 1 Running time圖1 運行時間

由于K-MPNP方法中需要多次重復(fù)單源最短路徑的計算過程,因此執(zhí)行效率遠(yuǎn)低于其他2個方法.在較小規(guī)模數(shù)據(jù)集中,dp-noisy方法與lp-noisy方法的執(zhí)行效率相當(dāng),當(dāng)數(shù)據(jù)集規(guī)模不斷擴大時,由于lp-noisy方法的擾動形式單一,因而具有更好的運行效率.而LWSPA方法通過向三元組查詢模型中添加Laplace擾動,因而在數(shù)據(jù)規(guī)模較小時運行效率最優(yōu),然而當(dāng)數(shù)據(jù)規(guī)模較大導(dǎo)致圖結(jié)構(gòu)復(fù)雜時,運行效率會急速下降.綜上,dp-noisy方法與lp-noisy方法具有更好的執(zhí)行效能.

由于帶邊權(quán)值的社交網(wǎng)絡(luò)數(shù)據(jù)隱私保護的時空復(fù)雜度與無權(quán)值的相比更高,因此,為了進一步驗證本方法的執(zhí)行效率,我們將本方法的運行時間與同樣采用差分隱私保護機制、但作用于無權(quán)值社交網(wǎng)絡(luò)圖的DER方法進行對比,實驗中2種方法的隱私預(yù)算ε取值都為1.從圖1(b)可以看出隨著數(shù)據(jù)集規(guī)模的增加,2種方法的運行時間都在增加,但dp-noisy相較于DER方法有了較大程度的提高.因為DER方法的運行時間主要是在矩陣聚集上,這部分執(zhí)行的過程中,每一次交換都需要計算曼哈頓距離,時間復(fù)雜度為O(n2),而dp-noisy方法的時間復(fù)雜度為O((m+n) lbn).這說明本方法可以運行在較大規(guī)模的數(shù)據(jù)集上,且對比傳統(tǒng)擾動方法DER具有良好的可擴展性.同時,也說明了本方法在處理帶權(quán)值的社交網(wǎng)絡(luò)數(shù)據(jù)時也有著較好的運行效率.

4.2 隱私保護質(zhì)量分析

針對邊權(quán)值的識別攻擊,本實驗首先將dp-noisy方法與抵御邊權(quán)值識別攻擊的lp-noisy方法、LWSPA方法以及K-MPNP方法進行對比.其后,本實驗選擇了無向無權(quán)值的DER算法作對比,以驗證本方法抵御圖結(jié)構(gòu)攻擊的性能.

Fig. 2 Comparison of weight distribution before and after disturbance圖2 擾動前后權(quán)值分布對比

針對邊權(quán)值的分析,本實驗中dp-noisy的隱私預(yù)算ε=1.如圖2所示,dp-noisy的擾動效果明顯好于lp-noisy的擾動效果.當(dāng)數(shù)據(jù)規(guī)模較小時,如圖2(a)(b)所示,lp-noisy的擾動效果還比較明顯,這是因為lp-noisy方法通過線性規(guī)劃方法重新定義單源最短路徑上的邊權(quán)值,且只對不在路徑上的權(quán)值加噪,雖然對于較低的權(quán)值并未實現(xiàn)很好的擾動,但由于數(shù)據(jù)規(guī)模小,依然取得了較好的擾動效果.如圖2(c)(d)所示,當(dāng)數(shù)據(jù)規(guī)模較大時,lp-noisy的擾動分布與原數(shù)據(jù)差異很小,尤其在權(quán)值極大和極小處,lp-noisy擾動后的分布幾乎與原始數(shù)據(jù)一致.出現(xiàn)這種情況是因為數(shù)據(jù)規(guī)模較大時,邊數(shù)的增加會引起約束集的增加,這使得線性規(guī)劃求出的最優(yōu)解無限接近于原始數(shù)據(jù).而dp-noisy方法,除了對不在最短路徑上的邊權(quán)值擾動之外,還對線性規(guī)劃的解添加差分隱私噪聲,同時在節(jié)點擾動過程中也對權(quán)值分布產(chǎn)生了較大改變,由圖2(a)～(d)可知,dp-noisy方法總能產(chǎn)生較明顯的擾動.

Fig. 4 Ratio of modified edges圖4 擾動邊比例

(8)

Fig. 3 Average recognition rate comparison圖3 平均識別率對比圖

針對邊權(quán)值的擾動質(zhì)量,實驗選擇LWSPA方法與k-匿名方法K-MPNP 做對比,其中LWSPA方法是蘭麗輝等人[15]提出的基于差分隱私的帶權(quán)值的社交網(wǎng)絡(luò)隱私保護方法.K-MPNP方法,是通過修改非最短路徑中的邊權(quán)值,使其等于最短路徑長度,并且當(dāng)路徑數(shù)小于K時,則修改所有存在的路徑.實驗中,K-MPNP的|H|=10,當(dāng)K分別取10，8，5，2時,其保護效果與另外2種差分隱私方法的ε取0.5，1，3，10時相當(dāng).在此基礎(chǔ)上,對比實驗結(jié)果如圖4所示.

如圖4(a)(b)所示,當(dāng)數(shù)據(jù)規(guī)模較小時,K-MPNP取較大K值,即節(jié)點對之間被擾動的路徑較多,因而大量的邊權(quán)值被擾動.當(dāng)數(shù)據(jù)集規(guī)模增加,由于社交網(wǎng)絡(luò)圖的“小世界”特征,最短路徑不會發(fā)生較大改變,當(dāng)|H|固定時,K-MPNP擾動的邊權(quán)值數(shù)量并不會增加.LWSPA方法則通過三元組查詢結(jié)構(gòu)添加擾動噪聲,因此當(dāng)數(shù)據(jù)規(guī)模較大時,所添加的擾動最高.綜上,在4個數(shù)據(jù)集中,隱私預(yù)算較小時,dp-noisy擾動比例較為平穩(wěn),LWSPA在數(shù)據(jù)規(guī)模較大時,擾動量有較大增加,而K-MPNP則在數(shù)據(jù)集3和數(shù)據(jù)集4中的擾動比例大幅度降低,其并不適合大規(guī)模數(shù)據(jù)集.

如圖4(c)(d)所示,此時K的取值較小(隱私預(yù)算較大),會導(dǎo)致權(quán)值的擾動比例降低.在4個數(shù)據(jù)集中,dp-noisy都優(yōu)于K-MPNP和LWSPA,尤其是當(dāng)K=2,ε=10時,差異非常明顯.這是由于,當(dāng)K=2時,節(jié)點對之間只需要擾動1條路徑的長度即可保證他們之間存在2條相等的最短路徑,因此K-MPNP的擾動比例始終在30%以下.而dp-noisy則因為存在擾動邊關(guān)系來擾動權(quán)值的過程，所以在4個數(shù)據(jù)集中都取得了最好的效果.

針對圖結(jié)構(gòu)的識別攻擊是通過發(fā)布特殊形狀的子圖到網(wǎng)絡(luò)中,在擾動后根據(jù)該子圖確定擾動圖中目標(biāo)節(jié)點的位置.實驗通過統(tǒng)計不同相似度的子圖的匹配數(shù)來反映隱私保護質(zhì)量.為了方便比較,隱私預(yù)算ε取值都為1,其中dp-noisy隱私預(yù)算分配為ε1∶ε2∶ε3=2∶1∶2.

如圖5所示,在相同的隱私預(yù)算下,不論是何種數(shù)據(jù)集,同一相似度下DER擾動后的結(jié)果要小于dp-noisy,從而被攻擊者識別的概率要高于dp-noisy.這是因為DER添加的邊噪聲過多,導(dǎo)致圖結(jié)構(gòu)變得復(fù)雜,攻擊者一旦掌握了某一個子圖信息便很容易確定目標(biāo)在圖中的位置.

Fig. 5 Matching number comparison圖5 匹配數(shù)對比

4.3 數(shù)據(jù)可用性分析

對于帶權(quán)值的社交網(wǎng)絡(luò)圖數(shù)據(jù)而言,數(shù)據(jù)可用性分析將分成2個部分進行：一是社交網(wǎng)絡(luò)的結(jié)構(gòu)特征參數(shù)分析,二是邊權(quán)值分析.

對于結(jié)構(gòu)特征參數(shù),本實驗通過將原始數(shù)據(jù)的圖特征參數(shù)與擾動分布后社交網(wǎng)絡(luò)數(shù)據(jù)的圖特征參數(shù)進行比較分析,以驗證在不同的隱私預(yù)算下本算法的數(shù)據(jù)可用性.本實驗選擇了聚集系數(shù)、三角形計數(shù)和邊數(shù)這3個最重要的參數(shù),用于統(tǒng)計圖結(jié)構(gòu)特征.實驗選擇同樣使用差分隱私保護機制的LWSPA方法和DER方法在4個數(shù)據(jù)集上進行了對比,由于LWSPA不涉及邊關(guān)系的擾動,因此三角形計數(shù)和邊數(shù)2個參數(shù)只與DER方法進行對比.實驗結(jié)果如圖6～9所示:

Fig. 6 Clustering coefficient comparison圖6 聚集系數(shù)對比

Fig. 7 Edge disturbance圖7 邊數(shù)擾動對比

Fig. 8 Number of triangles圖8 三角形數(shù)量對比

Fig. 9 Average shortest path圖9 平均最短路徑對比

如圖6所示,當(dāng)選擇不同的隱私預(yù)算時,使用這3種方法的聚集系數(shù)都不會發(fā)生大的改變且差異較小;其中dp-noisy和LWSPA的聚集系數(shù)大多數(shù)時候高于原始數(shù)據(jù),但是隨著隱私預(yù)算的增加,LWSPA的聚集系數(shù)更加接近于原始數(shù)據(jù).由于dp-noisy方法會在2個互相可到達但是不存在邊的節(jié)點對之間添加邊關(guān)系,同時選擇度較低的節(jié)點為基準(zhǔn)點插入虛假節(jié)點,這在一定程度上增加了圖的聚集程度.而DER方法則是通過聚類之后添加邊噪聲,這在一定程度上減少了對聚集系數(shù)的影響.對比圖6(c)(d)還可以發(fā)現(xiàn)在更大規(guī)模的數(shù)據(jù)集上,3種方法對聚集系數(shù)的影響將會減小.對于稀疏矩陣而言,更大的數(shù)據(jù)集意味著噪音邊有著更大的概率被添加到無效區(qū)域,從而對聚集系數(shù)的影響更小.

圖7是每個數(shù)據(jù)集上,通過2種方法擾動之后的邊數(shù)量對比,可以看到擾動后的邊數(shù)量往往會高于原始數(shù)據(jù).對比圖7(a)～(d)可以發(fā)現(xiàn),當(dāng)數(shù)據(jù)集增大時DER算法的數(shù)據(jù)可用性越來越差,雖然dp-noisy方法也會增加邊數(shù)量但影響遠(yuǎn)小于DER方法.這是因為DER通過添加大量的邊噪音以達到保護效果,其中有相當(dāng)一部分的冗余噪音邊嚴(yán)重地破壞了數(shù)據(jù)的可用性.

同時由于邊數(shù)量的增加,三角形數(shù)量也隨之增加.如圖8所示,DER方法產(chǎn)生的大量噪音邊使得擾動后的三角形數(shù)量急劇增加,尤其是在大規(guī)模數(shù)據(jù)集data3和data4中,如圖8(c)(d)所示,DER方法擾動后的三角形數(shù)量超過原數(shù)據(jù)的2倍.這是因為DER方法需要進行聚類劃分,在社區(qū)密集處添加擾動邊對三角形數(shù)量的影響要大于非密集處.對比DER,dp-noisy方法則可以在隱私預(yù)算取較大值時達到很好的數(shù)據(jù)可用性.

綜上所述,在相同的隱私預(yù)算下,和LWSPA相比,dp-noisy的數(shù)據(jù)可用性與其相當(dāng); 與DER相比則有更好的數(shù)據(jù)可用性,尤其在大規(guī)模的數(shù)據(jù)集上具有顯著的效果,同時也解決了現(xiàn)有帶權(quán)圖擾動方法無法抵御結(jié)構(gòu)攻擊的問題.

針對邊權(quán)值的分析,實驗通過對比圖的平均最短路徑來反映權(quán)值的數(shù)據(jù)有效性.如圖9所示,隨著隱私預(yù)算的增加,向數(shù)據(jù)集中添加的噪音將會減少,因此平均最短路徑會更接近原始數(shù)據(jù).而DER方法則因為聚類之后引入大量的噪音邊導(dǎo)致平均最短路徑長度低于原始數(shù)據(jù),因此無論何種規(guī)模的數(shù)據(jù)集,其數(shù)據(jù)可用性均最差.當(dāng)數(shù)據(jù)規(guī)模較小時,dp-noisy的數(shù)據(jù)可用性優(yōu)于LWSPA方法; 當(dāng)數(shù)據(jù)規(guī)模增大時,如圖9(c)(d)所示,LWSPA的數(shù)據(jù)可用性有明顯提升,但dp-noisy仍實現(xiàn)了效果最好的數(shù)據(jù)可用性.

針對dp-noisy生成的擾動圖中權(quán)值及其屬性要保持不變,需滿足約束條件盡可能完整,約束不等式的數(shù)量在一定程度上決定了最終約束的完整性.表2記錄了本實驗在數(shù)據(jù)集data1,data2,data3,data4上每個階段產(chǎn)生的約束不等式數(shù).

Table 2 Number of Constraint Inequality表2 約束不等式數(shù)量表

由表2可知,本方法執(zhí)行過程中矩陣A中的約束不等式數(shù)量大于圖中的邊數(shù)量,則可認(rèn)為本方法得出的邊權(quán)值屬性與原圖保持一致.

5 結(jié) 論

由于大規(guī)模數(shù)據(jù)應(yīng)用社交網(wǎng)絡(luò)的普及,社交用戶之間的邊關(guān)系不能簡單地同一化,其敏感度將直接影響到隱私的分布和保護方法的效能.本文針對帶權(quán)值的社交網(wǎng)絡(luò)提出了基于差分隱私機制的保護方法,該方法采用改進的單源最短路徑約束模型構(gòu)建邊權(quán)值噪音,最大程度上保證擾動后的社交網(wǎng)絡(luò)圖的數(shù)據(jù)可用性.仿真實驗表明,當(dāng)數(shù)據(jù)集規(guī)模最大時(此時節(jié)點數(shù)目為30 000),本文所提出的方法在運行效率上比K-MPNP提高了47.3%,比LWSPA提高了41.8%,比DER提高了52.6%.在相似的數(shù)據(jù)隱私保護程度下,dp-noisy的數(shù)據(jù)可用性比lp-noisy提高了10%,顯著優(yōu)于DER的數(shù)據(jù)可用性,略好于LWSPA.當(dāng)數(shù)據(jù)集規(guī)模最大時,dp-noisy的平均擾動質(zhì)量比lp-noisy提高了14%,比DER提高了11.3%,比K-MPNP提高了27%,比LWSPA略低了3.6%; 而實際應(yīng)用中為了保證數(shù)據(jù)效用,都會選擇較高的隱私預(yù)算(例如蘋果公司選擇的隱私預(yù)算通常會在ε≤10時盡可能取最大值),因而當(dāng)選擇ε=10時,dp-noisy的擾動質(zhì)量比LWSPA提升了6%.綜上,dp-noisy具有較高的運行效率和數(shù)據(jù)效用,同時滿足抵御圖結(jié)構(gòu)攻擊的特性,且可適用于大規(guī)模的社交網(wǎng)絡(luò)數(shù)據(jù)分析.

然而,本文提出的方法仍然存在一些問題有待深入研究.例如,單源最短路徑模型是否可以進行優(yōu)化,進一步減少不等式的數(shù)量從而提高算法的運行效率.后續(xù)工作將考慮根據(jù)對參數(shù)的不同需求優(yōu)化模型,減少需求較低的屬性約束.