帶權值的大規模社交網絡數據隱私保護方法

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

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

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

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

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

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

1) 針對帶權值的社交網絡圖的特征,在約束模型下區分圖中的關鍵邊和非關鍵邊,基于差分隱私模型,分別添加不同的噪音達到隱私保護的同時最大程度保留了數據的可用性;

2) 設計了帶權社交網絡中的節點和邊的擾動策略,使得算法具有抵御圖結構攻擊的能力;

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

1 相關工作

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

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

2 約束模型和算法描述

2.1 差分隱私定義和模型

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

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

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

(1)

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

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

(2)

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

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

上述性質將運用到本文的隱私算法設計中.

2.2 約束模型

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

(3)

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

(4)

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

3 差分隱私擾動模型

3.1 單源最短路徑約束模型

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

算法1.約束模型建立.

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

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

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

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

③ END FOR

④ IFQ=?且V-V0≠?*當圖G不聯通時,遍歷完1個聯通區域后重新設置源點*

⑤V=V-V0;

⑥v0=rand(V);

⑦V0={v0};

⑧ GOTO ①;

⑨ END IF

⑩ WHILEQ≠?

w(u,v)};

w(u,v)};

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

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

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

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

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

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

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

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

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

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

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

相比于以上2種方式，針對帶權值的社交網絡數據而言,單源最短路徑可以直接在圖結構上操作執行，其簡明性、應用廣泛和較高的執行效率也使之成為各類隱私保護方案中最常用的模型,因此本文選擇單源最短路徑來建立模型.

3.2 差分隱私噪音添加

在帶權值的社交網絡圖中的噪聲添加不同于無權值圖,一條邊的權值改動將會影響整個圖的結構,如最短路和最小代價生成樹,都會發生相應的改變.因此本文采用算法1表示的約束模型對添加噪音進行線性約束.

因此f的敏感度為

w(u′,v′)|,

(5)

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

具體添加算法如下：

算法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)中線性規劃的求解結果*

⑥ END FOR

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

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

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

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

(6)

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

算法3.節點擾動算法.

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

輸出：G′.

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

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

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

(7)

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

3.3 隱私保護分析

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

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

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

4 實驗與結果

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

Table 1 Number of Nodes and Edges in 4 Data Sets表1 4個不同數據集的節點數和邊數

4.1 性能分析

本文在表1中4個不同規模的數據集上將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都是采用單源最短路徑原理來擾動社交網絡圖中的邊權值.圖1中橫坐標表示數據集的編號,縱坐標表示運行時間(單位s).

Fig. 1 Running time圖1 運行時間

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

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

4.2 隱私保護質量分析

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

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

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

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

(8)

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

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

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

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

針對圖結構的識別攻擊是通過發布特殊形狀的子圖到網絡中,在擾動后根據該子圖確定擾動圖中目標節點的位置.實驗通過統計不同相似度的子圖的匹配數來反映隱私保護質量.為了方便比較,隱私預算ε取值都為1,其中dp-noisy隱私預算分配為ε1∶ε2∶ε3=2∶1∶2.

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

Fig. 5 Matching number comparison圖5 匹配數對比

4.3 數據可用性分析

對于帶權值的社交網絡圖數據而言,數據可用性分析將分成2個部分進行：一是社交網絡的結構特征參數分析,二是邊權值分析.

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

Fig. 6 Clustering coefficient comparison圖6 聚集系數對比

Fig. 7 Edge disturbance圖7 邊數擾動對比

Fig. 8 Number of triangles圖8 三角形數量對比

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

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

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

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

綜上所述,在相同的隱私預算下,和LWSPA相比,dp-noisy的數據可用性與其相當; 與DER相比則有更好的數據可用性,尤其在大規模的數據集上具有顯著的效果,同時也解決了現有帶權圖擾動方法無法抵御結構攻擊的問題.

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

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

Table 2 Number of Constraint Inequality表2 約束不等式數量表

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

5 結 論

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

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