殷軼平，徐睿峰

(1.哈爾濱工業(yè)大學深圳研究生院 計算機科學與技術(shù)學院，廣東 深圳 518055；2.哈爾濱工程大學 國家保密學院，黑龍江 哈爾濱 150001)

0 引言

近年來，以Twitter、Facebook、微博為代表的在線社交網(wǎng)絡得到飛速發(fā)展。由于可以實時獲取海量真實用戶的用戶屬性、個人表達、交互關(guān)系等內(nèi)容，社交網(wǎng)絡被廣泛用于用戶建模、社區(qū)發(fā)現(xiàn)、信息推薦等應用和研究。例如Facebook作為全球最受歡迎的在線社交網(wǎng)絡之一，擁有大量的好友關(guān)系信息，可以被用來分析社群關(guān)系，挖掘社會觀點。然而，一些存在的關(guān)系可能被用戶視為敏感信息，直接發(fā)布會導致個人信息的嚴重泄露。2018年3月16日，美國紐約時報曝光Facebook超過5000萬用戶的個人信息數(shù)據(jù)被泄露并被用于選舉干預等非法行為。這一事件突顯出社交媒體數(shù)據(jù)的濫用可能帶來的嚴重后果，為數(shù)據(jù)持有者敲響了警鐘。因此，在發(fā)布社交媒體數(shù)據(jù)之前，必須對其進行處理，使數(shù)據(jù)在具有隱私保證的基礎(chǔ)上支持相關(guān)的研究工作。

因此，考慮到社交網(wǎng)絡數(shù)據(jù)的緊密關(guān)聯(lián)性，本文研究將注意力放在添加盡可能少的噪聲來實現(xiàn)圖數(shù)據(jù)的差分隱私保護。為此，本文提出了一種非交互式的嚴格差分隱私方法，稱為DP2Gsister(Two- phase Differential Privacy for Gsister)。這一方法的主要思想是分兩個階段實現(xiàn)差分隱私以形成與原圖結(jié)構(gòu)信息相似且具有隱私保證的發(fā)布圖Gsister。第一階段引入層次隨機圖模型重構(gòu)圖結(jié)構(gòu)特征，用滿足ε1-差分隱私的MCMC在原圖上采集樣本Tsample；第二階段計算Tsample的連接概率，對其添加隱私預算為ε2的拉普拉斯噪聲以生成概率噪聲序列{Pn}；然后按照概率序列生成發(fā)布圖Gsister。對于給定的社交網(wǎng)絡數(shù)據(jù)集，本研究的目標是:(1)實現(xiàn)單次發(fā)布和增量發(fā)布社交網(wǎng)絡圖的邊差分隱私；(2)盡可能地保留原始社交網(wǎng)絡圖的結(jié)構(gòu)信息。

本文的主要貢獻如下：

(1)研究了不直接對邊進行擾動的邊差分隱私方法，通過滿足差分隱私約束的MCMC算法先采樣HRG的樹狀圖，再對HRG內(nèi)部的連接概率進行干擾來實現(xiàn)差分隱私。

(2)研究了一種可用于社交網(wǎng)絡圖發(fā)布的差分隱私保護模型DP2Gsister，其包括DPtoTsample和DPtoGsister兩個主要算法。

(3)設(shè)計了一種擴展的DP2Gsister方法，稱為multiR_DP2Gsister，可以用于增量圖發(fā)布中的隱私保護。

(4)在真實數(shù)據(jù)集上進行實驗，從算法收斂性、度分布、信息損失度、平均聚類系數(shù)、平均路徑長度幾方面做評估與分析，證明本文研究的模型在保證數(shù)據(jù)隱私性的基礎(chǔ)上較好地保證了數(shù)據(jù)可用性[11]。

1 相關(guān)概念及背景知識

本文主要研究面向無向無權(quán)社交網(wǎng)絡[12]的差分隱私保護方法。首先介紹與本文研究相關(guān)的概念及背景知識。

1.1 主要符號及其意義

本文中主要符號及其意義如表1所示。

1.2 差分隱私

定義1：ε-差分隱私

一個隨機算法Α的輸出空間為Range(A)。若對任意一對鄰居數(shù)據(jù)集D,D′和D和D′有且只有一條記錄k不同，及任一輸出O∈Range(A)均滿足：

Pk[A(D)∈O]≤eεPk[A(D′)∈O]

