黃茜茜，蔣千越，蔣 琳，熊圳天

(1.哈爾濱工業(yè)大學 計算機科學與技術(shù)學院，廣東 深圳 518000;2.國防科學技術(shù)大學 計算機學院，湖南 長沙 410000)

0 引言

社交網(wǎng)絡的飛速發(fā)展為人們工作生活帶來了極大的便利，而其中的個人隱私問題也越來越引發(fā)關注和擔憂。在社交網(wǎng)絡上公開信息是用戶的自愿活動，用戶通常不知道誰能夠訪問他們的數(shù)據(jù)以及他們的數(shù)據(jù)如何被使用，社交網(wǎng)絡中包含很多敏感信息，比如個人信息、朋友關系等，攻擊者甚至可能通過個體與個體之間的連接來推斷他們的朋友關系以及其他敏感信息。社交網(wǎng)絡的隱私保護是以網(wǎng)絡節(jié)點為對象，利用某種隱私保護模型對其敏感信息進行保護。

對社交網(wǎng)絡的研究通常將其抽象為圖結(jié)構(gòu)，即形式化為G=(V,E)，圖G表示社交網(wǎng)絡，每個個體抽象化為一個節(jié)點，V表示節(jié)點集，節(jié)點之間的鏈接關系用邊表示，E代表邊集。還可以用三元組表示G=(V,E,W)，其中W表示邊上的權(quán)值。

常用的隱私保護技術(shù)有SWEENEY L提出的k-anonymity[1]、MACHANAVJJHALA A等提出的l-diversity[2]和LI N等提出的t-closeness[3]等，以及在這些模型基礎上不斷完善的隱私模型。這些基于匿名方法的模型能夠在一定程度上保護社交網(wǎng)絡的隱私信息，但是對于擁有背景知識的攻擊者卻無能為力。比如對于匿名發(fā)布的社交網(wǎng)絡圖，攻擊者從外部信息得知其中某兩個節(jié)點來自同一個研究小組，那么攻擊者就有很大把握推斷他們是朋友關系。

DWORK C提出的差分隱私(Differential Privacy)[4]近年來成為新的研究熱點。差分隱私是一種嚴格的且能被證明的隱私定義，其基本思想是對原始數(shù)據(jù)或者統(tǒng)計結(jié)果添加噪音，使攻擊者無法區(qū)分某個記錄加入或者刪除于某個數(shù)據(jù)集。差分隱私技術(shù)能夠抵抗攻擊者所具有的背景知識，并且根據(jù)其隱私參數(shù)ε，在隱私保護程度和數(shù)據(jù)可用性之間取得良好的平衡。

研究人員已經(jīng)將差分隱私應用于社交網(wǎng)絡的隱私保護上，并且取得了很好的效果。本文首先對社交網(wǎng)絡中的特點和隱私威脅進行了介紹，然后對差分隱私的定義進行了闡述，最后結(jié)合前人所做的研究，著重對差分隱私在社交網(wǎng)絡隱私保護的應用進行了綜述。

1 社交網(wǎng)絡上的隱私信息

可將社交網(wǎng)絡圖分為有向圖和無向圖，本文只研究連通的無向圖的隱私保護。社交網(wǎng)絡的隱私信息包括節(jié)點隱私(個體隱私信息)、邊隱私(個體之間的連接關系)、圖結(jié)構(gòu)隱私[5]。下面將對社交網(wǎng)絡的隱私特點進行敘述。

1.1 節(jié)點隱私

Twitter、新浪微博上的用戶即可看作社交網(wǎng)絡的節(jié)點。節(jié)點隱私信息可分為下面兩類：

(1) 存在性信息，可根據(jù)某節(jié)點是否存在于某個社交網(wǎng)絡圖獲取。比如在Twitter中，某用戶是否被其他用戶關注。

