一種基于差分隱私保護的社交網(wǎng)絡發(fā)布圖模型

石秀金， 李寒悅

(東華大學 計算機科學與技術學院， 上海 201620)

0 引 言

社交網(wǎng)絡分析是一種重要的預測工具，由于社交網(wǎng)絡的數(shù)據(jù)需要通過“發(fā)布”來面向大眾，往往可以通過深層次的分析獲得一些藏匿在已經(jīng)“發(fā)布”信息中的真實知識，甚至包括部分隱私信息。在滿足社交網(wǎng)絡分析應用的前提下，對隱私數(shù)據(jù)進行有效的保護是非常必要的。

社交網(wǎng)絡圖隱私保護技術的研究大多是對于圖匿名化的研究[1-3]，這種方法可將一條記錄隱藏在一組記錄當中，其缺陷是很容易受到去匿名化的攻擊，無法真正地達到保護社交網(wǎng)絡中的隱私[4-5]。差分隱私機制[6-7]的提出解決了上述方法所遇到的問題,可以達到很好的保護效果，確保數(shù)據(jù)不會被泄露。本文的主要工作：

(1)將社交網(wǎng)絡原始圖按照節(jié)點分成多個子圖，每個子圖中邊的聯(lián)系較為緊密，子圖之間邊的聯(lián)系較弱；

(2)將分類后的每個子圖通過層次隨機圖模型進行子圖區(qū)域劃分，并在生成樹的葉子節(jié)點上添加相應的噪聲，再構建待發(fā)布圖；

(3)基于對度發(fā)布和聚類系數(shù)等攻擊者最希望獲得的統(tǒng)計數(shù)據(jù)，通過實驗分析，驗證了生成的待發(fā)布圖與原始圖的一致性，證明算法是有效的。

1 基本概念

社交網(wǎng)絡表示為無向圖G，G中的每個節(jié)點代表社交網(wǎng)絡中的用戶，每一條邊代表2個對象之間的聯(lián)系，如果2個節(jié)點之間沒有邊則代表兩者沒有聯(lián)系。數(shù)學符號表達如下:

圖G:G(U,E),U是所有節(jié)點的集合，E是所有邊的集合；

節(jié)點集：U={Ui|i=1,2,…,n}，其中n是節(jié)點的個數(shù)；

1.1 層次隨機圖模型(HRG)

層次隨機圖模型是基于無向圖的。假設：

(1)社交網(wǎng)絡G是具有n個結(jié)點的簡單無向圖；

(2) 樹狀圖D是一顆二叉樹，由n個葉子節(jié)點和n-1個父節(jié)點所組成，n個葉子節(jié)點代表了社交網(wǎng)絡中的n個用戶，每個父節(jié)點r有2個子樹；

(3)連接強度pr是父節(jié)點r的屬性，表示在該父節(jié)點下，左右子樹之間的連接強度,由左右子樹之間的邊的個數(shù)Er除以左右子樹的節(jié)點個數(shù)Lr和Rr之積得來，公式如下：

(1)

層次隨機模型由以上3個概念組合而成，是將無向圖轉(zhuǎn)化為二叉樹的形式，而二叉樹的結(jié)構是由樹中每個父節(jié)點的連接強度決定。

1.2 差分隱私保護(DP)

差分隱私的方法是基于“鄰居”數(shù)據(jù)集的概念下發(fā)展起來的，鄰居數(shù)據(jù)集指的是和原來的數(shù)據(jù)集有差別且差別僅為一條記錄的數(shù)據(jù)集。

定義ε-差分隱私保護：設有隨機算法M，PM為算法M所有可能輸出結(jié)構的集合。對于任意兩個鄰近數(shù)據(jù)集D和D'以及PM的任意子集SM，若算法M滿足：