則稱算法Α滿足ε-差分隱私[5]，ε為隱私預算，P表示概率。差分隱私隱藏了單個個體在數(shù)據(jù)集中的存在性。ε越小，隱私保證越強。

定義2：全局敏感度

對于任意一對鄰居數(shù)據(jù)集D和D′，查詢函數(shù)f的全局敏感度定義為：

(2)

定義3：拉普拉斯機制

DWORK C等人[5]首次提出拉普拉斯機制，對于一個數(shù)據(jù)集D，一個函數(shù)f，一個隱私參數(shù)ε，函數(shù)f的返回值是真實值加噪聲后的結(jié)果。這個噪聲是由概率密度函數(shù)為

(3)

的拉普拉斯分布產(chǎn)生的。對于任意的函數(shù)f：D→R，算法A(D)=f(D)+滿足ε-差分隱私。

定義4：指數(shù)機制

定義一個估價函數(shù)q，它對每一種輸出計算出一個分值，分值高的輸出有更大概率被發(fā)布。

1.3 層次隨機圖模型(HRG)[13]

定義4：層次隨機圖模型是基于節(jié)點間關(guān)聯(lián)程度構(gòu)建的二叉樹結(jié)構(gòu)的隨機圖模型。對于一個圖G，HRG通過其樹狀結(jié)構(gòu)T和連接概率序列{Pr}來表征G。如圖1所示，圖1(a)表示社交網(wǎng)絡圖G，圖1(b)和圖1(c)分別表示它對應的兩個可能的樹狀結(jié)構(gòu)。內(nèi)部節(jié)點r標記的數(shù)值為以該節(jié)點為根節(jié)點的左右子樹的連接概率Pr，Pr=|er|/(|nLr|·|nRr|)，其中，er為左右子樹之間的連接數(shù)，nLr和nRr分別為左右子樹中的節(jié)點數(shù)量。

圖1 層次隨機圖模型

1.4 似然函數(shù)L

似然函數(shù)L為

(4)

1.5 姊妹圖

本文提出“姊妹圖”的概念，用Gsister表示。姊妹圖是一系列差分隱私算法處理后得到的發(fā)布圖，它盡可能好地保留了原始圖的結(jié)構(gòu)信息。

2 DP2Gsister：基于差分隱私的社交網(wǎng)絡數(shù)據(jù)發(fā)布模型

利用HRG模型進行社交網(wǎng)絡數(shù)據(jù)發(fā)布隱私保護模型研究時需要應對兩個挑戰(zhàn)：(1)使HRG盡可能近似地保留原始社交網(wǎng)絡圖的結(jié)構(gòu)信息；(2)實現(xiàn)邊差分隱私以保護網(wǎng)絡中個體之間的關(guān)系。

為此，本文設(shè)計了DP2Gsister模型。該模型分成兩個階段來應對上述挑戰(zhàn)：(1)算法1，利用MCMC算法差分隱私的從所有原圖可能生成的候選樹狀圖空間T中采集樣本圖Tsample；(2)算法2，對于Tsample中的連接概率序列{Pr}應用拉普拉斯機制添加噪聲生成噪聲概率序列{Pn}.根據(jù)Tsample和{Pn}生成凈化后的社交網(wǎng)絡圖Gsister。將全部的隱私預算ε分為ε1和ε2兩部分，分別用于算法1和算法2，使其均滿足差分隱私。

2.1 差分隱私算法設(shè)計

算法1為差分隱私MCMC算法,下面給出具體的算法步驟，如表2所示。

算法2為差分隱私姊妹圖生成算法，下面給出具體的算法步驟，如表3所示。

表2 差分隱私MCMC算法

表3 差分隱私姊妹圖生成算法

算法2的主要思路是計算層次隨機圖的內(nèi)部節(jié)點的連接概率，進而利用拉普拉斯機制對其添加噪聲。由定義3可知算法滿足ε2-邊差分隱私。最后按照內(nèi)部節(jié)點的噪聲概率序列依次生成相對應的邊，從而得到發(fā)布的姊妹圖Gsister。

根據(jù)差分隱私的組合特性可知，DP2Gsister模型滿足ε-差分隱私，其中ε=ε1+ε2。

2.2 multiR_DP2Gsister：增量社交網(wǎng)絡圖發(fā)布隱私保護模型

