DP2Gsister:差分隱私社交網絡圖發布模型*

殷軼平，徐睿峰

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

0 引言

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

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

本文的主要貢獻如下：

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

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

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

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

1 相關概念及背景知識

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

1.1 主要符號及其意義

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

1.2 差分隱私

定義1：ε-差分隱私

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

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

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

定義2：全局敏感度

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

(2)

定義3：拉普拉斯機制

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

(3)

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

定義4：指數機制

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

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

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

圖1 層次隨機圖模型

1.4 似然函數L

似然函數L為

(4)

1.5 姊妹圖

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

2 DP2Gsister：基于差分隱私的社交網絡數據發布模型

利用HRG模型進行社交網絡數據發布隱私保護模型研究時需要應對兩個挑戰：(1)使HRG盡可能近似地保留原始社交網絡圖的結構信息；(2)實現邊差分隱私以保護網絡中個體之間的關系。

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

2.1 差分隱私算法設計

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

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

表2 差分隱私MCMC算法

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

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

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

2.2 multiR_DP2Gsister：增量社交網絡圖發布隱私保護模型

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

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

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

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

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

表4 差分隱私增量社交網絡圖發布算法

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

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

3 實驗評估及分析

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

3.1 實驗設置

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

表5 靜態數據集統計信息

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

表6 增量數據集統計信息

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

3.2 實驗評估與分析

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

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

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

(1)logL-step

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

圖2 MCMC算法收斂情況

(2)度分布

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

圖3 度分布情況

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

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

(1)信息損失度

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

信息損失度為:

(5)

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

圖4 t1和t2時刻發布圖的信息損失

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

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

(6)

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

(7)

其中，n為網絡中的節點數目，PL(i,j)為節點i、j之間的最短路徑。

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

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

4 結論

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

[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] 郭彩華, 王斌, 朱懷杰,等. 增量的動態社會網絡匿名化技術[J]. 計算機研究與發展, 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] 劉向宇, 王斌, 楊曉春. 社會網絡數據發布隱私保護技術綜述[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.