基于三元閉包的不確定社交網絡隱私保護算法?

彭擎宇 文中華，2 原偉杰

（1.湘潭大學計算機學院網絡信息安全學院 湘潭 411105）（2.海南熱帶海洋學院計算機科學與技術學院 三亞572022）（3.湖南工程學院計算機與通信學院 湘潭 411104）

1 引言

隨著互聯網技術的飛速發展，第五代移動通訊技術（簡稱5G 技術）的不斷發展［1］，越來越多的人投入到社交網絡中進行交流并共享信息。例如：2016 年Facebook 每月擁有14 億用戶，擁有9 億每日活躍用戶［2］。隨著時間的增加社交網絡中累計了大量的用戶數據，大部分用戶的身份信息，社會關系信息等敏感信息將被發布到網絡中，這些信息都會成為攻擊者的攻擊目標，所以在發布社交網絡數據時保證個人的匿名性是一個具有挑戰性的研究問題。迄今為止提出的匿名化社會圖的方法大概可分為3 大類：1）k度匿名保護模型，該模型將頂點分組為至少k個大小的超級頂點，使目標的隱私泄露的可能性<1/k，其中k是所需的匿名水平；2）通過隨機添加、刪除或切換邊緣的形式向數據添加噪聲的方法，從而使攻擊者不能夠依靠背景知識準確地識別原始圖結構的方法；3）通過向原始圖注入不確定性生成不確定圖，改變圖屬性的方法。目前在計算機科學、工業科學、社會科學、自然科學、生物科學等眾多研究領域都存在著不同程度的不確定性［3］。

根據以上三類不同的研究學者提出了不同的研究方法，例如：Fard 等提出的一種鄰居隨機的邊擾動方法［4］；P.L.Lekshmy 等提出的加快隱私保護內核K均值聚類的混合保護方法［5］；Varsha提出的在保留隱私的情況下識別社交網絡中的傳播者［6］；Nguyen 等在提出一種不確定隱私保護方法通過方差最大化的方法來衡量隱私與效用之間的聯系［7］；以上研究方法主要針對靜態社會網絡，而對處于動態變化中的社交網絡適用性不好。另外，這些隱私保護方法在著重于加大圖的隱私性保護程度的時候對圖數據效用的破壞程度較高。

三元閉包原則是一個社交網絡中的基本原則：在同一個社交網絡中，如果兩個人之間有一個共同的朋友，那么這兩個人在未來成為朋友的可能性就會提升。根據三元閉包的基本原則，眾多研究者把它作為社交網絡中推薦算法和重要的鏈接生成算法的基礎。Giuliana等在研究Twitter的社交網絡的時候，使用了HIT 算法得到了朋友的推薦結果并且產生了不錯的效果［8］。Peng 等通過引文網絡中的引文鏈接的生成，證明了三元閉包方法是多種網絡生成新鏈接的重要原則［9］。Bianconi等以社交網絡節點數和聚集度為基礎建立了簡單的社交網絡模型，該模型可以自然導致社區出現［10］。這些研究說明了三元閉包方法可以一定程度的預測社交網絡生長結果。

針對上述問題，本文提出一種基于三元閉包的不確定圖的社會網絡隱私保護方法，主要貢獻是：1）考慮到社交網絡本身存在的動態性，本文使用了三元閉包方法生成潛在邊，更好地反映真實的社交網絡環境，有效地保護了社交網絡隱私。2）對含有潛在邊的社會網絡圖使用(k,ε)-模糊方法注入不確定性，在保持原圖高效用的情況下對原圖提供有效的保護。

2 相關定義

定義1：對于給定無向圖G=(V,E)，其中V是頂點集，E是邊集。我們使用Vp表示邊集V中的所有無序頂點對，即Vp={(vi,vj} |1 ≤i≤j≤1}。

定義2：對于給定圖G，如果存在映射p:Vp→[0,1]是每條邊存在的概率函數，則G'=(V,p)是關于G的不確定圖。

定義3：（潛在邊）根據三元閉包原則：如果兩個人有共同的朋友，這兩個人將來成為朋友的概率就會增加。在原始社交網絡中如果節點A與節點B具有共同的朋友C，則節點A與B間存在潛在邊。

定義4：不確定圖G’ 誘導了一個可能世界W(G') ，W?W(G') 是 一 個 圖W=(V,EW)，其 中EW?EC，則不確定圖G’中的邊的概率表明W的概率為

其中，EW為引入不確定性的頂點集合，p(e)為邊存在的概率，且不確定圖中不同的邊的概率分布是相互獨立的。