由上述算法1和算法2構(gòu)成的DP2Gsister模型適用于單次數(shù)據(jù)發(fā)布場景下的隱私保護。然而，考慮到真實的社交網(wǎng)絡是不斷變化的，將針對單次數(shù)據(jù)發(fā)布的方法直接應用到多次數(shù)據(jù)發(fā)布的場景下效果不佳。因此，為解決增量數(shù)據(jù)發(fā)布的隱私保護問題，在DP2Gsister模型的基礎(chǔ)上研究設(shè)計了一種可用于增量社交網(wǎng)絡圖發(fā)布的隱私保護算法，稱為multiR_DP2Gsister。

① http://socialnetworks.mpi-sws.org/data-wosn2009.html

② http://snap.stanford.edu/data/index.html

定義:隨時間增量變化的社交網(wǎng)絡圖表示為G1，G2，…，Gt，時刻t的社交網(wǎng)絡圖表示為Gt=。假設(shè)Gt相對于Gt-1“只增不減”，即Vt-1∈Vt，Et-1∈Et。本研究只考慮邊的增添，忽略節(jié)點的變化。

由于社交網(wǎng)絡中的節(jié)點具有很強的關(guān)聯(lián)性，節(jié)點間一條邊的增加就有可能改變樣本樹狀圖的整個結(jié)構(gòu)。高敏感性直接造成了需要添加的噪聲增多。因此，針對層次隨機圖的高敏感特征，在DP2Gsister的基礎(chǔ)上，本文設(shè)計了用于實現(xiàn)增量社交網(wǎng)絡圖發(fā)布的隱私保護模型multiR_DP2Gsister，下面給出具體的算法步驟，如表4所示。

表4 差分隱私增量社交網(wǎng)絡圖發(fā)布算法

算法3的主要思想是利用t1時刻的樣本層次隨機圖編碼網(wǎng)絡結(jié)構(gòu)，對于每一條新增的邊，找到其對應的葉子節(jié)點的最小共同祖先rlowest，更新rlowest的連接概率，進而添加拉普拉斯噪聲使其滿足ε2′-差分隱私。樣本層次隨機圖的樹狀結(jié)構(gòu)Tsample是隱私預算設(shè)為0.5時DPtoTsample采樣得到的。

此外，在添加噪聲之前，增設(shè)一項策略判斷噪聲尺度是否超過某個閾值，若超出閾值，則認為添加這樣的噪聲會嚴重破壞網(wǎng)絡結(jié)構(gòu)。解決方法是當噪聲尺度λ超出設(shè)定的范圍時，用Erdos-Renyi隨機圖模型置換當前對應的子樹，然后再添加噪聲進行擾動。

3 實驗評估及分析

為了評估DP2Gsister和multiR_DP2Gsister模型的可用性，本文在兩個典型的社交網(wǎng)絡數(shù)據(jù)集(Facebook①和wiki-Vote②)上進行了實驗。實驗環(huán)境為Intel Corei5 CPU 3.20 GHz，8 G內(nèi)存，Ubuntu服務器，編程語言C++。

3.1 實驗設(shè)置

實驗分別選用靜態(tài)數(shù)據(jù)集(統(tǒng)計信息見表5)和增量數(shù)據(jù)集(統(tǒng)計信息見表6)評估DP2Gsister和multiR_DP2Gsister兩個模型的效果。

表5 靜態(tài)數(shù)據(jù)集統(tǒng)計信息

表5中數(shù)據(jù)集Facebook包含的是朋友關(guān)系信息，節(jié)點代表Facebook用戶，如Facebook中包含13 097位用戶；邊代表用戶之間的朋友關(guān)系，某用戶與另一位用戶是Facebook好友，則邊數(shù)計1，相應的代表兩位用戶的節(jié)點之間產(chǎn)生一條連接，此數(shù)據(jù)集中包含44 624條邊。Wikipedia是由世界各地的志愿者合作撰寫的免費百科全書。數(shù)據(jù)集wiki-Vote包含的是維基百科管理員的選舉投票信息，其中節(jié)點代表參與選舉投票的維基百科用戶，該數(shù)據(jù)集包含7 115位用戶；邊代表用戶之間的投票關(guān)系，某用戶為另一位用戶投票，則邊數(shù)計1，該數(shù)據(jù)集包含100 762條邊。

表6 增量數(shù)據(jù)集統(tǒng)計信息