(2) 標識符信息，可細分為身份信息(Identifier, ID)、準標識符信息(Quasi-Identifier, QI)和敏感信息(Sensitive Attribute, SA)。身份信息即用戶的唯一身份；準標識符本身并不是唯一的標識符，但可以與其他準標識符組合以創(chuàng)建唯一標識符，攻擊者可利用準標識符信息進行重識別攻擊；敏感信息指用戶不愿發(fā)布的隱私信息，泄露會導致嚴重的影響。

1.2 邊隱私

社交網(wǎng)絡中的邊通常表示節(jié)點之間的關系，比如微信中的朋友關系、新浪微博中用戶之間互相關注等等。邊的隱私信息中最重要的是邊權(quán)重信息，邊權(quán)重信息表示兩個節(jié)點的緊密程度，權(quán)重越大，節(jié)點之間聯(lián)系的越緊密。例如微信上兩個用戶頻繁交流的次數(shù)。攻擊者可以根據(jù)權(quán)重信息進行攻擊，挖掘出隱私信息。

我們的目標是在盡可能保持數(shù)據(jù)可用性的情況下保護社交網(wǎng)絡中的權(quán)重信息。DAS S等[6]提出邊權(quán)重的匿名。他們提出了一個線性規(guī)劃模型來保護圖的一些性質(zhì)，比如最短路徑、最小生成樹等，這些都是權(quán)重的線性函數(shù)。LIU L等[7]設計了兩種權(quán)重保護方法：基于圖論的高斯隨機乘法和貪婪攝動算法。

這些方法都是對于邊隱私信息的初步保護，難以抵抗擁有背景知識的攻擊者的攻擊，后面將會介紹用差分隱私技術(shù)對邊隱私信息的保護[8-9]。

1.3 圖結(jié)構(gòu)隱私

圖的結(jié)構(gòu)隱私信息是社交網(wǎng)絡圖特有的，比如節(jié)點度數(shù)、鄰接信息、中心區(qū)域距離以及圖的割集等。圖結(jié)構(gòu)信息的隱私保護更為重要。ZHOU B等[10]提供了保護圖鄰接信息的一種方法，將k-anonymity應用于對鄰接信息的處理，能對圖的隱私信息進行有效的保護。

節(jié)點度數(shù)指與目標節(jié)點直接鏈接的節(jié)點數(shù)目，如果攻擊者得到某節(jié)點的度信息，可以與數(shù)據(jù)中節(jié)點的度數(shù)信息進行比對，獲取該節(jié)點的隱私。攻擊者還可以通過節(jié)點度數(shù)進行鏈接攻擊。

2 差分隱私的定義

2.1 (ε,δ)-差分隱私

給定某隨機函數(shù)K，若函數(shù)K在給定的相鄰數(shù)據(jù)集D1和D2(二者至多相差一條記錄)上的任意輸出結(jié)果S(S∈Range(K))滿足下面的不等式，則K滿足(ε,δ)-差分隱私[11]。

Pr[K(D1)∈S]≤exp(ε)*Pr[K(D2)∈S]+δ

(1)

其中，δ是松弛因子，如果δ=0，則隨機函數(shù)K給出嚴格的ε-差分隱私[12]。ε稱為隱私參數(shù)，用來平衡隱私保護程度和數(shù)據(jù)可用性。ε越小，隱私保護程度越高，而數(shù)據(jù)可用性越低。實現(xiàn)差分隱私技術(shù)需要引入噪聲，而噪聲大小與數(shù)據(jù)集的全局敏感性密切相關，下面介紹全局敏感性。

2.2 全局敏感性

對于任意的查詢函數(shù)Q:D→Rk(函數(shù)Q將數(shù)據(jù)集D映射到k維的實數(shù)空間)，函數(shù)Q的全局敏感性[8]由ΔQ表示：

(2)