定義5：給定一個不確定圖G'，假定攻擊者知道他的目標頂點和一些頂點的性質P，令Ωp為P取值的域。當P 代表的是所有頂點的度的時，Ωp={0 ,…,n-1} 。則對每個v?G'并且w?Ωp，頂點v?G并且具有屬性P的概率為

其中Pr(W)由式（1）中給出，χv,w(W)是一個0-1 變量，它指示頂點v是否在可能的世界W中具有w的屬性值。同樣，圖G中具有屬性值w的頂點v在G’中像的概率Yw(v)為

定義6：(k,ε)-模糊處理（以后都稱(k,ε)-模糊），如果P為頂點性質，k≥1 是所需要的模糊水平，ε≥0 是一個容許參數。當G’的頂點分布熵大于或者等于log2k時，不確定圖G’就可以被稱為關于屬性P在v?G的k-模糊，即：

定義7：如果對于v?G'并且令e1,…,en-1是包含頂點v的n-1 個頂點對，那么對于每一個1 ≤i≤n-1，ei是一個隨機的伯努利變量，dv是v的度所對應的隨機變量，則有：

那么對于v的每一個可能的度w?Ωp，都有：

如果式（5）中含有大量的加法，我們可以用高斯分布近似的表示dv，如下所示：

定義8：如果P 是圖G 在頂點集合V 上的一個屬性，P:V→Ωp，并且參數θ>0，對于任意屬性值w?Ωp，則有屬性值w的θ-共性Cθ(w)和θ-唯一性Uθ(w)分別為

定義9：為了使不確定圖G'能夠更好地保持原始圖G的特性，設置了一個[0 ,1] 截斷的高斯分布。

3 相關算法

3.1 基于三元閉包的潛在邊算法

對于一個社交網絡圖GY=(V,EY)，其中V為頂點集，EY為邊集。我們對GY進行加邊處理后可得到圖G，如圖1所示。

圖1 原始圖和加入潛在邊的圖

相關算法如下：

算法1：潛在邊算法

輸入：初始圖GY=(V,EY)，節點集為V，邊集為EY，需求添加的邊數ex；

輸出：加入潛在邊的新圖G=(V,E)，新邊集E。

1：E←?,i=0

2：WHILEi

3：RANDOMLY PICK A PAIR OF VERTICESu,v，AND (u,v)?EY，dis(u,v)=2

4：EY←EY∪(u,v)

5：i=i+1

6：E←EY

7：RETURNG=(V,E)，E

原圖經過處理后，通過加入潛在邊可以使部分頂點的某些屬性P發生改變，實現部分隱私保護的效果。例如，某些文獻都認為攻擊者知道目標頂點的某些性質P［12~15］，比如知道頂點的度、頂點及其鄰域的度。

3.2 使用(k,ε)-模糊算法對圖G 進行模糊處理

算法2 的目的是找到可以往圖G中注入最小不確定性又可以符合條件的(k,ε)-模糊的不確定圖，算法3是算法2的子算法，在給定不確定性的參數σ的條件下，找到圖G的(k,ε)-模糊圖。

算法2：(k,ε)-模糊算法

輸入：G=(V,E)，頂點屬性P，模糊等級k，容許參數ε，尺寸乘子c，以及白噪聲水平q；

輸出：G關于屬性P是(k,ε)-模糊的不確定圖G'F。

1：σι←0

2：σu←1

3：REPEAT

4：<ε',G'>←obfuse(G,σu,P,k,ε,c,q)

5：IFε'=∞THENσu←2σu

6：UNTILEε'≠∞

7：G'F←G'

8：WHILEσl+σ<σudo

9：σ←(σu+σl)/2

10：<ε',G'>←obfuse(G,σu,P,k,ε,c,q)

11：IFε'=∞THENσl←σ

12：ELSEG'F←G'；σu←σ

13：RETURNG'F

算法2 是圖G關于頂點性質P的(k,ε)-模糊算法，旨在通過對不確定參數σ的調整，注入最小的不確定性，達到較高的實用性，實現所需要的模糊效果。

算法3：子算法obfuse算法

輸入：G=(V,E),P,k,ε,c,q以及標準差σ；

輸出：<ε',G'>，其中G’是一個在ε'<ε時的(k,ε')-模糊或在ε'=∞時(k,ε')-模糊不成立。

1：FOR ALLv?VCOMPUTE THEσ-uniquenessUσ(P(v))

2：H←THE SET OF

|VERTICES WITH LARGESTUσ(P(v))

3：FOR ALL

4：ε'←∞

5：FORtTIMES DO

6：EC←E

7：REPEAT