表6中數(shù)據(jù)集Facebook1包含的是2007年1月至2007年6月Facebook網(wǎng)絡中的朋友關(guān)系信息，數(shù)據(jù)集Facebook2包含的是2007年7月時Facebook網(wǎng)絡中的朋友關(guān)系信息，包含14 561位用戶，58 331條邊，此時相對于數(shù)據(jù)集Facebook1新增了13 707條邊，即新增13 707條朋友關(guān)系記錄。因為本研究只考慮邊的增刪，不考慮節(jié)點的改變，所以在實驗前首先對數(shù)據(jù)集Facebook2進行處理，刪除與數(shù)據(jù)集Facebook1相比新增節(jié)點關(guān)聯(lián)的邊，只保留在原始節(jié)點間新增的邊。

3.2 實驗評估與分析

在實驗中，首先從算法收斂性、度分布兩方面對DP2Gsister模型進行實驗評估與分析，然后從信息損失度、平均聚類系數(shù)、平均路徑長度三方面對multiR_DP2Gsister模型進行實驗評估與分析。

3.2.1DP2Gsister模型的實驗評估與分析

將DP2Gsister模型的隱私預算設(shè)為ε=1(ε=ε1+ε2)，分成ε1=0.5 和ε2=0.5，ε1=0.2 和ε2=0.8，ε1=0.8 和ε2=0.2三種組合，在表1所示數(shù)據(jù)集上進行實驗并分析結(jié)果。

(1)logL-step

如圖2所示，實驗通過分析log-likelihood隨馬爾科夫步數(shù)step的變化趨勢判斷MCMC算法的收斂情況。圖2(a)和圖2(b)分別展示了在Facebook和wiki-Vote數(shù)據(jù)集上，不同預算分配下logL隨馬爾科夫步數(shù)step的變化趨勢?？梢园l(fā)現(xiàn)logL隨著step的增加逐漸變大且很快趨于穩(wěn)定，說明DP2Gsister在MCMC運行下采樣圖與原始圖的相似度越來越高且收斂很快。此外，可以觀察到ε1=0.5和ε2=0.8的效果差距不大，由此可以推斷即使分配較少的隱私預算也不會影響數(shù)據(jù)可用性。

圖2 MCMC算法收斂情況

(2)度分布

如圖3所示，實驗通過對比原始社交網(wǎng)絡圖G和發(fā)布圖Gsister的度分布統(tǒng)計情況分析發(fā)布數(shù)據(jù)的可用性。圖3(a)和圖3(b)分別展示了Facebook和wiki-Vote的原始圖和發(fā)布圖的度分布統(tǒng)計情況。圖中橫軸表示度數(shù)，縱軸表示擁有相應度數(shù)的節(jié)點數(shù)。original對應的曲線代表原始圖的度分布情況，其余三條曲線分別代表ε1=0.5和ε2=0.5，ε1=0.2和ε2=0.8，ε1=0.8和ε2=0.2三組隱私預算分配下得到的發(fā)布圖的度分布情況?？梢园l(fā)現(xiàn)DP2Gsister在三組實驗中均能使發(fā)布圖保持和原始圖相似的度分布，表現(xiàn)為大多數(shù)節(jié)點擁有低度數(shù)，極少節(jié)點擁有高度數(shù)的網(wǎng)絡特征。這證明該模型能夠很好地保留原始圖的結(jié)構(gòu)特點，從而保證數(shù)據(jù)可用。

圖3 度分布情況

3.2.2multiR_DP2Gsister模型的實驗評估與分析

上述實驗證明DP2Gsister模型在處理單次數(shù)據(jù)發(fā)布上效果顯著，接下來實驗評估其擴展模型multiR_DP2Gsister的效果。設(shè)置multiR_DP2Gsister模型的隱私預算為ε2′=0.5，在圖2所示的數(shù)據(jù)集上進行實驗并分析結(jié)果。

(1)信息損失度

要實現(xiàn)增量數(shù)據(jù)發(fā)布中的隱私保護，往往需要添加更多的噪聲以保證與單次發(fā)布時相仿的數(shù)據(jù)質(zhì)量。額外添加的噪聲容易導致數(shù)據(jù)損失增加，因此，分析隱私保護模型處理后的數(shù)據(jù)損失是衡量模型效果的一項重要指標。本文引入信息損失度(Information Loss, IL)衡量數(shù)據(jù)可用性。

信息損失度為:

(5)

圖4所示為t=1和t=2時刻經(jīng)multiR_DP2Gsister模型處理后的發(fā)布圖的信息損失度量。從圖中可以看出，對于t=2時刻增加了邊的數(shù)據(jù)集，該算法將信息損失控制在25%以下較好地保證了數(shù)據(jù)可用性。

