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

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

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

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

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

本文的主要貢獻(xiàn)有3個(gè)方面:

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

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

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

1 相關(guān)工作

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

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

2 約束模型和算法描述

2.1 差分隱私定義和模型

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

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

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

(1)

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

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

(2)

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

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

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

2.2 約束模型

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

(3)

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

(4)

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

3 差分隱私擾動(dòng)模型

3.1 單源最短路徑約束模型

在本節(jié)中,通過(guò)單源最短路徑算法建立圖的約束模型.設(shè)G為原始社交網(wǎng)絡(luò)圖,E為圖中全體邊的集合,V為全體節(jié)點(diǎn)集合,W為邊對(duì)應(yīng)的權(quán)值集合.初始化V0={v0},其中v0為給定的源點(diǎn).通過(guò)改進(jìn)的Dijkstra算法[16]在每一步選擇節(jié)點(diǎn)添加到生成樹的過(guò)程中構(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集合為下一步可到達(dá)的所有點(diǎn)集合*

③ END FOR

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

⑤V=V-V0;

⑥v0=rand(V);

⑦V0={v0};

⑧ GOTO ①;

⑨ END IF

⑩ WHILEQ≠?

w(u,v)};

w(u,v)};

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

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

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

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

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

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

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

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

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

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

3.2 差分隱私噪音添加

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

因此f的敏感度為

w(u′,v′)|,

(5)

其中，P(u,v)表示節(jié)點(diǎn)u和節(jié)點(diǎn)v間的最短路徑的邊集合,w′和w分別表示擾動(dòng)前后邊(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的輸入是需要添加噪音擾動(dòng)的原始圖數(shù)據(jù)G,E,V,W,生成樹序列T,以及約束矩陣A和隱私預(yù)算ε1,最終得到擾動(dòng)圖G′.首先我們將集合E分成ET和EN兩個(gè)部分,其中ET為構(gòu)成生成樹的邊集合；先對(duì)ET中的邊權(quán)值添加Laplace噪聲,再將加噪之后的權(quán)值帶入約束不等式中,可解得EN中的邊權(quán)值約束,并生成新的權(quán)值.在每個(gè)生成樹ti中,我們選擇若干原來(lái)不存在邊的節(jié)點(diǎn)對(duì)(u,v)構(gòu)造一條新邊,比較ti中最大邊權(quán)值與f(u,v),選擇其中較小的一個(gè)作為邊權(quán)值.

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

(6)

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

算法3.節(jié)點(diǎn)擾動(dòng)算法.

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

輸出：G′.

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

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

(7)

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

3.3 隱私保護(hù)分析

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

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

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

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

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

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

4.1 性能分析

本文在表1中4個(gè)不同規(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)方法的運(yùn)行效率進(jìn)行了對(duì)比.如圖1(a)所示,其中dp-noisy方法、lp-noisy方法和K-MPNP都是采用單源最短路徑原理來(lái)擾動(dòng)社交網(wǎng)絡(luò)圖中的邊權(quán)值.圖1中橫坐標(biāo)表示數(shù)據(jù)集的編號(hào),縱坐標(biāo)表示運(yùn)行時(shí)間(單位s).

Fig. 1 Running time圖1 運(yùn)行時(shí)間

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

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

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

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

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

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

Fig. 4 Ratio of modified edges圖4 擾動(dòng)邊比例

(8)

Fig. 3 Average recognition rate comparison圖3 平均識(shí)別率對(duì)比圖

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

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

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

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

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

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

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

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

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

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

Fig. 7 Edge disturbance圖7 邊數(shù)擾動(dòng)對(duì)比

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

Fig. 9 Average shortest path圖9 平均最短路徑對(duì)比

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

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

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

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

針對(duì)邊權(quán)值的分析,實(shí)驗(yàn)通過(guò)對(duì)比圖的平均最短路徑來(lái)反映權(quán)值的數(shù)據(jù)有效性.如圖9所示,隨著隱私預(yù)算的增加,向數(shù)據(jù)集中添加的噪音將會(huì)減少,因此平均最短路徑會(huì)更接近原始數(shù)據(jù).而DER方法則因?yàn)榫垲愔笠氪罅康脑胍暨厡?dǎo)致平均最短路徑長(zhǎng)度低于原始數(shù)據(jù),因此無(wú)論何種規(guī)模的數(shù)據(jù)集,其數(shù)據(jù)可用性均最差.當(dāng)數(shù)據(jù)規(guī)模較小時(shí),dp-noisy的數(shù)據(jù)可用性優(yōu)于LWSPA方法; 當(dāng)數(shù)據(jù)規(guī)模增大時(shí),如圖9(c)(d)所示,LWSPA的數(shù)據(jù)可用性有明顯提升,但dp-noisy仍實(shí)現(xiàn)了效果最好的數(shù)據(jù)可用性.

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

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

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

5 結(jié) 論

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

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