Pr[M(D)∈SM]≤eε*Pr[M(D')∈SM]

則算法M提供ε-差分隱私保護，其中，參數(shù)ε稱為隱私保護預算，ε越小，隱私保護水平越高。

2 CHRG-DP算法設計

將社交網(wǎng)絡圖分成若干個內(nèi)部具有很高關聯(lián)度的子圖，分別用HRG模型將每個子圖變成一顆二叉樹，圖中的節(jié)點都在二叉樹的葉子節(jié)點上，并對節(jié)點進行噪聲添加，將擾動后的每個HRG合并形成一個完整的HRG，最后將經(jīng)過擾動的完整的HRG還原成社交網(wǎng)絡發(fā)布圖發(fā)布，可以使社交網(wǎng)絡圖的噪聲添加更為合理，更有效率。

2.1 圖分類

首先對社交網(wǎng)絡圖G進行深度優(yōu)先的搜索，同時計算出圖中每個節(jié)點完成深度搜索的時間t，再按照訂單完成深度搜索的速度進行排序，對圖的逆圖也進行深度優(yōu)先搜索，逆圖DFS得到的森林即為連通區(qū)域。

2.2 HRG生成及加噪

將社交網(wǎng)絡圖分類成若干個子圖后，算法通過隨機層次圖模型將生成的子圖序列中每一個子圖轉(zhuǎn)化成對應二叉樹，圖中的每個節(jié)點都分布在二叉樹的葉子節(jié)點當中，一個原始社交網(wǎng)絡圖均存在多種HRG的方案。當圖的規(guī)模很大時，無法逐一尋找得到最優(yōu)HRG方案。使用馬爾科夫蒙特卡洛方法，可以縮短計算過程。算法隨機構建一個HRG作為馬爾科夫鏈的初始狀態(tài)，然后當馬爾科夫鏈未收斂時進行多次循環(huán)，每次循環(huán)決定了狀態(tài)轉(zhuǎn)移的順序。在生成HRG時，使用指數(shù)機制進行一定程度的隱私保護。生成HRG(SG,ε)算法的過程如下：

算法:生成HRG(SG,ε)

輸入: 子圖(SG),隱私預算ε

輸出: HRG T’

(1)隨機構建一個HRG作為馬爾科夫鏈的初始狀態(tài)；

(2)當馬爾科夫鏈未收斂時；

(3)選擇HRG中一個節(jié)點；

(4)變換n的相鄰子樹后，得到HRG方案T’；

(5)變換概率小于min時，接受轉(zhuǎn)變；

(6)返還最優(yōu)HRG方案。

2.3 HRG合并生成社交網(wǎng)絡發(fā)布圖

算法的第三步，是將添加噪子圖的HRG集合合并成一個完整的HRG，再還原成社交網(wǎng)絡的形式生成發(fā)布圖。滿足差分隱私保護模型的目的在于對原始社交網(wǎng)絡圖添加噪聲擾動從而保護數(shù)據(jù)的安全性和穩(wěn)定性，所以首先要將子圖的HRG集合合并成一個完整的HRG，并在發(fā)布之前，將其還原為復雜圖的形式。社交網(wǎng)絡發(fā)布圖生成(G，T)算法的過程如下：

輸入: 原始圖G,HRGT

輸出: 社交網(wǎng)絡發(fā)布圖G’

(1)將原始圖中所有節(jié)點加入輸入結(jié)果G’中；

(2)選擇G’中任意兩個節(jié)點i和j；

(3)在層次隨機圖T中找出節(jié)點i和j最低祖先節(jié)點的概率值；

(4)根據(jù)最低祖先節(jié)點的概率值選擇是否在i和j中間添加一條邊；

(5)返還社交網(wǎng)絡發(fā)布圖。

2.4 隱私預算分配

本論文將隱私保護預算值ε分成了3個部分εc，εg，εa，其中把εc添加給連接2個子圖之間的邊，εg在生成HRG圖時使用指數(shù)機制對邊進行差分隱私保護，εa在合并生成HRG圖時進行差分隱私保護。

3 實驗結(jié)果及分析

算法在Window10 64位操作系統(tǒng)中用Java語言實現(xiàn)。實驗采用了2個數(shù)據(jù)集Douban和Flixster，Douban是中國在線推薦網(wǎng)站豆瓣，只要用戶與用戶對于同一話題關注，2個用戶之間就存在一條“邊”。Flixster是一家美國社交電影網(wǎng)站，當2個用戶對于同一類的電影感興趣的時候，2個用戶之間就存在聯(lián)系。算法選取節(jié)點的度分布與圖聚類系數(shù),這2個攻擊者最希望能從社交網(wǎng)絡圖獲取的特征作為指標,通過和傳統(tǒng)的差分隱私保護方案Tr-DP及基于密度的節(jié)點探索和重構方法DER算法的對比來檢測CHRG-DP算法的性能。實驗數(shù)據(jù)集可見表1。

表1 實驗數(shù)據(jù)集

圖1將3種算法在不同的隱私保護預算下對2組社交網(wǎng)絡數(shù)據(jù)集的度分布分別進行了計算，以KL散度作為檢測指標，代表隱私保護后的社交網(wǎng)絡數(shù)據(jù)與原始數(shù)據(jù)之間的分布趨勢，KL散度越小表示分布相似性越高。實驗結(jié)果顯示,CHRG-DP算法不會隨著隱私控制參數(shù)ε進行大幅度改變，無論隱私保護水平如何，KL散度百分比波動很小，都可以達到很好的保護效果。由此可見，CHRG-DP算法相較于傳統(tǒng)的差分隱私，基于密度的重構法有較大的優(yōu)越性。

圖2利用平均相對誤差指標從聚類系數(shù)的角度比較CHRG-DP、DRG和Tr-DP這3種算法的社交網(wǎng)絡發(fā)布圖的可用性。實驗結(jié)果表明，隨隱私保護預算的增加，CHRG-DP算法的差值呈平穩(wěn)下降的趨勢，并且誤差始終是3種算法中最小的；在預算值較大的時，CHRG-DP產(chǎn)生的查詢結(jié)果準確性較高。此外，F(xiàn)lixster數(shù)據(jù)集比Douban擁有更多的數(shù)據(jù)，CHRG-DP算法在對較大數(shù)據(jù)集時產(chǎn)生查詢結(jié)果的準確性依然比較高。

圖2 聚類系數(shù)與ε分析圖

4 結(jié)束語

本文從社交網(wǎng)絡發(fā)布數(shù)據(jù)的用戶隱私保護方向出發(fā)，在保證發(fā)布圖的有用性與原社交網(wǎng)絡圖的結(jié)構一致性的基礎上，設計了一種新的算法，主要包含3個過程：將社交網(wǎng)絡原始圖分類成若干個內(nèi)部關聯(lián)度較高的子圖，再將子圖通過層次隨機圖模型建立最適合的HRG，合并形成總HRG，通過HRG再還原生成社交網(wǎng)絡發(fā)布圖。最后通過度分布與聚類系數(shù)等社交網(wǎng)絡最基本的特性指標驗證了發(fā)布圖的有用性，實驗結(jié)果表明提出的CHRG-DP算法比傳統(tǒng)的差分隱私保護算法以及基于密度的重構法具有更好保護性和查詢準確性。