圖4 t1和t2時刻發(fā)布圖的信息損失

(2)平均聚類系數(shù)和平均最短路徑

平均聚類系數(shù)(Average Clustering Coefficient, ACC)和平均最短路徑(Average Path Length, APL)通常被用來衡量網(wǎng)絡的整體特征。因此，本文引入ACC和APL衡量原始圖和發(fā)布圖的特征差異。

(6)

其中，Ci為節(jié)點i的局部聚類系數(shù)，T(i)為網(wǎng)絡中由節(jié)點i參與組成的三角形的數(shù)目，d(i)為節(jié)點i的度數(shù)。

(7)

其中，n為網(wǎng)絡中的節(jié)點數(shù)目，PL(i,j)為節(jié)點i、j之間的最短路徑。

如表3所示，用平均聚類系數(shù)ACC和平均路徑長度APL量化原始圖和發(fā)布圖的網(wǎng)絡特征，可以看出multiR_DP2Gsister模型處理后的發(fā)布圖在APL上與原始圖差異非常小，在ACC上差異不大，證明發(fā)布圖能夠較好地保留原始的網(wǎng)絡特征。

表3 multiR_DP2Gsister處理后的發(fā)布圖與原始圖ACC和APL對比情況

4 結(jié)論

本文在社交網(wǎng)絡數(shù)據(jù)發(fā)布的場景下研究了一種差分隱私社交網(wǎng)絡圖發(fā)布模型DP2Gsister。該模型利用差分隱私MCMC算法DPtoTsample和差分隱私姊妹圖生成算法DPtoGsister重構(gòu)原始圖的結(jié)構(gòu)信息，進而對連接概率添加噪聲，最終生成具有隱私保證的姊妹圖Gsister，且實驗證明Gsister較好地保留了原始圖的結(jié)構(gòu)信息。此外，考慮社交網(wǎng)絡數(shù)據(jù)增量更新的需求，對DP2Gsister進行擴展得到multiR-DP2Gsister模型，該模型可用于增量社交網(wǎng)絡圖發(fā)布的隱私保護。實驗證明本文研究的模型在數(shù)據(jù)可用性與隱私性之間達到了較好的平衡。

[1] CHENG J, FU W C, LIU J. K-isomorphism: privacy preserving network publication against structural attacks[C]// ACM SIGMOD International Conference on Management of Data, SIGMOD 2010, Indianapolis, Indiana, USA, June. DBLP, 2010:459-470.

[2] SUN C, YU P S, KONG X, et al. Privacy preserving social network publication against mutual friend attacks[C]//International Conference on Data Mining Workshops. IEEE, 2013:883-890.

[3] ZHOU B, PEI J. Preserving privacy in social networks against neighborhood attacks[C]//International Conference on Data Engineering. IEEE, 2008:506-515．

[4] 郭彩華, 王斌, 朱懷杰,等. 增量的動態(tài)社會網(wǎng)絡匿名化技術(shù)[J]. 計算機研究與發(fā)展, 2016, 53(6):1352-1364.

[5] DWORK C, MCSHERRY F, NISSIM K. Calibrating noise to sensitivity in private data analysis[J]. Lecture Notes in Computer Science, 2006, 3876(8):265-284.

[6] CHEN R, FUNG B C M, YU P S, et al. Correlated network data publication via differential privacy[J]. VLDB Journal — the International Journal on Very Large Data Bases, 2014, 23(4):653-676.

[7] ZHANG X, MENG X, CHEN R. Differentially private set-valued data release against incremental updates[M].Database Systems for Advanced Applications, 2013:392-406.

[8] XIAO Q, CHEN R, TAN K L. Differentially private network data release via structural inference[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2014:911-920.

[9] WANG Y, WU X, WU L. Differential privacy preserving spectral graph analysis[C]// Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, 2013:329-340.

[10] DWORK C. The differential privacy frontier (extended abstract)[J]. Theory of Cryptography Conference, 2009, 5444:496-502.

[11] FUNG B C M, WANG K, CHEN R, et al. Privacy-preserving data publishing: a survey of recent developments[J]. ACM Computing Surveys, 2010, 42(4):14.

[12] 劉向宇, 王斌, 楊曉春. 社會網(wǎng)絡數(shù)據(jù)發(fā)布隱私保護技術(shù)綜述[J]. 軟件學報, 2014, 25(3):576-590.

[13] CLAUSET A, MOORE C, NEWMAN M E J. Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008, 453(7191):98.