D1和D2是相鄰的數(shù)據(jù)集，全局敏感性衡量對相鄰數(shù)據(jù)集作查詢操作的所得到的最大差異，比如一個數(shù)據(jù)集插入或者刪除一條記錄后所得到的最大查詢差異值。

2.3 噪聲機制

最常用的噪聲機制[11]是Laplace機制，它通過Laplace分布產(chǎn)生噪聲對查詢操作產(chǎn)生的輸出值進行擾動，使攻擊者無法區(qū)分真實值和擾動后的值，從而實現(xiàn)差分隱私保護。如下：

對于任意查詢函數(shù)Q:D→Rk，全局敏感性為ΔQ，隨機算法K(D)=Q(D)+Y滿足ε-差分隱私，其中Y～(Lap(ΔQ/ε))k為添加的Laplace噪聲，是k維的獨立同分布的向量。噪聲大小與全局敏感性ΔQ成正比，與隱私參數(shù)ε成反比，即ΔQ越大，ε越小，添加的噪聲越大，隱私保護效果越好，數(shù)據(jù)可用性越低。

3 差分隱私在社交網(wǎng)絡隱私保護的應用

3.1 邊-差分隱私和點-差分隱私

因為傳統(tǒng)差分隱私要求兩個數(shù)據(jù)集是相鄰的數(shù)據(jù)集，即二者只相差一條記錄，那么應用到社交網(wǎng)絡圖中可以分為邊-差分隱私和點-差分隱私[13]。對于邊-差分隱私，要求圖G′為圖G刪除或添加某一條邊得到的。形式化定義為對于任意圖G=(V,E)，G′=(V′,E′)，它們是邊相鄰的，如果對于任一條邊e∈E′，滿足V′=V,E′=E-{e}。HAY M等[14]對邊-差分隱私做了擴展，提出k邊-差分隱私,即圖G′為圖G刪除或添加k條邊得到的。對于點-差分隱私，要求圖G′為圖G刪除或添加某一點以及與該點相關聯(lián)的所有邊。即G=(V,E)，G′=(V′,E′)，它們是點相鄰的，如果對于任一點x∈V，如果V′=V-x，E′=E-{(v1,v2)|v1=x∨v2=x}。點-差分隱私比邊-差分隱私提供更強的隱私保護，但對數(shù)據(jù)可用性的破壞也更嚴重。例如在一個星形的社交網(wǎng)絡圖中，一個點與其他所有點相連接，刪除該點后，圖中不存在任何一條邊，完全失去研究價值。實驗證明，k邊-差分隱私能夠和點-差分隱私提供相同的隱私保護。

3.2 權(quán)重信息的隱私保護

邊權(quán)重是社交網(wǎng)絡圖中重要的信息，很多數(shù)據(jù)發(fā)布者將邊權(quán)重作為圖的統(tǒng)計信息。LI X等[15]提出MB-CI(Merging Barrels and Consistency Inference)方法來保護帶權(quán)社交網(wǎng)絡圖。該方法通過將權(quán)重序列看作非屬性的柱狀圖，再將差分隱私應用于柱狀圖中。該方法的獨到之處在于網(wǎng)絡圖中很多邊有相同的權(quán)重，可以把有相同計數(shù)的桶合并(即Merging Barrels)，這樣可以減少所需的噪聲量。除此之外，由于噪聲本身的原因，簡單的合并操作可能會泄露隱私，作者根據(jù)權(quán)重序列的原始順序做一致性推理(Consistency Inference)，這是重要的后處理步驟。實驗證明這種方法能很好提高數(shù)據(jù)的可用性。COSTEA S等[16]分析差分隱私如何用于邊權(quán)重的隱私保護上，通過Dijkstra最短路徑算法來評估發(fā)布數(shù)據(jù)的質(zhì)量，得出具有較大權(quán)重值的網(wǎng)絡圖適合應用差分隱私技術(shù)進行保護的結(jié)論。

3.3 社交網(wǎng)絡圖的度數(shù)信息發(fā)布