8：RANDOMLY PICK A VERTEXu?VHACCORDING TOQ

9：RANDOMLY PICK A VERTEXv?VHACCORDING TOQ

10：if(u,v) ?E THEN EC←EC{(u,v)}

11：ELSEEC←EC∪{(u,v)}

12：UNTILE |EC| =c|E|

13：FOR ALLe?ECDO

14：COMPUTEσ(e)

15：DRAWwUNIFORMLY AT RANDOM FROM [0,1]

16：ifw

17：THEN DRAWreUNIFORMLY AT RANDOM FROM [0,1]

18：ELSE DRAWreFROM THE RANDOM DISTRIBUTIONRσ(e)

19：IFe?ETHENp(e)←1-reELSEp(e)←re

20：ε''←|{v?V:not k-obfuscated by G''=(V,p)| |V|

21：IFε''<ε'and ε''<εTHENε'←ε''；G'←G''

22：RETURN <ε',G'>

子算法obfuse算法在給定的標準差參數σ的條件下找出圖G的(k,ε)-模糊圖G'。首先，該算法計算了每個頂點v?V的σ-唯一性級別Uσ(P(v))。然后，第14 行將根據頂點唯一性的不同，重新分配的所有頂點對e?Ec的唯一性級別將按下式分配。

最后，通過給定邊的不確定水平σ(e)，為每個頂點對e?Ec選擇一個隨機擾動re（定義9），得到(k,ε)-模糊圖G'。

4 實驗結果

由于不同的隱私方法在評價隱私保護效果時方法有差別，本文將采用邊熵來度量不同隱私保護算法的隱私性；采用文獻［16］中提供的統計方法度量生成的不確定圖的數據效用性。

4.1 隱私性度量

定義10：不確定社交網絡圖中，邊的不確定程度越高，不確定方法對原始社交網絡的保護越好。即邊熵Ente的值越高圖的隱私性越強。

其中，e?G'，p(ei)該邊存在的概率，Ente為不確定圖的邊熵。

4.2 數據效用性度量

定義11：我們用d1,…,dn來表示圖GY中的度序列。如果對于函數F，有S=F(d1,…,dn)，則稱S為基于度的統計量。

根據定義11：我們可推理如下統計量：

邊的個數（Number of edges）：

節點的平均度（Average degree）：

度方差（Degree variance）：

當圖G'是一個不確定圖時，d1,…,dn將是隨機變量。如果F是線性函數則我們能推出：

4.3 實驗結果及隱私性對比分析

本次實驗中我們選用了斯坦福大學公開的三個大型網絡數據集，Facebook、Twitch和Github。

表1 為潛在邊算法的實驗結果，通過對原圖加入潛在邊，然后使用(k,ε)-模糊算法注入不確定性達到隱私保護的目的。從表1 中可看出隨著潛在邊的增加，得到的不確定圖的邊熵也在明顯增加。

表1 潛在邊算法的邊熵變化

表2 是使用差分隱私法得到的實驗結果，從表2 可以看出隨著節點數量的增加，邊熵也在明顯的增加。但是在不同的隱私預算的情況下，邊熵的變化并不明顯。

表2 差分隱私法的邊熵變化

根據表3 可以看出，隨著加邊數量的增加，潛在邊算法的數據效用逐漸降低。而差分隱私算法的數據效用明顯弱于潛在邊算法。

表3 兩種算法的數據效用比較圖

我們從三張表可以看出，差分隱私算法雖然有較高高的隱私性，但是數據效用太低，常用的隱私網絡不需要這么高的隱私性，而且差分隱私法對原始圖的破壞程度較大，適用范圍較為有限。而潛在邊算法在保持較好的隱私性的同時，數據效用極好，在用于社交數據挖掘和分析的時候能起到更好的效果。另外我們可以通過調整加入的邊ex的大小，和模糊程度k的大小來獲得我們所需要的隱私保護程度與數據效用，對不同的真實社交網絡達到不同的保護效果。同時，所加入的潛在邊為對真實社交網絡又有一定的預測性，所以在真實社交網絡發生變化時也具有一定的隱私保護能力，具有一定的動態性。

5 結語

本文介紹了一種新的社交網絡的隱私保護方法，該方法通過向原始網絡中加入一些預測邊，來適用社交網絡的動態變化，然后對修改后的圖注入不確定性形成不確定圖，從而達到隱私保護的目的。該方法相對其他不確定的隱私保護方法，適用范圍較廣，可以在不同環境中動態調整隱私保護程度。后續工作是提升對動態社會網絡的適用性，使所加入的潛在邊能夠更加精準地預測社交網絡的動態變化情況。