度數(shù)分布是網(wǎng)絡圖的重要特征，直接發(fā)布度數(shù)信息可能導致隱私的泄露。HAY M等[14]利用改進的差分隱私技術(shù)，對含噪聲的度數(shù)分布查詢執(zhí)行后處理步驟，證明可以在不犧牲隱私的情況下提高準確性，獲得更為精確的度數(shù)分布。DAY W Y等[17]通過投影方法降低敏感度，研究在點-差分隱私下的度數(shù)分布的發(fā)布問題。在滿足點-差分隱私的條件下對網(wǎng)絡圖作投影，使圖的最大度數(shù)不超過度數(shù)閾值θ，并且在投影過程中盡量保護隱私信息。作者提出基于聚合和累積直方圖的方法來發(fā)布度數(shù)分布。實驗表明，這兩種方法大大減少了逼近真實度數(shù)分布的誤差，相對于現(xiàn)有的工作具有顯著的改進。KARWA V等[18]研究了度數(shù)序列的發(fā)布問題，在滿足差分隱私的條件下保護了隱私，同時允許分析人員使用發(fā)布的數(shù)據(jù)執(zhí)行統(tǒng)計推斷。

3.4 合成圖的發(fā)布

因為差分隱私的本質(zhì)是對數(shù)據(jù)作擾動，所以如果在原始圖中加入大量噪聲的話，很難得到可發(fā)布的有價值的合成圖。SUN Y等[19]提出保護數(shù)據(jù)可用性的關鍵是在合成圖中保留重要數(shù)據(jù)的原始值與否。作者分析了圖數(shù)據(jù)的k三角形計數(shù)(圖數(shù)據(jù)的一種統(tǒng)計信息)，提出了滿足邊-差分隱私的合成圖發(fā)布的新方法，名為NoiseGraph。實驗結(jié)果顯示NoiseGraph在很低的隱私預算下，仍然能保證合成圖的k三角形計數(shù)是精確的。QIN Z等[20]提出了LDPGen，一種滿足本地差分隱私的合成圖生成技術(shù)。每次用戶報道信息時，LDPGen注入噪聲確保本地差分隱私。在此過程中推導出最佳參數(shù)，將結(jié)構(gòu)相似的用戶聚集在一起。一旦獲得了良好的用戶聚類，LDPGen就會調(diào)整現(xiàn)有的社交圖生成模型來構(gòu)建新的合成圖。WANG Y等[21]研究了在圖生成中實施邊-差分隱私的問題，其思想是對從原始網(wǎng)絡圖學習到的參數(shù)加噪聲，然后使用加噪后的參數(shù)發(fā)布合成圖。PROSERPIO D等[22]提供了一種基于差分隱私的圖合成的工作流程。

3.5 差分隱私在社交網(wǎng)絡圖的其他應用

AHMED F等[23]利用隨機矩陣的投影方法發(fā)布社交網(wǎng)絡圖的結(jié)構(gòu)信息，并且滿足差分隱私。關鍵思想是使用隨機投影方法將圖的鄰接矩陣的每一行投影到一個低維空間中，然后添加少量噪聲實現(xiàn)差分隱私。與現(xiàn)有的特征向量(鄰接矩陣的特征向量是重要的結(jié)構(gòu)信息)的近似方法相比，該方法計算效率高，保留了效用并滿足差分隱私。WANG Y等[24]分析了基于差分隱私保的譜信息(特征值和特征向量)保護，因為經(jīng)過噪聲擾動的輸出特征向量不再相互正交，作者通過向量正交技術(shù)對輸出的特征向量作了后處理。SALA A等[25]提出了一個差分隱私圖模型Pygmalion,Pygmalion將圖的詳細結(jié)構(gòu)提取為度數(shù)相關統(tǒng)計量，將噪聲引入到結(jié)果數(shù)據(jù)集中，并生成合成圖。

LU W等[26]提出了針對于圖結(jié)構(gòu)參數(shù)估計的指數(shù)隨機圖模型ERGM。ERGM是一個滿足差分隱私的統(tǒng)計建模工具，可以讓分析人員分析社交網(wǎng)絡的結(jié)構(gòu)和形成過程。MIR D等[27]提出參數(shù)估計模型stochastic Kronecker graph model來對網(wǎng)絡圖建模，建立圖的參數(shù)的估計器。SOMMER等[28]根據(jù)差異隱私框架對基于鄰近社交網(wǎng)絡設置的用戶進行匹配，可以準確地配對類似的用戶，同時提供不讓惡意用戶推斷隱私信息的保護。

3.6 小結(jié)

將上述差分隱私在社交網(wǎng)絡隱私保護的應用進行歸納總結(jié)，如表1所示。

表1 各種方法優(yōu)缺點的比較

表1對差分隱私在社交網(wǎng)絡隱私保護的應用的各種方法的優(yōu)缺點進行了比較。各個方法有其特定的應用場景，比如文獻[15]等使用KSP測量未改變的最短路徑的比例；文獻[16]使用Erdos-Renyi模型進行圖的生成；文獻[14]在合成的數(shù)據(jù)集和真實的數(shù)據(jù)集都做了實驗驗證；文獻[17]使用了8個來自不同領域的真實數(shù)據(jù)集，包括社交網(wǎng)絡、引用網(wǎng)絡和郵件網(wǎng)絡等；文獻[18]提出的方法主要估計差分隱私算法產(chǎn)生的度數(shù)分布的統(tǒng)計特性；文獻[19]在四個真實數(shù)據(jù)集(GrQc、HepPh、HepTh和wiki-Vote)做了應用場景的模擬等。

4 結(jié)論

本文主要講述了差分隱私在社交網(wǎng)絡中的各類應用，如權(quán)重信息的隱私保護、度數(shù)信息的發(fā)布問題、合成圖的發(fā)布問題等。雖然已經(jīng)提出了較多的方法，在未來還有很多的研究方向。比如在社交網(wǎng)絡圖的度數(shù)發(fā)布上，使用已保存的低度數(shù)信息預測高度數(shù)節(jié)點的分布是未來的一個研究方向；在合成圖的發(fā)布上，可以考慮其他可用性度量標準，并使合成圖滿足多個可用性度量標準；在去中心社交網(wǎng)絡的隱私保護上，結(jié)合更強大的隱私模型、處理權(quán)重信息和點/邊屬性是未來要做的工作。

[1] SWEENEY L. k-anonymity: a model for protecting privacy[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based System, 2002, 10(5): 557-570.

[2] MACHNAVAJJHALA A, KIFER D, GEHRKE J. l-diversity: privacy beyond k-anonymity[C]//Proceedings of the 22nd International Conference on Data Engineering(ICDE). Atlanta, Georgia, USA, 2006: 24-35.

[3] LI N, LI T. t-closeness: privacy beyond k-anonymity and l-diversity[C]//Proceedings of the IEEE International Conference on Data Engineering(ICDE). Istanbul, Turkey, 2007: 106-115.

[4] DWORK C. Differential privacy[C]//Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. Venice, Italy, 2006: 1-12.

[5] 張冰，苗水清，李顯峰. 社會網(wǎng)絡隱私信息研究[J]. 無線互聯(lián)科技, 2017(22).

[6] DAS S, EGECIOGLU O, ABBADI A E. Anonymizing weighted social network graph[C]//Proceedings of the 26th IEEE International Conference on Data Engineering (ICDE ’10), Long Beach, Calif, USA, 2010:904-907.

[7] LIU L, WANG J et al. Privacy preserving in social networks against sensitive edge disclosure[R]. Tech Rep CMIDA-HiPSCCS 006-08, Department of Computer Science, University of Kentucky, 2008.

[8] TASK C, CLIFTON C. A guide to differential privacy theory in social network analysis[C]//The 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2012), Istanbul, Turkey,2012.

[9] XIAO Q, CHEN R, TAN K L. Differentially private network data release via structural inference[M]. KDD, 2014:911-920.

[10] ZHOU B, PEI J. The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks[J]. Knowledge & Information Systems, 2011, 28(1):47-77.

[11] DWORK C, MCSHERRY F, NISSIM K. Calibrating noise to sensitivity in private data analysis[C]//Proceedings of the 3th Theory of Cryptography Conference (TCC). New York, USA, 2006: 365-385.

[12] 孟曉峰，張嘯劍. 面向數(shù)據(jù)發(fā)布和分析的差分隱私保護[J]. 計算機學報, 2014,37(4):927-949.

[13] LANGWEG H, MEIER M. Towards a differential privacy theory for edge-labeled directed graphs[M]. Sicherheit 2018, Lecture Notes in Informatics (LNI), Gesellschaft für Informatik, Bonn,2018: 273.

[14] HAY M, LI C, MIKLAU G, et al. Accurate estimation of the degree distribution of private networks[C]//Proceedings of the 2009 Ninth IEEE International Conference on Data Mining, 2009:169-178.

[15] LI X, YANG J, Sun Z, et al. Differential privacy for edge weights in social networks[J]. Security and Communication Networks. Volume 2017, 4(8):1-10.

[16] COSTEA S, BARBU M, RUGHINIS R. Qualitative analysis of differential privacy applied over graph structures[C]//2013 11th RoEduNet International Conference, 2013:1-4.

[17] DAY W Y, LI N, LYU M. Publishing graph degree distribution with node differential privacy[M]. ACM SIGMOD, 2016.

[18] KARWA V, SLAVKOVIC A. Differentially private ′ graphical degree sequences and synthetic graphs[M]. Privacy in Statistical Databases, Springer, 2012.

[19] SUN Y, ZHAO H, Han Q, et al. Composite Graph Publication Considering Important Data[C]//International Conference of Pioneering Computer Scientists, Engineers and Educators. ICPCSEE, 2017: 207-219.

[20] QIN Z, YU T, Yang Y, et al. Generating synthetic decentralized social graphs with local differential privacy[C]//CCS ’17 Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. Dallas, Texas, USA, 2017:425-438.

[21] WANG Y, WU X. Preserving differential privacy in degree-correlation based graph generation[M]. TDP, 2013.

[22] PROSERPIO D, GOLDBERG S, MCSHERRY F. A workflow for differentially-private graph synthesis[C]//Proceedings of ACM Workshop on Online Social Networks (WOSN), 2012:13-18.

[23] AHMED F, JIN R, LIU A. A random matrix approach to differential privacy and structure preserved social network graph publishing[J]. arXiv preprint. arXiv:1307.0475, 2013.

[24] WANG Y, WU X, WU L. Differential privacy preserving spectral graph analysis[M]. PAKDD, 2013.

[25] SALA A, ZHAO X, WILSON C, et al. Sharing graphs using differentially private graph models[C]//Proceedings of the 11th ACM SIGCOMM Conference on Internet Measurement. Berlin, Germany, 2011: 81-98.

[26] LU W, MIKLAU G. Exponential random graph estimation under differential privacy[C]//20th ACM SIGKDD International Conference on Knowledge discovery and data mining, 2014:921-930.

[27] MIR D, WRIGHT R. A differentially private estimator for the stochastic Kronecker graph model[C]//EDBT-ICDT’12: Proceedings of the 2012 Joint EDBT/ICDT Workshops, ACM, 2012:167-176.

[28] SOMMER M, LIM L, Li D, et al. A differentially private matching scheme for pairing similar users of proximity based social networking applications[C]//Proceedings of the 51st Hawaii International Conference on System Sciences, 2018.